Source-linked AI summary
The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case
Edward Farhi, David Gamarnik, Sam Gutmann
TL;DR
The paper asks whether QAOA can find near-optimal independent sets in sparse random graphs despite its local circuit structure. It combines QAOA locality with the Overlap Gap Property and proves a shallow-depth barrier, while leaving higher-depth performance open.
Problem
The paper investigates whether QAOA can find large independent sets close to optimal in sparse random graphs of fixed average degree.
Method
The proof combines QAOA locality, distant-output independence, edge-influence bounds, and the Overlap Gap Property of nearly optimal independent sets.
Results
For 2p ≤ w log n / log(d / ln 2), with w < 1 and sufficiently large d, QAOA cannot produce an independent set larger than .854 times optimal.
Takeaways & Limitations
The result establishes a performance barrier for QAOA on typical sparse random-graph instances at depths below a d-dependent multiple of log n.
Takeaways & Limitations
The argument applies to random bounded-degree graphs and provides no indication of a limitation once p is large enough for QAOA to see the whole graph.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies QAOA for large independent sets in bounded-degree random graphs and uses graph locality with the Overlap Gap Property to establish a shallow-depth limitation. The bound applies to typical random instances, while fully connected settings fall outside the argument.
- QAOA measurements become uncorrelated for qubits separated by more than 2p graph distance when the graph has bounded degree.
- For 2p ≤ w log n / log(d / ln 2), with w < 1 and sufficiently large d, QAOA cannot produce an independent set larger than .854 times optimal.
- Unlike prior Max-Cut results for worst-case graphs, this result concerns typical random instances and does not require the cited Z2 symmetry conditions.
- The proof combines the Overlap Gap Property of nearly optimal independent sets with QAOA locality, making single-edge changes affect only o(n) final-state qubits.
- The locality-based obstruction does not apply to the fully connected Sherrington-Kirkpatrick model, where QAOA sees the whole graph at the lowest depths.
2 Maximum Independent Set
The paper frames Maximum Independent Set on sparse random graphs as a challenge of finding sets near the asymptotic optimum. It shows that shallow QAOA remains below a fixed fraction of that optimum, while larger-depth behavior is unresolved.
- Maximum Independent Set asks for a largest vertex subset containing no edge between any two selected vertices, and the arbitrary-graph problem is NP-hard.
- The studied graphs are sparse Erdős-Rényi graphs with fixed average degree d and dn/2 uniformly chosen edges.
- A greedy algorithm reaches asymptotically half the optimum, motivating the search for algorithms that provably perform better.
- For p < ϵ log n and sufficiently large d, QAOA fails to reach .854α_d.
- For larger p, the argument cannot determine whether QAOA approaches α_d, although sufficiently rapid growth eventually finds the optimum.
3 The Quantum Approximate Optimization Algorithm
QAOA prepares a parameterized quantum state by alternating graph-dependent cost and single-qubit driver unitaries, then samples computational-basis strings. The paper studies limits that hold regardless of parameter optimization.
- QAOA seeks a bit string whose classical cost function is close to its maximum by repeatedly measuring a parameterized quantum state.
- The cost unitary is local because its interactions occur only between qubits connected by edges of the instance graph.
- The driver unitary rotates individual qubits without affecting other qubits.
- The circuit initializes qubits in a product state and alternates p layers of cost and driver unitaries.
- The paper seeks parameter-independent impossibility results, so it does not need to optimize the QAOA parameters for each instance.
4 Locality Properties of the QAOA
QAOA locality implies independence between sufficiently distant measurements and limits how far a local graph change can influence output probabilities. These properties support concentration arguments for shallow circuits.
- On bounded-degree graphs, a depth-p QAOA circuit typically spreads a single-qubit operator to only about d^p qubits.
- For operators on qubit i and vertices at least 2p away, the product-state assumption yields factorized expectation values.
- Measurement outcomes at i and at graph distance at least 2p are therefore independent in the QAOA output state.
- Changing one graph edge affects probabilities only within distance p of that edge, leaving far-away bit-string probabilities unchanged.
- When 2p-neighborhoods contain fewer than n^A vertices for A < 1, distant-pair independence bounds Hamming-weight variance and produces concentration.
5 QAOA applied to Maximum Independent Set
This section formulates QAOA for Maximum Independent Set by combining a large-Hamming-weight objective with a local independent-set cost, then analyzes its shallowest depth on random graphs. The lowest-depth QAOA+ achieves an objective value approaching 1.02n/d, although simple classical algorithms can do better.
- Problem formulation: QAOA targets strings with large Hamming weight while using an edge-local cost function to penalize violations of independence.The objective combines Hamming weight with the independent-set cost, whose sum is only over graph edges.
- Problem formulation: Pruning any output string with positive objective value produces an independent set at least as large as that objective value.Randomly removing one endpoint from each edge among selected vertices reduces Hamming weight by at most the number of such edges.
- Shallow-depth analysis: At p = 1.5, setting γ = 0 gives an expected objective n[sin^2(θ + β) − (d/2)sin^4(θ + β)] with maximum 1/(2d).Allowing γ to vary can only improve this value.
- Shallow-depth analysis: For large d, numerical optimization gives an asymptotic optimum of 1.02 after extracting a factor 1/d and rescaling θ and β.The optimized objective approaches 1.02n/d.
- Conclusion: The lowest-depth QAOA+ finds an independent set whose size is at least a constant times n/d, but simple classical algorithms can outperform it.The analysis is presented as a starting point for understanding QAOA at higher depth.
6 The Overlap Gap Property
The Overlap Gap Property partitions pairs of large independent sets into low- or high-overlap regimes with essentially no intermediate overlap. The section establishes this structure across an interpolation between two random graphs and for pairs of independently sampled graphs.
- Definition and role: The Overlap Gap Property is the key structural property used to show a limitation of QAOA on random graphs.It applies to independent sets larger than a multiplicative threshold η* away from optimality.
- Definition and role: η-optimal independent sets are those whose size is at least η times the asymptotic optimum, and OAb and OBe classify pairs by normalized intersection above or below a threshold.The intersection is normalized by the asymptotic size of the largest independent set.
- Interpolating graphs: The interpolation G_t replaces edges of one random graph with edges of another, while each fixed G_t has the G(n, dn/2) distribution up to negligible edge repetitions.The total number of repetitions is O(1) with high probability.
- Overlap Gap Theorem: For every η > η*, suitable τ1 < τ2 exist such that, across interpolating graph pairs, η-optimal independent sets have normalized intersection at most τ1 or at least τ2, except with exponentially small probability.Thus there is essentially no middle ground between the two overlap regimes.
- Overlap Gap Theorem: For two independently sampled random graphs, all corresponding pairs of large independent sets have normalized intersection at most τ1.This is the second claim of the theorem for independent random graphs.
7 Overlap Gap Property is an obstruction to the QAOA+
The paper combines the Overlap Gap Property with QAOA+ locality and neighborhood-size bounds to show an obstruction below logarithmic circuit depth. A coupled interpolation argument then contradicts the OGP when successive outputs can change only locally.
- Main Result: QAOA+ fails to find independent sets close to optimal when p is below a constant times log n.The result concerns random graphs of average degree d and QAOA augmented by pruning.
- Preliminary Results: For p below a suitable constant times log n, every vertex neighborhood contains a vanishing fraction of the graph's vertices with high probability.This neighborhood bound supplies the locality scale needed by the obstruction argument.
- Preliminary Results: Changing one graph edge leaves the total probability of independent sets agreeing far from that edge unchanged.The statement extends the purely quantum locality result to QAOA+ because the pruning process also respects graph locality.
- Proof of Obstruction Theorem: The proof interpolates between graphs and couples their QAOA+ outputs so consecutive independent sets differ only within bounded neighborhoods.The resulting change is bounded by 4D, where D is the largest relevant neighborhood size along the interpolation.
- Proof of Obstruction Theorem: The coupled sequence must cross from large to small overlap, but the OGP forbids a middle ground; the local-change bound yields a contradiction for large n.The contradiction establishes the obstruction theorem.
8 Proofs of Neighborhood Size and Concentration Results
The proofs establish that shallow QAOA+ on random bounded-degree graphs has small neighborhoods and concentrated output Hamming weight. They combine branching-process bounds, locality, moment methods, and Azuma-style concentration.
- Neighborhood Size Theorem: For fixed d > 1 and w < 1, suitable constants a > 0 and A < 1 bound the maximum 2p-neighborhood when 2p is logarithmic in n.The theorem applies under the displayed depth condition and uses a union bound over vertices.
- Neighborhood Size Theorem: A branching process with Poisson(d) offspring bounds random-graph neighborhood sizes through comparisons with Erdős–Rényi graphs and fixed-edge random graphs.The proof transfers moment-generating-function bounds from the branching process to graph neighborhoods.
- Concentration Theorem: For fixed graphs, locality makes one-edge changes affect only nearby output bits, so an adjusted function permits Azuma concentration despite exceptional large-neighborhood graphs.The argument handles graphs outside the small-neighborhood set using a modification that agrees with the original function on the good set.
- Concentration Theorem: For random graphs, the combined graph and QAOA+ randomness also yields exponential concentration bounds for the Hamming weight.The second concentration statement treats graph randomness together with algorithmic randomness.
- Concentration Theorem: The QAOA+ output weight is a sum of locally dependent Bernoulli variables, enabling sub-exponential concentration when 2p-neighborhoods are small compared with n.Moment-generating functions control the dependence created by overlapping neighborhoods.
- Concentration Theorem: Only products whose indices have partners within graph distance 2p contribute nonzero terms, and valid dependency graphs decompose into star components.This structure bounds the number of terms needed in the moment calculation.
9 Discussion
The discussion frames the work as a search for provable quantum-algorithm limitations and applies it to maximum independent set on fixed-degree random graphs. The locality-based barrier is logarithmic in n, while the argument does not constrain sufficiently deep circuits.
- Discussion: Provable limitations of quantum algorithms provide an alternative to experimentally testing whether quantum computation outperforms classical methods on combinatorial search.The paper studies such a limitation for QAOA rather than establishing a quantum speedup.
- Discussion: For maximum independent set on fixed-average-degree random graphs, QAOA cannot pass a performance barrier when 2p < w log n / log(d/ln 2), for any w < 1 with d sufficiently large.The bound concerns the algorithm’s depth and the graph size, with d fixed.
- Discussion: The proof relies on locality: qubits farther than distance 2p have uncorrelated measurements, while each qubit’s influence sphere contains roughly d^p other qubits.When p is large enough that d^p exceeds n, the paper’s argument no longer applies.
- Discussion: At d = 3 and one million qubits, the result suggests failure for p less than 7, whereas at double-digit p the paper cannot determine performance.The discussion emphasizes that the logarithmic depth boundary grows slowly with n.