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.

arXiv comment9 pages, 8 figures, corrected typos, added simulation results

References in corpus (29)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
• Building logical qubits in a superconducting quantum computing system
• Quantum circuits with many photons on a programmable nanophotonic chip
• Benchmarking an 11-qubit quantum computer
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Warm-starting quantum optimization
• $XY$-mixers: analytical and numerical results for QAOA
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• 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
• Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
• How many qubits are needed for quantum computational supremacy?
• 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
• Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
• Quantum Algorithms for Scientific Computing and Approximate Optimization
• 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 (7)

• Quantum Circuit Cutting with Maximum Likelihood Tomography
• 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