Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths

Abstract

We generalize the Quantum Approximate Optimization Algorithm (QAOA) of Farhi et al. (2014) to allow for arbitrary separable initial states with corresponding mixers such that the starting state is the most excited state of the mixing Hamiltonian. We demonstrate this version of QAOA, which we call QAOA-warmest, by simulating Max-Cut on weighted graphs. We initialize the starting state as a warm-start using $2$ and $3$-dimensional approximations obtained using randomized projections of solutions to Max-Cut's semi-definite program, and define a warm-start dependent custom mixer. We show that these warm-starts initialize the QAOA circuit with constant-factor approximations of $0.658$ for $2$-dimensional and $0.585$ for $3$-dimensional warm-starts for graphs with non-negative edge weights, improving upon previously known trivial (i.e., $0.5$ for standard initialization) worst-case bounds at $p=0$. These factors in fact lower bound the approximation achieved for Max-Cut at higher circuit depths, since we also show that QAOA-warmest with any separable initial state converges to Max-Cut under the adiabatic limit as $p\to \infty$. However, the choice of warm-starts significantly impacts the rate of convergence to Max-Cut, and we show empirically that our warm-starts achieve a faster convergence compared to existing approaches. Additionally, our numerical simulations show higher quality cuts compared to standard QAOA, the classical Goemans-Williamson algorithm, and a warm-started QAOA without custom mixers for an instance library of $1148$ graphs (upto $11$ nodes) and depth $p=8$. We further show that QAOA-warmest outperforms the standard QAOA of Farhi et al. in experiments on current IBM-Q and Quantinuum hardware.

References in corpus (14)

• Probabilistic error cancellation with sparse Pauli-Lindblad models on noisy quantum processors
• Warm-starting quantum optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• MAXCUT QAOA performance guarantees for p >1
• Hybrid quantum-classical algorithms for approximate graph coloring
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Computationally Efficient Zero Noise Extrapolation for Quantum Gate Error Mitigation
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Solving SDPs for synchronization and MaxCut problems via the Grothendieck inequality
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs

Cited by in corpus (22)

• Barren Plateaus in Variational Quantum Computing
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Engineered dissipation to mitigate barren plateaus
• Scaling Whole-Chip QAOA for Higher-Order Ising Spin Glass Models on Heavy-Hex Graphs
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Approximating under the Influence of Quantum Noise and Compute Power
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
• A Monte Carlo Tree Search approach to QAOA: finding a needle in the haystack
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• Approximate Quadratization of High-Order Hamiltonians for Combinatorial Quantum Optimization
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers