Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs

1.1 Related work

• Earlier work found that optimized threshold algorithms can outperform QAOA1 on triangle-free regular graphs, revising the comparison with local classical baselines.Source: §1.1 · p. 2
• QAOA2 has few established performance results, with prior analyses largely restricted to QAOA1, 2-regular graphs, or 3-regular graphs.Source: §1.1 · p. 2

1.2 Our results

• A 2-local classical MAX-CUT algorithm outperforms QAOA2 on every D-regular graph of girth above 5 for all D ≥ 2.The construction combines the 2-step threshold algorithm with a family of 2-local algorithms, covering the remaining degree choices.Source: §1.2 · p. 2
• The paper derives a graph-size-independent expression for QAOA2’s expected cut fraction on D-regular graphs of girth > 5 and numerically optimizes it for D < 500.Source: §1.2 · p. 2
• For equal thresholds, the 2-step threshold algorithm outperforms QAOA2 for 41 < D < 500 and is expected to do so for all larger D.Source: §1.2 · p. 2
• The girth restriction makes radius-2 neighborhoods tree-like, enabling the local analyses for QAOA2 and the 2-step threshold algorithm.Source: §1.2 · p. 2

• QAOA is implemented with |V| qubits, mixing and problem Hamiltonians, 2p parameters, alternating unitaries, and measurement in the problem-Hamiltonian eigenbasis.Source: §2 · pp. 2–3
• QAOA2’s edge-cut probability depends only on the radius-2 neighborhood, so identical local neighborhoods yield a graph-wide expected cut fraction.Source: §2 · p. 3
• For D-regular graphs of girth > 5, the theorem gives an explicit expected-cut expression in the QAOA2 parameters and degree D.Source: §2 · p. 3
• The resulting formula is independent of graph size and Hilbert-space dimension and does not require evaluating a trace.Source: §2 · p. 3
• Numerical optimization for 2 ≤ D < 500 shows QAOA2 outperforming optimal QAOA1 and the cited 1-local classical algorithms in all cases.Source: §2 · p. 3

3 Local classical algorithms

• The 2-step threshold algorithm applies thresholds τ1 and τ2 sequentially, extending the 1-step threshold algorithm to an n-step, n-local procedure.Each step flips vertices whose spin agrees with at least the specified threshold fraction of neighbors.Source: §3 · p. 4
• For graphs of girth > 5, the algorithm’s performance is derived as a function of τ1 and τ2, with optimal equal thresholds approximately τ = D/2 + k and k ≈ 0.4.For intermediate degrees up to 500, the search over threshold pairs is restricted using this approximate optimum.Source: §3 · p. 4
• b ≈0.417 outperforms QAOA2 for all 41 < D < 500, and the authors expect the 2-step threshold algorithm to win for all D ≥500.The performance oscillates because the threshold is a discrete parameter, although the oscillations decrease at large D.Source: §3 · p. 4
• For D ∈[2, 3, 4, 5], modified local classical algorithms outperform QAOA2 for D = 3, 4, and 5, while a separate search is needed for D = 2.For D = 2, one construction achieves expected performance 0.3343 over random assignment, versus QAOA2’s maximum of 1/3.Source: §3 · p. 4
• Overall, a local classical MAX-CUT algorithm has larger expected cut fraction than QAOA2 on every D-regular graph of girth > 5 for D < 500, and likely for all D.The small-degree performance values are reproduced in Appendix A.Source: §3 · p. 4

4 Discussion

• The analysis derives a graph-size-independent QAOA2 expression and optimizes its parameters, with possible extensions beyond regular high-girth graphs.Removing regularity or high-girth would require handling additional graph structure and combinatorial sums.Source: §4 · pp. 4–5
• The authors suggest that QAOA performance on high-girth graphs may reflect locality more than quantumness, and conjecture analogous p-local classical dominance for every constant p.The conjecture concerns regular graphs of girth > 2p + 1 and is also stated as a broader conjecture over all graphs.Source: §4 · p. 5
• The study is restricted to D-regular graphs and compares graphs of girth above 5.Phantom vertices can extend the analysis to maximum-degree graphs, but the authors do not claim this construction is optimal.Source: §4 · pp. 5–6
• At large degree, the 2-step threshold algorithm reaches b ≈0.417, exceeding QAOA2 at b ≈0.407 and the 1-step baselines.The comparison uses scaled performance defined by cut fraction 1/2 + bD^-0.5.Source: Figure 1 · p. 5, Figure 2 · p. 6
• The authors do not expect a small number of short cycles to change the result, but note that threshold algorithms may be ineffective on highly connected graphs.Highly connected graphs are identified as a topic for future study.Source: §4 · p. 6

A Listing of performance values at small D

• QAOA2 and the 2-step threshold algorithm outperform all previously known values at every listed degree and numerically for all D < 500.Threshold2 does not beat QAOA2 for D ∈ [2, 3, 4, 5], although a related 2-step local classical algorithm does.Source: Table 1 · p. 8

B Proof of the p = 2 QAOA formula

• The derivation assumes a D-regular graph with girth > 5 and introduces trigonometric variables p, q, k, l, r, t, y, and z.These substitutions support the subsequent simplification of f2(γ1, β1, γ2, β2).Source: B Proof of the p = 2 QAOA formula · p. 9

B.2.1 Evaluating exponentials

• The expected cut fraction is decomposed as f2 = 0.5 − 0.5(A + B1 + B2 + E), with graph symmetry giving B1 = B2.The terms are evaluated separately inside the trace.Source: B Proof of the p = 2 QAOA formula · p. 9, §B.2.1 · p. 9

B.2.2 Breaking apart into terms

• Only operators on the local neighborhoods of the measured edge can fail to commute, and trace parity eliminates terms with incompatible numbers of Pauli factors.The calculation retains terms that can reduce to trace-contributing operator products.Source: §B.2.1 · p. 9, §B.2.2 · pp. 9–11, §B.3.2 · p. 12
• The V and W sums are simplified using double-angle identities and the fact that e^{iaσx} becomes e^{ia} under the relevant trace.The resulting combinations are expressed through r, t, y, and z.Source: §B.2.2 · pp. 10–11

B.2.3 Effect of the crossover terms

• Girth > 5 ensures each external neighbor has a unique connection into the local set, so crossover terms modify selected factors while leaving the remaining terms unchanged.The transformations are applied D − 1 times for the relevant neighboring nodes.Source: §B.2.3 · p. 11, §B.3.3 · p. 14

B.3 Calculating E

• The E contribution is handled analogously by expanding exponentials, tracking sign flips, and retaining only combinations whose Pauli products can contribute nonzero trace.The calculation treats local and crossover terms separately.Source: §B.3.2 · p. 13

B.4 Full expression

• The full expression combines the A, B1, B2, and E contributions into the graph-size-independent QAOA2 formula.The proof concludes after substituting the simplified terms into the expected cut-fraction expression.Source: §B.4 · p. 14

C Correctness tests of the p = 2 QAOA formula

• The tests impose restrictions on D and the input parameters to recover previously known expressions from the derived QAOA2 formula.These checks assess consistency rather than introducing new performance results.Source: C Correctness tests of the p = 2 QAOA… · p. 15

C.1 Simplification to p = 1 formula

• Setting γ1 = β1 = 0 gives r = y = 1 and t = z = 0, reducing f2(0, 0, γ2, β2) to the p = 1 formula.The resulting expression matches Corollary 1 of [WHJR18].Source: §C.1 · p. 15
• Under γ1 = β1 = 0, the simplified expression becomes 1/2 + sin(2β2) cos(2β2) sin(γ2) cosD−1(γ2).This is the known QAOA1 expression associated with the second layer.Source: §C.1 · p. 15
• Setting γ2 = β2 = 0 instead gives f2(γ1, β1, 0, 0) = f1(γ1, β1).The first layer independently reproduces the corresponding QAOA1 expression.Source: §C.1 · p. 15

C.2 Simplification to the ring (D = 2)

• The derivation defines α(γ1, β1, γ2) = (1 + r)(−mrz − ny)(my − nrz)D−1 + (1 − r)(mrz − ny)(my + nrz)D−1, then simplifies κ and f2.Source: §C.2 · p. 15
• The resulting D = 2 expression is symbolically equal to the expression in Section IV and Appendix C of [WHJR18].The verification uses SymPy, with code made available online.Source: §C.2 · p. 15

D Analysis of the 2-step threshold algorithm

• The analysis follows by examining a neighborhood around an edge Eij in a (n+1)-regular graph.The local structure is used to evaluate the algorithm’s expected contribution.Source: D Analysis of the 2-step threshold… · p. 16
• The method defines threshold functions qi(k) that output −1 when k ≥ τi and 1 otherwise for i ∈ {1, 2}.The two thresholds parameterize the 2-step local algorithm.Source: D Analysis of the 2-step threshold… · p. 16
• For graphs of girth > 5, the expectation ⟨Zi2Zj2⟩ is calculated as −2 times the improvement over random assignment.The girth condition excludes the relevant short-cycle adjacencies in the local neighborhood.Source: D Analysis of the 2-step threshold… · p. 16

D.1 Zi, Zj initially equal

• The neighbor-spin averages Z1,+ and Z1,− are computed from binomial probabilities according to whether neighbors initially agree with i or j.The corresponding probabilities p+ and p− convert these averages into probabilities of spin +1.Source: §D.1 · p. 16
• H(k, l, r) gives the probability that l + r neighbors agree with the initial value when k/n initially agree.This quantity supplies the case weights used in the subsequent correlation calculation.Source: §D.1 · p. 16
• The four threshold-sign cases determine whether the count contribution uses l + r or n − l − r and whether one is added when Zi1 = Zj1.Mixed signs instead subtract one because the updated spins differ.Source: §D.1 · pp. 16–17
• Q combines the case probabilities for updates centered on i and j into the second-step correlation expression.The construction includes the corresponding H terms and updated-spin products for both endpoints.Source: §D.1 · p. 17
• The resulting equation is symmetric under simultaneously changing both initial spins from +1 to −1.Thus the equal-initial-spin case does not depend on which common spin value the endpoints have.Source: §D.1 · p. 17

D.2 Zi, Zj initially unequal

• If Zj0 = −1 while its other-neighbor agreement fraction remains u/n, then Zi1,k = q1(k) and Zj1,u = −q1(u).The analogous case with Zi0 = −1 and Zj0 = 1 is obtained by symmetry.Source: §D.2 · p. 17
• The expressions for Zi2,k, Zj2,u, and ⟨Zi2Zj2⟩ continue to hold after substituting the new values of Z1.The initial-sign exchange leaves the form of the equations unchanged.Source: §D.2 · p. 17
• The unequal-initial-spin calculation is symmetric under exchanging which endpoint starts at −1.This identifies the two unequal-sign orientations as equivalent cases.Source: §D.2 · p. 17

D.3 All together

• The initial agreement and disagreement cases occur with equal probability.This equal weighting determines how the case-specific correlations contribute to the overall result.Source: §D.3 · p. 17
• The section uses these equally likely initial cases to state the resulting spin correlation.The displayed correlation aggregates the preceding case analysis.Source: §D.3 · p. 17
• The final correlation is therefore an average over the two possible initial relationships between Zi and Zj.The passage frames the correlation as the consequence of combining agreement and disagreement cases.Source: §D.3 · p. 17