Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers

Abstract

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, e.g., the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). 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.

References in corpus (20)

• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• The theory of variational hybrid quantum-classical algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum optimization using variational algorithms on near-term quantum devices
• Quantum autoencoders for efficient compression of quantum data
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Improving Variational Quantum Optimization using CVaR
• $XY$-mixers: analytical and numerical results for QAOA
• Performance of hybrid quantum/classical variational heuristics for combinatorial optimization
• Douglas-Rachford splitting and ADMM for nonconvex optimization: tight convergence results
• Multistart Methods for Quantum Approximate Optimization
• A Note on the Convergence of ADMM for Linearly Constrained Convex Optimization Problems
• Building an iterative heuristic solver for a quantum annealer
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances
• qTorch: The Quantum Tensor Contraction Handler
• Evaluating Quantum Approximate Optimization Algorithm: A Case Study
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Faster quantum and classical SDP approximations for quadratic binary optimization

Cited by in corpus (9)

• Quantum Computing for Finance: State of the Art and Future Prospects
• Challenges and Opportunities in Quantum Optimization
• Hybrid Quantum-Classical Unit Commitment
• Quantum computing through the lens of control: A tutorial introduction
• Quantum Computing for Software Engineering: Prospects
• Incentivising Demand Side Response through Discount Scheduling using Hybrid Quantum Optimization
• Improved full-waveform inversion for seismic data in the presence of noise based on the K-support norm
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Hybrid Quantum-Classical Multi-cut Benders Approach with a Power System Application