Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
arXiv:2503.20048 · doi:10.1103/nt3w-j4mj
Abstract
In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with to qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the -qubit case even in level 1 can only be matched by the GW algorithm after about random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.
arXiv comment17 pages, 7 figures
References in corpus (36)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- A variational eigenvalue solver on a quantum processor
- Variational Quantum Algorithms
- Ising formulations of many NP problems
- The theory of variational hybrid quantum-classical algorithms
- Noisy intermediate-scale quantum (NISQ) algorithms
- Strong quantum computational advantage using a superconducting quantum processor
- Suppressing quantum errors by scaling a surface code logical qubit
- Logical quantum processor based on reconfigurable atom arrays
- Quantum error correction below the surface code threshold
- How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Training variational quantum algorithms is NP-hard
- Real-time quantum error correction beyond break-even
- A Review on Quantum Approximate Optimization Algorithm and its Variants
- Obstacles to State Preparation and Variational Optimization from Symmetry Protection
- Warm-starting quantum optimization
- Improving Variational Quantum Optimization using CVaR
- Challenges and Opportunities in Quantum Optimization
- Quantum annealing initialization of the quantum approximate optimization algorithm
- Reachability Deficits in Quantum Approximate Optimization
- Encoding a magic state with beyond break-even fidelity
- Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory
- MAXCUT QAOA performance guarantees for p >1
- Classical variational simulation of the Quantum Approximate Optimization Algorithm
- Quantum annealing with longitudinal bias fields
- Quantum optimization via four-body Rydberg gates
- Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
- Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
- Quantum Computational Phase Transition in Combinatorial Problems
- Mitigating algorithmic errors in quantum optimization through energy extrapolation
- Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm