The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case

Abstract

The Quantum Approximate Optimization Algorithm can naturally be applied to combinatorial search problems on graphs. The quantum circuit has p applications of a unitary operator that respects the locality of the graph. On a graph with bounded degree, with p small enough, measurements of distant qubits in the state output by the QAOA give uncorrelated results. We focus on finding big independent sets in random graphs with dn/2 edges keeping d fixed and n large. Using the Overlap Gap Property of almost optimal independent sets in random graphs, and the locality of the QAOA, we are able to show that if p is less than a d-dependent constant times log n, the QAOA cannot do better than finding an independent set of size .854 times the optimal for d large. Because the logarithm is slowly growing, even at one million qubits we can only show that the algorithm is blocked if p is in single digits. At higher p the algorithm "sees" the whole graph and we have no indication that performance is limited.

19 pages, no figures

References in corpus (6)

• A Quantum Approximate Optimization Algorithm
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Suboptimality of local algorithms for a class of max-cut problems
• For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances

Cited by in corpus (35)

• Noisy intermediate-scale quantum (NISQ) algorithms
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Differentiable Quantum Architecture Search
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Neural Predictor based Quantum Architecture Search
• Fast quantum circuit cutting with randomized measurements
• NISQ Computers: A Path to Quantum Supremacy
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Prospects and challenges of quantum finance
• Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
• Constrained Optimization via Quantum Zeno Dynamics
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• Exploiting Symmetry Reduces the Cost of Training QAOA
• Evaluation of QAOA based on the approximation ratio of individual samples
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• 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
• Error Mitigation for Deep Quantum Optimization Circuits by Leveraging Problem Symmetries
• Bounds on approximating Max $k$XOR with quantum and classical local algorithms
• Approaches to Constrained Quantum Approximate Optimization
• Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization
• HamLib: A library of Hamiltonians for benchmarking quantum algorithms and hardware
• Networked Quantum Services
• Quantum Local Search with the Quantum Alternating Operator Ansatz
• High-Round QAOA for MAX $k$-SAT on Trapped Ion NISQ Devices
• Classical algorithms and quantum limitations for maximum cut on high-girth graphs
• Quantum mean value approximator for hard integer value problems
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Limits of Short-Time Evolution of Local Hamiltonians
• The Overlap Gap Property limits limit swapping in the QAOA
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Improving the Quantum Approximate Optimization Algorithm with postselection
• Enhanced Framework of Quantum Approximate Optimization Algorithm and Its Parameter Setting Strategy