Approaches to Constrained Quantum Approximate Optimization

Abstract

We study the costs and benefits of different quantum approaches to finding approximate solutions of constrained combinatorial optimization problems with a focus on Maximum Independent Set. In the Lagrange multiplier approach we analyze the dependence of the output on graph density and circuit depth. The Quantum Alternating Ansatz Approach is then analyzed and we examine the dependence on different choices of initial states. The Quantum Alternating Ansatz Approach, although powerful, is expensive in terms of quantum resources. A new algorithm based on a "Dynamic Quantum Variational Ansatz" (DQVA) is proposed that dynamically changes to ensure the maximum utilization of a fixed allocation of quantum resources. Our analysis and the new proposed algorithm can also be generalized to other related constrained combinatorial optimization problems.

9 pages, 8 figures, corrected typos, added simulation results

References in corpus (15)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Quantum circuits with many photons on a programmable nanophotonic chip
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Warm-starting quantum optimization
• Sequential Generation of Matrix-Product States in Cavity QED
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Constrained mixers for the quantum approximate optimization algorithm
• Efficient quantum algorithm for preparing molecular-system-like states on a quantum computer
• The learnability of Pauli noise
• Hybrid quantum-classical optimization for financial index tracking
• Quantum Local Search with the Quantum Alternating Operator Ansatz
• The Largest Compatible Subset Problem for Phylogenetic Data

Cited by in corpus (6)

• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• Variational Quantum Multi-Objective Optimization
• Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems
• Q-CHOP: Quantum constrained Hamiltonian optimization