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

AI summary

Overview

Research area: Quantum optimization — specifically the Quantum Approximate Optimization Algorithm (QAOA) applied to Max-$k$-Cut, compared head-to-head against provable classical local algorithms on regular, high-girth graphs.

Technical level: Advanced. The paper assumes familiarity with semidefinite programming relaxations, QAOA, tensor networks, and high-dimensional Gaussian integrals.

Scope (one sentence): The paper builds a state-of-the-art provable classical local algorithm for Max-$k$-Cut on $d$-regular graphs of girth $g$, develops new tensor-network and qudit–boson techniques to bound QAOA's performance under identical structural assumptions, and identifies the depth ($p \geq 9$, girth $g \geq 20$) at which QAOA provably overtakes the classical algorithm.

What This Paper Is About

A quantum advantage claim for approximate optimization only counts if, under the same assumptions, an efficient quantum algorithm provably beats what can be proven for the best known efficient classical algorithm. Prior work established such a claim for Max-Cut ($k=2$) on 3-regular graphs at girth $g \geq 16$; this paper asks whether the same program can be carried out for Max-$k$-Cut, where vertices are split into $k$ subsets rather than two. To answer it, the authors simultaneously strengthen the classical side (a new local vector algorithm that provably beats the random baseline) and the quantum side (new exact and asymptotic methods for evaluating QAOA on qudits).

Key Contributions

1. A classical Local Vector algorithm for Max-$k$-Cut. The authors generalize the explicit vector construction of Thompson, Parekh, and Marwaha (TPM) from Max-2-Cut to $k$ labels, and add a one-step "neighbor-message" rounding rule. The algorithm provably exceeds the random baseline $(k-1)/k$ for all regular graphs with girth $g \geq 4$, with an improvement that scales as $\Theta(1/\sqrt{d})$ as $d \to \infty$.

2. A qudit–boson reformulation of QAOA in the infinite-degree limit. Prior qudit QAOA analyses were finite-$d$ only. The authors take $d \to \infty$ and express the QAOA cut fraction in the same $(k-1)/k + \Theta(1/\sqrt{d})$ normalization as the classical algorithm, so the two can be compared on common footing. In this limit, QAOA expectation values are expressed as a qudit coupled to $(k-1)\times(p+1)$ bosonic modes, extending earlier qubit results.

3. A degree-independent tree tensor-network algorithm for qudit QAOA. The exact tree contraction of earlier work is generalized from qubits to $k$-level qudits, computing the depth-$p$ Max-$k$-Cut QAOA cut fraction on $d$-regular graphs with $g \geq 2p+2$. Collapsing identical light-cone branches by entrywise $(d-1)$-th powers gives time cost $\mathcal{O}(p,k^{2(p+1)})$ and memory $\mathcal{O}(k^{2p})$, both independent of $d$.

4. A head-to-head comparison across $(k, d, p)$. Putting the classical and quantum analyses side by side identifies the regime where QAOA wins, and a proof (Proposition 1) that the Frieze–Jerrum SDP guarantee becomes vacuous — falling below the random baseline — above an explicit degree threshold.

Main Findings

• The Frieze–Jerrum guarantee collapses at high degree. Proposition 1 defines $d_k^{\star} := 4(\alpha_k^{\mathrm{FJ}})^2/(1-\alpha_k^{\mathrm{FJ}})^2$, where $\alpha_k^{\mathrm{FJ}}$ is the Frieze–Jerrum approximation ratio. For any $d$-regular graph satisfying the near-Ramanujan bound $\lambda_{\min}(A_G) \geq -2\sqrt{d-1}$ (which holds asymptotically almost surely for random $d$-regular graphs by Friedman's theorem) and any $d > d_k^{\star}$, the certified cut fraction satisfies $\alpha_k^{\mathrm{FJ}} \cdot \mathsf{OPT}_k(G)/|E| < (k-1)/k$. The proposition concerns the guarantee, not realized performance on any particular instance.

• Classical baseline beats the SDP where it matters. For Max-2-Cut, the Dembo–Montanari–Sen result gives $\mathsf{OPT}2(G)/|E| \to 1/2 + P/\sqrt{d}$ with Parisi constant $P_ \approx 0.7632$, so the Goemans–Williamson guarantee yields roughly $0.439 + O(1/\sqrt{d})$ — below the random baseline of $1/2$ for large $d$. The authors' explicit algorithm instead achieves $(k-1)/k + \Theta(1/\sqrt{d})$ in exactly this regime.

• The neighbor-message rule strictly improves the leading coefficient. Numerically, the one-step rounding rule, in which each vertex discounts its own label preference by non-positive messages from neighbors, strictly increases the leading $1/\sqrt{d}$ coefficient for every $k$ and every girth $g \geq 6$. Because this improvement is additive and applies precisely where the Frieze–Jerrum guarantee is vacuous, the result is the best provable cut-fraction guarantee among known efficient classical algorithms on regular graphs for $k \geq 3$.

• Girth conditions are explicit. The distance-shell construction requires the radius-$(m-1)$ ball around every edge to be a tree, i.e. $g \geq 2m$. The message rule additionally requires the one-step edge neighborhood to be a tree, giving the clean condition $g \geq 6$ (it rules out triangles and 4-cycles through the edge).

• QAOA wins at depth 9. Despite the classical improvements, QAOA achieves a better cut fraction guarantee once $p \geq 9$, corresponding to girth $g \geq 20$, in both the finite-degree and infinite-degree regimes. The authors describe this as an apparent quantum advantage for Max-$k$-Cut.

• Scope limited to $k = 2, 3, 4$. The authors restrict to these values because the complexity of evaluating QAOA expectation values grows exponentially in $k$.

Methodology in Plain English

The classical algorithm borrows two ideas from the Frieze–Jerrum semidefinite program — give every vertex a vector, then round those vectors against random directions to produce a label — but throws away the SDP itself. Instead, each vertex's vector has entries that depend only on graph distance from that vertex: an entry $\alpha_0$ for itself, $\alpha_1$ for its neighbors, $\alpha_2$ for vertices two steps away, and so on out to distance $m-1$, then zero. On a regular graph of girth at least $2m$, every edge looks locally like the same tree, so the inner product between the vectors at the two endpoints of any edge takes a single common value $\sigma$. Making adjacent vectors as anti-correlated as possible (minimizing $\sigma$) reduces to finding the minimum eigenvector of an $m \times m$ tridiagonal matrix — a tiny problem whose size is set by the girth and is completely independent of the number of vertices $n$. By contrast, solving the SDP takes $O(n^{3.5})$ time with interior-point methods.

Rounding samples $k$ independent Gaussian vectors and scores each vertex-label pair by an inner product; the simple rule picks the highest-scoring label. The improved rule lets each vertex also listen to its neighbors, adding a scaled sum of neighbor "gap messages" (how strongly a neighbor prefers its top label over the alternatives) to its own score. A prefactor of $1/\sqrt{d}$ is chosen so this correction lands at the same order as the original score, which is what allows it to shift the leading $1/\sqrt{d}$ coefficient rather than a subleading term.

On the quantum side, the depth-$p$ QAOA expectation on an edge depends only on the local tree of radius $p$ when $g \geq 2p+2$. The authors contract that tree as a tensor network, exploiting the fact that all branches at a given level are identical, which collapses the cost and removes any dependence on $d$. They then take $d \to \infty$ analytically to get closed-form asymptotics, and reformulate the result as a qudit interacting with $(k-1)\times(p+1)$ bosonic modes to make larger-depth evaluations tractable.

Why This Matters

Impact on research. The paper tightens the standards for quantum advantage claims in optimization. Rather than comparing QAOA to a weak or unrelated classical baseline, it strengthens the classical competitor first — generalizing the TPM construction to $k$ labels and adding a message-passing rounding rule — and only then asks whether QAOA still wins. It also supplies reusable technical machinery: degree-independent tensor-network contraction for qudit QAOA, and a qudit–boson mapping for the infinite-degree limit. Separately, Proposition 1 gives a clean, spectral-proof-based statement of when the Frieze–Jerrum guarantee stops certifying anything beyond random guessing, which matters for how SDP-based baselines are cited in future work.

Real-world applications (context for Max-$k$-Cut; the paper itself does not discuss applications):

• Partitioning networks into communities or clusters while maximizing cross-group connectivity.
• VLSI and circuit layout, where components must be assigned to regions with many inter-region connections.
• Load balancing and scheduling, where jobs are assigned to $k$ machines and cross-assignments are preferred.
• Image segmentation with multiple labels, a standard multiway-cut formulation in computer vision.

Industry relevance. The work comes from JPMorganChase's Global Technology Applied Research and Google Quantum AI, reflecting direct interest from both the financial-technology and quantum-hardware sectors in establishing which optimization problems, and which regimes, could credibly favor quantum hardware. The girth-20 threshold is a concrete target that hardware roadmaps can be measured against.

Future Directions

• The Potts–Parisi upper bound. The authors flag this in their concluding discussion (Section 6) as a direction for bounding how much headroom remains above the current guarantees.
• Pushing beyond $k = 4$. Evaluation cost grows exponentially in $k$, so new techniques are needed to extend the comparison to larger alphabets.
• Beyond moderate girth. The advantage is established at $g \geq 20$; whether it persists or strengthens at other girth and degree combinations, and how the threshold moves, remains open.
• Demonstrating the regime physically. The analysis is provable but asymptotic and tree-based; realizing $p \geq 9$ QAOA on graphs of girth at least 20 is a hardware question the paper does not address.

Target Audience

Researchers in quantum computing and combinatorial optimization who work on QAOA performance analysis, provable approximation algorithms, or quantum advantage claims. It is most useful to readers already comfortable with SDP relaxations, tensor networks, and asymptotic analysis — graduate students and specialists in the field rather than newcomers. Practitioners evaluating whether near-term quantum hardware has a credible path to outperforming classical heuristics on graph partitioning will also find the explicit $(k, d, p)$ comparison valuable.

Authors’ abstract

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.