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.
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.
Solving combinatorial optimization problems on current noisy quantum devices is currently being advocated for (and restricted to) binary polynomial optimization with equality constraints via quantum heuristic approaches. This is achieved using, for example, the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). In this article, we present a decomposition-based approach to extend the applicability of current approaches to “quadratic plus convex” mixed binary optimization (MBO) problems, so as to solve a broad class of real-world optimization problems. In the MBO framework, we show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms), and continuous constrained convex subproblems (that can be solved cheaply with classical optimization solvers). The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit, an open-source quantum computing software development framework.
Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.
Relaxation is a common way for dealing with combinatorial optimization problems. QRAO (Quantum Random Access Optimization) is a quantum-relaxation based optimizer that uses fewer qubits than the number of bits in the original problem, by encoding multiple variables per qubit using QRAC (Quantum Random Access Code). Reducing the number of qubits will alleviate physical noise (typically, decoherence) and, as a result, the quality of the binary solution of QRAO may be robust against noise, which is however unknown. In this paper, we numerically demonstrate that the mean approximation ratio of the (3, 1)-QRAC Hamiltonian, i.e., the Hamiltonian utilizing the encoding of 3 bits into 1 qubit by QRAC, is less affected by noise compared to the conventional Ising Hamiltonian used in quantum annealer and QAOA (Quantum Approximate Optimization Algorithm). Based on this observation, we discuss a plausible mechanism behind the robustness of QRAO under depolarizing noise. Finally, we assess the number of shots required to estimate the values of binary variables correctly under depolarizing noise and show that the (3, 1)-QRAC Hamiltonian requires less shots to achieve the same accuracy compared to the Ising Hamiltonian.
Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.
The advent of quantum computing can potentially revolutionize how complex problems are solved. This paper proposes a two-loop quantum-classical solution algorithm for generation scheduling by infusing quantum computing, machine learning, and distributed optimization. The aim is to facilitate employing noisy near-term quantum machines with a limited number of qubits to solve practical power system optimization problems such as generation scheduling. The outer loop is a 3-block quantum alternative direction method of multipliers (QADMM) algorithm that decomposes the generation scheduling problem into three subproblems, including one quadratically unconstrained binary optimization (QUBO) and two non-QUBOs. The inner loop is a trainable quantum approximate optimization algorithm (T-QAOA) for solving QUBO on a quantum computer. The proposed T-QAOA translates interactions of quantum-classical machines as sequential information and uses a recurrent neural network to estimate variational parameters of the quantum circuit with a proper sampling technique. T-QAOA determines the QUBO solution in a few quantum-learner iterations instead of hundreds of iterations needed for a quantum-classical solver. The outer 3-block ADMM coordinates QUBO and non-QUBO solutions to obtain the solution to the original problem. The conditions under which the proposed QADMM is guaranteed to converge are discussed. Two mathematical and three generation scheduling cases are studied. Analyses performed on quantum simulators and classical computers show the effectiveness of the proposed algorithm. The advantages of T-QAOA are discussed and numerically compared with QAOA which uses a stochastic gradient descent-based optimizer.
The advent of quantum computing can potentially revolutionize how complex problems are solved. This paper proposes a two-loop quantum-classical solution algorithm for generation scheduling by infusing quantum computing, machine learning, and distributed optimization. The aim is to facilitate employing noisy near-term quantum machines with a limited number of qubits to solve practical power system optimization problems such as generation scheduling. The outer loop is a 3-block quantum alternative direction method of multipliers (QADMM) algorithm that decomposes the generation scheduling problem into three subproblems, including one quadratically unconstrained binary optimization (QUBO) and two non-QUBOs. The inner loop is a trainable quantum approximate optimization algorithm (T-QAOA) for solving QUBO on a quantum computer. The proposed T-QAOA translates interactions of quantum classical machines as sequential information and uses a recurrent neural network to estimate variational parameters of the quantum circuit with a proper sampling technique. T-QAOA determines the QUBO solution in a few quantum-learner iterations instead of hundreds of iterations needed for a quantum-classical solver. The outer 3-block ADMM coordinates QUBO and non-QUBO solutions to obtain the solution to the original problem. The conditions under which the proposed QADMM is guaranteed to converge are discussed. Two mathematical and three generation scheduling cases are studied. Analyses performed on quantum simulators and classical computers show the effectiveness of the proposed algorithm. The advantages of T-QAOA are discussed and numerically compared with QAOA which uses a stochastic gradient descent-based optimizer.