Elementary Proof of QAOA Convergence
arXiv:2302.04968 · doi:10.1088/1367-2630/ad59bb
Abstract
The Quantum Alternating Operator Ansatz (QAOA) and its predecessor, the Quantum Approximate Optimization Algorithm, are one of the most widely used quantum algorithms for solving combinatorial optimization problems. However, as there is yet no rigorous proof of convergence for the QAOA, we provide one in this paper. The proof involves retracing the connection between the Quantum Adiabatic Algorithm and the QAOA, and naturally suggests a refined definition of the `phase separator' and `mixer' keywords.
arXiv comment10 pages, 2 figures
References in corpus (10)
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Quantum Search by Local Adiabatic Evolution
- Quantum Computation by Adiabatic Evolution
- Perspectives of quantum annealing: Methods and implementations
- Mathematical Foundation of Quantum Annealing
- Adiabatic Theorem without a Gap Condition
- Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study
- Knapsack Problem variants of QAOA for battery revenue optimisation
Cited by in corpus (6)
- A quantum algorithm for solving 0-1 Knapsack problems
- Noise-aware variational eigensolvers: a dissipative route for lattice gauge theories
- Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
- Constraint-Aware Quantum Optimization via Hamming Weight Operators
- Symmetry-based quantum algorithms for open-shop scheduling with hard constraints
- Quantum tree generator improves QAOA state-of-the-art for the knapsack problem