PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Classical and Quantum Local Algorithms for Max-$k$-Cut and Quantum Advantage at Moderate Girth

Anuj Apte, Abid Khan, Edward Farhi, Kunal Marwaha, Sami Boulebnane, Ruslan Shaydulin

arXiv:2609.39042v1quant-phcs.DSmath.OC

TL;DR

Max-k-Cut research asks whether quantum optimization can achieve better provable performance than classical algorithms under matched graph assumptions. This paper develops a local classical algorithm and tools to analyze QAOA on regular graphs. The comparison finds a regime where QAOA overtakes the classical algorithm, while leaving the gap to the optimum as an open question.

  • Problem

    The paper asks whether QAOA can outperform the best provable classical local algorithm for Max-k-Cut on the same regular, locally tree-like graphs.

    Source: §1 · pp. 1–2, §5 · p. 27

  • Method

    The paper generalizes the TPM Local Vector algorithm and analyzes QAOA using qudit tree tensor networks and an infinite-degree qudit–boson reformulation.

    Source: §4.2 · p. 18, §5 · p. 27, §6 · p. 29

  • Results

    At shallow depth p = 1 the Local Vector algorithm is ahead of or tied with QAOA for every k, while QAOA overtakes it once the girth is large enough.

    Source: §6 · p. 30

  • Takeaways & Limitations

    The paper identifies a regime of quantum advantage for graph optimization at moderate girth despite improving the classical guarantee.

    Source: §6 · pp. 29–30

    The paper leaves open how far the Local Vector algorithm and QAOA fall below the optimal cut fraction.

    Source: §6 · p. 30

Abstract

from arXiv · show

Broadening the study of quantum optimization algorithms from binary to $k$-element alphabets has been shown to open new avenues for potential quantum advantage. A quantum advantage claim for approximate optimization requires showing that, under the same assumptions, an efficient quantum algorithm provably achieves a better performance than can be proven for the best known efficient classical algorithms. We study local classical and quantum algorithms for Max-$k$-Cut on $d$-regular graphs of girth $g$. We advance classical algorithms for this problem by developing a local vector algorithm based on the explicit vector construction of Thompson, Parekh, and Marwaha (TPM). Our algorithm gives the best provable cut fraction guarantee among known efficient classical algorithms on regular graphs for $k\geq3$. To evaluate the performance of QAOA under identical assumptions of girth and regularity, we develop tensor network techniques for general $d$ and $k \geq 2$. In addition, using an equivalence to a coupled qudit--boson system, we compute the QAOA performance in the infinite-degree limit. Together, these techniques give provable guarantees on QAOA performance on large graphs. Despite the improvements we introduce to the classical algorithm, QAOA achieves a better cut fraction guarantee for depths $p\geq 9$, corresponding to girth $g\geq 20$, for both finite- and infinite-degree regimes. Thus, we obtain an apparent quantum advantage from applying QAOA to the Max-$k$-Cut problem.

1 Introduction

The paper asks whether local quantum algorithms can outperform classical ones under the same regularity and girth assumptions, extending that comparison from Max-Cut to Max-k-Cut. It develops a stronger classical guarantee and methods for evaluating QAOA, then identifies a girth regime where QAOA overtakes the classical algorithm.

1 Introduction

  • The analysis compares provable guarantees for local classical and quantum algorithms, rather than benchmarking empirical heuristic performance.The comparison adopts the same assumptions about graph structure for both algorithms.Source: §1 · pp. 2–3

1.1 Results

  • The generalized TPM Local Vector algorithm exceeds the random baseline on regular graphs with girth g ≥ 4.Its improvement is asymptotically Θ(1/d) as d grows.Source: §1.1 · p. 3
  • For k ≥ 3, one-step neighbor-message rounding gives the best known provable cut-fraction guarantee among efficient classical algorithms on regular graphs.The improvement is additive and applies where the Frieze–Jerrum guarantee is vacuous.Source: §1.1 · p. 3
  • For p ≥ 9, corresponding to g ≥ 20, QAOA overtakes the Local Vector algorithm in the head-to-head comparison.The comparison uses the same regular, locally tree-like graph assumptions for both algorithms.Source: §1.1 · p. 3
  • The paper generalizes tree tensor-network contraction to k-level qudits and uses a qudit–boson reformulation to analyze QAOA at infinite degree.The contraction cost is O(p k^2(p+1)) in time and O(k^2p) in memory, independent of d.Source: §1.1 · p. 3

2 Preliminaries

The preliminaries define Max-k-Cut and the cut-fraction benchmark, then explain how regular-graph structure motivates explicit vectors and girth-aware analysis. They also describe why a worst-case SDP approximation guarantee can fall below the random cut-fraction baseline, motivating the paper’s explicit algorithm.

2.1 The Max-k-Cut Problem

  • Max-k-Cut partitions vertices into k subsets to maximize edges crossing between subsets; a uniformly random labeling cuts an expected fraction (k − 1)/k.The paper distinguishes this cut fraction from an approximation ratio relative to the optimum.Source: §2.1 · p. 4
  • Girth g = 2m for the vector algorithm and g = 2p + 2 for depth-p QAOA makes the corresponding edge neighborhoods tree-like.This structure simplifies analysis of both algorithms.Source: §2.1 · p. 5

2.2 Semidefinite Programming Relaxation

  • The Frieze–Jerrum SDP assigns vectors to vertices and rounds them with random directions, but its approximation-ratio guarantee does not by itself ensure a cut fraction above random.The cut-fraction consequence depends on the graph’s optimum cut fraction.Source: §2.2 · pp. 5–6
  • The Frieze–Jerrum certified cut fraction can be strictly below the random baseline, while the explicit vector algorithm is designed to beat that baseline in this regime.The proposition concerns the guarantee, not the realized performance of an individual SDP solution.Source: §2.2 · pp. 6–7
  • The explicit vector algorithm guarantees cut fraction (k − 1)/k + Θ(1/d) on d-regular graphs with girth g ≥ 2m using an m × m minimum-eigenvector computation.That computation is independent of graph size, unlike the stated O(n^3.5) interior-point SDP solve.Source: §2.2 · p. 7

3 Local Vector Algorithm for Max-k-Cut

This section develops and analyzes a local vector algorithm for Max-k-Cut that assigns distance-based vectors and rounds them using Gaussian scores, optionally incorporating neighbor messages. The algorithm improves on the random cut fraction, and the neighbor-message rule improves the leading large-degree coefficient over generalized Thompson–Parekh–Marwaha rounding, strictly for k ≥ 3.

3.1 Vector Assignment

  • For girth g ≥2m, the algorithm assigns unit vectors whose coordinates depend only on distance, choosing coefficients via a minimum-eigenvalue problem that minimizes adjacent-vector correlation.The local tree structure makes the edge correlation common across edges and the eigenvalue problem independent of graph size.Source: §3 · pp. 7–8, §3.1 · pp. 8–9

3.2 Rounding

  • Root-only Gaussian argmax has same-label probability determined by edge correlation σ; one round of neighbor messages can move the leading 1/d term using neighbors’ score gaps, with τ = 0 recovering root-only rounding.Source: §3.2 · pp. 10–11

3.3 The Full Algorithm

  • Algorithm 1 uses neighbor-message rounding when g ≥6 and falls back to root-only rounding when g <6; its cut probability depends only on (d, m, k, τ) under g ≥max(2m, 6).It constructs the distance-shell vectors, samples k independent Gaussian directions, and rounds vertex scores.Source: §3.3 · pp. 11–12

3.4 Analyzing the Cut Fraction

  • For τ > 0, a central limit theorem yields a Gaussian limit for the collective field of each endpoint’s many neighbor messages, enabling analysis of the leading cut-fraction coefficient.The normalized message sums have bounded-variance terms with pairwise correlations O(1/d); the CLT applies to the collective field, not to an individual message.Source: §3.4 · pp. 13–15
  • The root-only rule exceeds the random baseline (k −1)/k by Θ(1/d) on every d-regular graph with girth g ≥2m, with coefficient αkcm.The coefficient combines a girth factor cm from the vector construction and a label-dependent rounding constant αk.Source: §3.4 · p. 13, Table 1 · p. 14
  • For k ≥2, m ≥2, and girth g ≥ max(2m, 6), fixed-τ Local Vector rounding improves expected cut fraction over (k−1)/k by Θ(1/√d) for sufficiently small τ.The coefficient C_m,k(τ) is continuous near zero and C_m,k(0) = α_k c_m > 0.Source: §3.4 · pp. 15–16
  • For τ=0, the exact finite-degree cut fraction is available; for τ>0, it is evaluated by a Gaussian integral over the one-step edge neighborhood using exact overlaps ρ_L(d,m).The numerical check tests the large-degree asymptotics for k=2, 3, 4 and m=3, 5 across degrees 10^2–10^4, with agreement within about 0.01.Source: §3.4 · p. 16, Figure 5 · p. 16
  • For every k ≥2 with g ≥6, the neighbor-message rule strictly improves the leading 1/√d coefficient over generalized Thompson–Parekh–Marwaha rounding by up to roughly 0.10 in absolute terms.The optimal τ is of order one, and the coefficient is flat near its optimum.Source: §3.4 · p. 16
  • For k ≥3, the gap message is nonlinear and yields a strict improvement, whereas for k=2 its linear-filter improvement is positive at finite girth but vanishes as girth increases.At k=2, the improved and root-only rules share an infinite-girth limit of 2/π.Source: §3.4 · pp. 16–17
  • At k=2, no choice of shell vectors or τ raises the Local Vector coefficient above 2/π, approached only as m →∞ and τ →0.The two k=2 curves converge toward 2/π as girth increases.Source: §3.4 · p. 17

4 Quantum Approximate Optimization Algorithm

This section develops methods to evaluate QAOA performance on regular, sufficiently high-girth graphs, using exact tree contractions at finite degree and a qudit–boson reformulation in the infinite-degree limit. It also presents an MPS implementation of the latter method, with accuracy controlled by Fock- and bond-dimension truncations.

4.1 QAOA for Max-k-Cut

  • For depth p on d-regular graphs with girth g ≥ 2p + 2, QAOA’s edge expectation depends only on (k, d, p) and the chosen angles, and can be evaluated on a tree light cone.The qudit encoding assigns one of k labels to each vertex; the analysis uses the Grover mixer. The tree condition makes the result independent of the particular graph instance.Source: §4.1 · pp. 17–18

4.2 Exact Tensor Contraction Algorithm at Finite Degree

  • O(p k^(2(p+1))) time and O(k^(2p)) memory suffice to contract the finite-degree tree network, independent of d.Identical branches of the regular tree are collapsed by contracting one branch and taking entrywise (d − 1)th powers; each tensor index ranges over k qudit levels.Source: §4.2 · pp. 18–19

4.3 Infinite-Degree Analysis and the Qudit–Boson Map

  • At fixed depth and angles, the finite-degree tensors converge entrywise to a d-independent recursion that yields the infinite-degree per-edge energy and Max-k-Cut cut fraction.The resulting QAOA coefficient must be extracted from the limiting recursion for each angle choice, then optimized over angles.Source: §4.3 · pp. 21, 23, 24

4.4 Qudit–Boson Representation and MPS Algorithm

  • The qudit–boson reformulation represents the infinite-degree recursion using one k-level qudit coupled to N = (k − 1)(p + 1) oscillator modes, extending the qubit mapping to arbitrary k.The k-level problem has k − 1 nontrivial Fourier channels, its central new feature relative to the qubit case; the MPS formulation enables evaluation at depths where direct recursion is impractical.Source: §4.4 · p. 24, §4.3 · p. 24
  • For the Grover mixer, the algorithm reconstructs G(p) via Schwinger–Keldysh reflections to evaluate ν∞, then uses gradient-free optimization over (γ, β) to obtain C_QAOA.Source: §4.4 · pp. 25–26
  • The bosonic state is represented as a k-tuple of MPS, with each mode truncated to Fock dimension f and bond dimension capped at χ by SVD after mixer steps.Source: §4.4 · p. 26
  • The method is exact up to independent f and χ truncations; convergence is rapid for f ≳ max |α_a,m|², while χ can grow by at most k per Grover-mixer layer before truncation.Both dimensions remain modest in practice at depths beyond the reach of the O(k^2p+2) brute-force recursion.Source: §4.4 · p. 26

5 Comparison of QAOA to the Local Vector Algorithm

The comparison puts QAOA, the improved Local Vector algorithm, and TPM on d-regular graphs at matched girth. QAOA overtakes Local Vector at sufficiently large girth in both finite-degree cut fractions and infinite-degree coefficients.

5 Comparison of QAOA to the Local Vector Algorithm

  • The comparison matches the algorithms at equal girth, using expected cut fraction at finite degree and the leading 1/d correction above the random baseline as d grows.QAOA values come from optimized-angle depth-p tree tensor-network contractions; classical values use the one-step tree averages.Source: §5 · p. 27, §5.1 · pp. 27–28

5.1 Finite-Degree Comparison

  • Across Max-2-Cut, Max-3-Cut, and Max-4-Cut, QAOA exceeds both classical curves at the girths shown, while improved rounding keeps Local Vector above TPM.Figure 7 compares expected cut fraction across degrees using each algorithm's largest available girth.Source: Figure 7 · p. 27, §5.1 · p. 28
  • At d = 20, all three methods improve with girth, and QAOA eventually crosses Local Vector while improved rounding keeps Local Vector above TPM.Figure 8 plots raw expected cut fraction against girth, equivalent to depth p.Source: Figure 8 · p. 28, §5.1 · p. 28

5.2 Infinite-Degree Comparison

  • Figure 9 compares the three methods' leading 1/d coefficients against girth, with the Local Vector coefficient optimized over rounding strength and TPM as its τ = 0 specialization.The QAOA coefficient is obtained from the qudit–boson recursion at optimized angles.Source: Figure 9 · p. 29, §5.2 · p. 29
  • In the infinite-degree limit, QAOA overtakes Local Vector by girth g = 20 (p = 9), while a persistent Local Vector–TPM gap remains for k ≥3.For k = 2, the Local Vector and TPM coefficients coincide at the girth-to-infinity ceiling 2/π.Source: §5.2 · p. 29, Figure 9 · p. 29

6 Conclusion and Future Work

The conclusion presents a provable classical Local Vector algorithm and tools for analyzing QAOA, with QAOA overtaking Local Vector at sufficiently large girth. It leaves open how close either method is to the optimum and whether stronger classical methods or a generalized overlap-gap framework are possible.

6 Conclusion and Future Work

  • The Local Vector algorithm improves the leading 1/d coefficient through one-step rounding and gives the best known provable cut-fraction guarantee among efficient classical algorithms on regular graphs for k ≥3.Its additive guarantee applies where the Frieze–Jerrum guarantee is vacuous.Source: §6 · p. 29
  • At p = 1 Local Vector is ahead of or tied with QAOA for every k, but QAOA overtakes it once girth is sufficiently large.The paper describes this as quantum advantage for graph optimization at moderate girth.Source: §6 · p. 30
  • Computing the Potts–Parisi large-degree limit for each k would provide an absolute comparison of both algorithms' distance from the optimum.The limit is identified as an open question.Source: §6 · p. 30
  • A remaining algorithmic question is whether message passing can attain the Potts–Parisi optimum for Max-k-Cut, matching or surpassing these guarantees.A positive answer would yield the first classical algorithm provably optimal at leading order for Max-k-Cut.Source: §6 · p. 30
  • Generalizing the Overlap Gap Property beyond binary alphabets remains open, and even an appropriate definition for that setting is missing.Source: §6 · p. 30

A Data for Cut Fraction Comparison

This appendix records the numerical values behind the comparison figures, including infinite-degree coefficients and finite-degree cut fractions, with details on how the SDP reference values were obtained.

A Data for Cut Fraction Comparison

Disclaimer

The document states that it is informational, not investment research or advice, and disclaims warranties and liability.

Disclaimer

  • The paper is presented for informational purposes and is not a Research Department product.Source: Disclaimer · p. 37
  • JPMorgan Chase and its affiliates disclaim express or implied warranties and liability for the document's contents.Source: Disclaimer · p. 37
  • The document is not investment research, advice, or an offer or solicitation involving financial products or transactions.Source: Disclaimer · p. 37
Loading 2609.39042v1…