PaperlayerView exact revision on arXiv

Source-linked AI summary

Classical algorithms and quantum limitations for maximum cut on high-girth graphs

Boaz Barak, Kunal Marwaha

arXiv:2106.05900v1quant-phcs.DS

TL;DR

The paper asks whether local quantum algorithms can outperform polynomial-time classical algorithms for graph optimization, focusing on maximum cut. It develops classical and quantum locality results and studies whether classical algorithms may match or dominate local quantum methods across instances.

  • Problem

    Whether local quantum algorithms can achieve better maximum-cut results than polynomial-time classical algorithms on some graph instances remains open.

    Source: §1 · p. 2, §1.1 · p. 3

  • Method

    The paper analyzes local quantum and classical algorithms for maximum cut, formalizes local distributions, proves results on regular high-girth graphs, and compares methods computationally on additional graph families.

    Source: §1.1 · pp. 3–5, §1.3 · p. 7, §2.1 · p. 9

  • Results

    The paper proves upper bounds for one-local algorithms, constructs a classical k-local algorithm for high-girth graphs, and reports experiments comparing ALR with QAOA beyond the high-girth setting.

    Source: §1.1 · p. 5, §3 · p. 12, §4 · p. 16

  • Takeaways & Limitations

    The results support the possibility that polynomial-time classical algorithms could pointwise dominate constant-locality quantum maximum-cut algorithms, while leaving the general question open.

    Source: §1.1 · p. 3, §4 · p. 15

    The paper suspects its classical algorithm is not optimal and notes that its results do not rule out a classical algorithm matching or beating constant-locality QAOA on every graph.

    Source: §3 · p. 15, §4 · p. 15

Abstract

from arXiv · show

We study the performance of local quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) for the maximum cut problem, and their relationship to that of classical algorithms. (1) We prove that every (quantum or classical) one-local algorithm achieves on $D$-regular graphs of girth $> 5$ a maximum cut of at most $1/2 + C/\sqrt{D}$ for $C=1/\sqrt{2} \approx 0.7071$. This is the first such result showing that one-local algorithms achieve a value bounded away from the true optimum for random graphs, which is $1/2 + P_*/\sqrt{D} + o(1/\sqrt{D})$ for $P_* \approx 0.7632$. (2) We show that there is a classical $k$-local algorithm that achieves a value of $1/2 + C/\sqrt{D} - O(1/\sqrt{k})$ for $D$-regular graphs of girth $> 2k+1$, where $C = 2/\pi \approx 0.6366$. This is an algorithmic version of the existential bound of Lyons and is related to the algorithm of Aizenman, Lebowitz, and Ruelle (ALR) for the Sherrington-Kirkpatrick model. This bound is better than that achieved by the one-local and two-local versions of QAOA on high-girth graphs. (3) Through computational experiments, we give evidence that the ALR algorithm achieves better performance than constant-locality QAOA for random $D$-regular graphs, as well as other natural instances, including graphs that do have short cycles. Our experimental work suggests that it could be possible to extend beyond our theoretical constraints. This points at the tantalizing possibility that $O(1)$-local quantum maximum-cut algorithms might be *pointwise dominated* by polynomial-time classical algorithms, in the sense that there is a classical algorithm outputting cuts of equal or better quality *on every possible instance*. This is in contrast to the evidence that polynomial-time algorithms cannot simulate the probability distributions induced by local quantum algorithms.

1 Introduction

This section examines whether local quantum algorithms can outperform polynomial-time classical algorithms for maximum cut, focusing on regular high-girth graphs and broader graph families through theoretical and experimental analysis. It frames these results within the question of NISQ optimization advantage for constraint satisfaction problems.

1 Introduction

  • QAOA is a p-local maximum-cut algorithm whose output at each vertex depends only on vertices within distance p, making constant p relevant to implementable noisy intermediate-scale quantum devices.The introduction notes that QAOA3 maximized performance in cited near-term experiments because larger p allowed noise to overwhelm the signal.Source: §1 · p. 2

1.1 Our results

  • The central open question is whether polynomial-time classical algorithms pointwise dominate every O(1)-local quantum maximum-cut algorithm, meaning they match or exceed its value on every graph up to ε.The paper proves progress only for the exponentially large family of sufficiently high-girth regular graphs, not for every instance.Source: §1.1 · p. 3
  • A polynomial-time classical algorithm achieves 1/2 + (2/π)/√D − O(1/√k) on D-regular graphs of girth greater than 2k+1, with 2/π ≈ 0.6366.The construction is an algorithmic version of Lyons (2017)’s existential bound and is related to the Aizenman–Lebowitz–Ruelle algorithm for the Sherrington–Kirkpatrick model.Source: §1.1 · p. 4
  • Experiments indicate that the ALR algorithm outperforms constant-locality QAOA on random 3-regular, torus, and grid graphs, including instances with short cycles.The experiments extend beyond the high-girth restrictions of the theorems and suggest possible pointwise domination by polynomial-time classical algorithms.Source: §1.1 · p. 5

1.2 Related works

  • Theoretical work had bounded QAOA1 at C = 1/(2·√e) ≈ 0.3033 and QAOA2 at C < 0.41 on high-girth graphs, with classical local algorithms numerically dominating both.Related work also established worst-case graph families where constant-p QAOA performs poorly, while this paper emphasizes per-instance quantum–classical comparisons.Source: §1.2 · pp. 5–6

1.3 Discussion: NISQ optimization advantage

  • Under the paper’s best-case NISQ formulation, an optimization advantage requires an O(1)-local quantum algorithm to beat every polynomial-time classical algorithm by ε on some instance; Theorem 2 strongly limits this for high-girth maximum cut.The formulation models fixed-topology, noisy, constant-depth devices as a quantum analogue of the LOCAL model, with the device and input graph identified in the best-case setting.Source: §1.3 · pp. 7–8
  • Figure 2 illustrates the question of “NISQ optimization advantage” for general CSPs.Source: §1.3 · p. 8

2 Classical and quantum one-local algorithms are suboptimal

The section formalizes why centered one-local algorithms cannot reach the best known high-girth maximum-cut values, using local output distributions and correlation arguments. It also identifies the assumptions and proof structure behind the one-local upper bound.

2.1 Local distributions

  • A centered r-local distribution makes outputs on sets with disjoint radius-r neighborhoods independent, while centeredness means every output coordinate has zero expectation.Centeredness captures the cut symmetry and excludes fixed-cut pathological algorithms.Source: §2.1 · p. 9
  • One-local algorithms induce one-local output distributions, so bounding such distributions suffices for a negative result even though the converse equivalence does not hold.Local classical outputs are more restricted than local quantum outputs, but the broader distributional class is enough for the upper bound.Source: §2 · pp. 8–9, §2.1 · p. 9

2 Classical and quantum one-local algorithms are suboptimal

  • For every centered one-local distribution over cuts on a D-regular graph of girth at least 6, the expected cut value is at most 1.Source: §2.1 · p. 9, §2 · p. 9

2.2 Proof of Theorem 3

  • The proof converts one-locality and girth into vanishing long-range correlations and constrains edge correlations through short random walks.The argument uses tree-like walks in girth-at-least-six graphs, conditional correlations, and averaging over vertices and signs.Source: §2.2 · pp. 10–11
  • The correlation constraints are translated into a spectral inequality for powers of the random-walk matrix, which yields the maximum-cut upper bound.The proof relates random-walk expectations to quadratic forms and combines the resulting claims to obtain the cut-value bound.Source: §2.2 · p. 11

3 A classical algorithm for maximum cut on high-girth graphs

The paper gives a polynomial-time k-local classical algorithm for high-girth D-regular graphs, with performance approaching the Lyons bound as k increases. The construction is related to the ALR algorithm and is analyzed through tree-like neighborhoods and Gaussian sums.

The classical algorithm

  • 1/2 + 2/(π√D) - O(1/√k) is achieved by a k-local algorithm on D-regular graphs of girth greater than 2k + 1.This is an algorithmic version of Lyons’s existential bound.Source: §3 · pp. 11–12
  • The algorithm assigns independent standard Gaussian values to vertices and outputs signs computed from weighted radius-k neighborhoods.Its locality follows because each output depends only on vertices within distance k.Source: §3 · p. 12

Analysis

  • High girth makes each edge neighborhood tree-like, allowing the cut probability to be analyzed using independent Gaussian contributions from the two endpoint sides.The girth condition excludes relevant shortcuts within the radius-k analysis.Source: §3 · pp. 12–13
  • Ignoring the terminal Gaussian terms changes the relevant sign decisions on only an O(1/√k) fraction of edges.This controls the finite-locality loss in the algorithm’s guarantee.Source: §3 · p. 13

Relation to ALR

  • The construction approaches the ALR algorithm: it can be viewed as a truncated power-method computation using the graph adjacency matrix and a Gaussian vector.The two algorithms are similar but not identical because the finite-k construction includes back-edge walks.Source: §3 · p. 13

Limitations and open direction

  • The authors suspect a better polynomial-time classical algorithm may achieve 1/2 + P*/√D on sufficiently high-girth D-regular graphs.They note that the presented ALR-related algorithm is not believed to be optimal.Source: §3 · p. 15

4 Beyond one-locality and high girth: some computational experiments

Computational experiments compare ALR with QAOA beyond the theorem’s one-locality and high-girth setting. They suggest that ALR often dominates constant-locality QAOA as graph size exceeds QAOA depth, including graphs with short cycles.

Limits of ALR

  • Theorem 5 shows that for some infinite graph sequence, fixed-p QAOA beats both ALR and the Goemans–Williamson algorithm by a positive constant.Thus ALR is not pointwise dominant by itself.Source: §4 · p. 15

Random regular graphs

  • For 100 random unweighted 3-regular graphs at each n ∈ {8, 10, 12, 14, 16}, QAOA’s relative performance deteriorates as n grows relative to depth p.The results suggest that for QAOAp to beat classical algorithms, p must grow with n.Source: §4 · p. 15

Interpretation

  • The experiments support the possibility that QAOA depth must grow with n to surpass classical algorithms on some maximum-cut instances.The authors state that further investigation is needed to determine whether constant-depth QAOA can surpass all polynomial-time classical algorithms.Source: §4 · pp. 15–16

Graphs with short cycles

  • On 4×4 grids and even-side toruses, ALR finds the perfect cut of value 1, while QAOAp remains bounded away from 1 when p ≪ n.These graphs are bipartite and contain short cycles, so the comparison tests the girth restriction.Source: §4 · p. 16
  • The authors obtained similar results when they added small cycles by superimposing a 16-vertex random 3-regular graph on the 4 × 4 torus; see Figure 6.Source: §4 · p. 16

5 Conclusions

The paper argues that restricted depth and locality may limit quantum advantage for optimization on every instance, but emphasizes that its theoretical results remain narrow. It identifies stronger classical bounds, broader local-algorithm lower bounds, and non-constant QAOA depth as open directions.

Conclusions

  • The results suggest that restricted quantum depth and locality may be incompatible with quantum advantage for maximum cut on every instance.This is presented as a possibility rather than an established general theorem.Source: §5 · p. 16
  • The theoretical results are limited because the classical analysis assumes high girth while the negative quantum result is established only for one-local algorithms.The paper highlights improving the classical bound and extending negative results to k-local algorithms as immediate goals.Source: §5 · p. 16

Open questions

  • Open directions include algorithms beyond maximum cut, classical competitors for broader local quantum algorithms, and QAOAp with slowly growing p such as O(log n).The sum-of-squares algorithm is named as one possible classical candidate.Source: §5 · p. 16

A Local algorithms induce local distributions

The paper formalizes locality for classical and quantum maximum-cut algorithms through the locality of their output distributions. For quantum circuits, this follows from finite light cones; for classical algorithms, it follows from independent local randomness.

Classical algorithms

  • Every r-local classical algorithm induces an r-local output distribution.Each vertex uses an independent random label and computes its output from a labeled radius-r neighborhood.Source: A Local algorithms induce local… · p. 20

Quantum model

  • The quantum model uses product-state qudits, local single-qudit gates, commuting neighboring two-qudit gates, and a binary partition of measured outcomes.QAOA is a p-local instance of this model.Source: A Local algorithms induce local… · p. 20

Quantum algorithms

  • Every r-local quantum algorithm also induces an r-local output distribution.The theorem applies to the cut produced after measuring the local quantum circuit.Source: A Local algorithms induce local… · pp. 20–21
  • Quantum locality is proved by propagating measurement operators backward through circuit layers, restricting each output to its radius-r light cone.Outputs at vertices with disjoint light cones are independent.Source: A Local algorithms induce local… · p. 21

Centered distributions

  • Centeredness is an additional assumption because otherwise a 0-local algorithm could output a fixed optimal cut for a particular graph.The assumption requires equal probabilities for +1 and −1 at each vertex.Source: A Local algorithms induce local… · p. 21
Loading 2106.05900v1…