MAXCUT QAOA performance guarantees for p >1

Abstract

We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. Previous work by Farhi et al obtained a lower bound on the approximation ratio of $0.692$ for $p=1$. We find a lower bound of $0.7559$ for $p=2$, where worst case graphs are those with no cycles $\le 5$. This bound holds for any 3 regular graph evaluated at particular fixed parameters. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $\le 2p+1$. Under this conjecture, the approximation ratio is at least $0.7924$ for all 3 regular graphs and $p=3$. In addition, using a simple indistinguishability argument we find an upper bound on the worst case approximation ratio for all $p$, which indicates classes of graphs for which there can be no quantum advantage for at least $p<6$.

17 pages, 13 figures

References in corpus (1)

• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples

Cited by in corpus (57)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Challenges and Opportunities in Quantum Optimization
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Counterdiabaticity and the quantum approximate optimization algorithm
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Towards large-scale quantum optimization solvers with few qubits
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Scaling Quantum Approximate Optimization on Near-term Hardware
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Analytical Framework for Quantum Alternating Operator Ansätze
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• Provable bounds for noise-free expectation values computed from noisy samples
• Recursive greedy initialization of the quantum approximate optimization algorithm with guaranteed improvement
• Quantum Approximate Multi-Objective Optimization
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Parity Quantum Optimization: Benchmarks
• Variational quantum algorithms for Poisson equations based on the decomposition of sparse Hamiltonians
• Fair Sampling Error Analysis on NISQ Devices
• Optimizing Quantum Algorithms on Bipotent Architectures
• Performance Analysis of Multi-Angle QAOA for p > 1
• Characterizing Error Mitigation by Symmetry Verification in QAOA
• Low-depth Clifford circuits approximately solve MaxCut
• Performance of Quantum Approximate Optimization with Quantum Error Detection
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Amplitude amplification-inspired QAOA: Improving the success probability for solving 3SAT
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer
• Quantum computing for genomics: conceptual challenges and practical perspectives
• Quantum approximate optimization algorithm with random and subgraph phase operators
• Compressed space quantum approximate optimization algorithm for constrained combinatorial optimization
• Twisted hybrid algorithms for combinatorial optimization
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Optimization via Quantum Preconditioning
• On the Effects of Small Graph Perturbations in the MaxCut Problem by QAOA
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization
• Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm
• Optimisation-Free Recursive QAOA for the Binary Paint Shop Problem
• Efficient Online Quantum Circuit Learning with No Upfront Training
• Lower bounds on the number of rounds of the quantum approximate optimization algorithm required for guaranteed approximation ratios
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Hidden local adiabatic ramp in the modulated time evolution and the quantum approximate optimization algorithm
• Qubit-efficient quantum combinatorial optimization solver
• Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
• Direct Gradient Computation for Barren Plateaus in Parameterized Quantum Circuits
• Variational Quantum Algorithm for Constrained Combinatorial Optimization Problems