Missing Puzzle Pieces in the Performance Landscape of the Quantum Approximate Optimization Algorithm

Abstract

We consider the maximum cut and maximum independent set problems on random regular graphs in the infinite-size limit, and calculate the energy densities achieved by QAOA for high degrees up to $d=100$. Such an analysis is possible because the reverse causal cones of the operators in the Hamiltonian are with high probability associated with tree subgraphs, for which efficient classical contraction schemes can be developed. We combine the QAOA analysis with state-of-the-art upper bounds on optimality for both problems. This yields novel and better bounds on the approximation ratios achieved by QAOA for large problem sizes. We show that the approximation ratios achieved by QAOA improve as the graph degree increases for the maximum cut problem. However, QAOA exhibits the opposite behavior for the maximum independent set problem, i.e. the achieved approximation ratios decrease when the degree of the problem is increased. This phenomenon is explainable by the overlap gap property for large $d$, which restricts local algorithms (like QAOA) from reaching near-optimal solutions with high probability. In addition, we use the QAOA parameters determined on the tree subgraphs for small graph instances, and in that way outperform classical algorithms like Goemans-Williamson for the maximum cut problem and minimal greedy for the maximum independent set problem. In this way we circumvent the parameter optimization problem and are able to compute the expected approximation ratios.

35 pages, 13 figures

References in corpus (36)

• Quantum Computing in the NISQ era and beyond
• Quantum algorithm for solving linear systems of equations
• Quantum Simulation
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• A rigorous and robust quantum speed-up in supervised machine learning
• Training variational quantum algorithms is NP-hard
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Information-theoretic bounds on quantum advantage in machine learning
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Clustering of solutions in the random satisfiability problem
• Challenges and Opportunities in Quantum Optimization
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Extremal Cuts of Sparse Random Graphs
• MAXCUT QAOA performance guarantees for p >1
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Local algorithms for independent sets are half-optimal
• On the Quantum versus Classical Learnability of Discrete Distributions
• Suboptimality of local algorithms for a class of max-cut problems
• On independent sets in random graphs
• Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs
• Warm-Started QAOA with Custom Mixers Provably Converges and Computationally Beats Goemans-Williamson's Max-Cut at Low Circuit Depths
• Quantum-Informed Recursive Optimization Algorithms
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Conjecture on the maximum cut and bisection width in random regular graphs
• Reinforcement Learning Assisted Recursive QAOA
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• The SK model is infinite step replica symmetry breaking at zero temperature
• The Overlap Gap Property limits limit swapping in the QAOA
• Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming