Quantum Combinatorial Optimization Algorithms for Network Reconfiguration: QRAO vs. QAOA
Anh Phuong Ngo, Hieu Trung Nguyen · 2024
This paper reviews a hybrid quantum-classical distributed algorithm for NP-hard combinatorial optimization problems, which is embedded in IBM Qiskit's Alternating Direction Method of Multipliers (ADMM) optimizer. We demonstrate a proof of concept for solving Mixed-Integer Convex Programs (MICP) in power system applications using a use case on power distribution network reconfiguration in IBM quantum computers. Using the Qiskit ADMM optimizer, the MICP is decomposed into two subproblems: a quadratic unconstrained binary optimization (QUBO) solved by quantum algorithms and a convex one solved by classical solvers. Our essential contribution is integrating the Quantum Random Access Optimization (QRAO) into the quantum-classical distributed framework and the existing Quantum Approximate Optimization Algorithm (QAOA) implemented in the Qiskit ADMM Optimizer. QRAO utilizes Quantum Random Access Codes (QRACs) to minimize qubit requirements and utilizes quantum state rounding for solution extraction. We examine the impact of noise on solutions derived from QRAO and compare them with results from QAOA using a use case on network reconfiguration in response to faults in the power distribution system.