Pith. sign in

REVIEW 3 major objections 4 minor 4 references

Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper shows that a five-layer QAOA-style circuit, analyzed exactly on high-girth regular graphs, reaches within 1.62% of the exact ground-state energy of the infinite 1D antiferromagnetic Heisenberg ring, while beating classical…

desk verdict Good recursion analysis for QAOA-style circuits on QMC/EPR/XY, but the abstract overstates the KING comparison on random regular graphs. read the letter →

arxiv 2412.15147 v1 pith:6IROK6YY submitted 2024-12-19 quant-ph

Kunal Marwaha , Adrian She , James Sud This is my paper · ORCID
classification quant-ph MSC 81P6805C80
keywords variationalquantumalgorithmsApproximateOptimizationAlgorithmMaxCutEPRHamiltonianrandomregulargraphslocalproblemsHeisenbergspinchainQAOA
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper analyzes two short variational quantum circuits, the MC ansatz, whose phase gate is the MaxCut $ZZ$ Hamiltonian, and the XY ansatz, which alternates $ZZ$ and $YY$ phase gates, applied to three graph Hamiltonians: Quantum MaxCut (QMC), the EPR Hamiltonian, and the XY model. For high-girth regular graphs it derives iterative formulas that compute the per-edge energy in the infinite-size limit with high probability, at a cost exponential in circuit depth. On the EPR Hamiltonian, and hence on QMC for bipartite graphs, the MC ansatz outperforms the classical baselines ZERO, MATCH, CUT, and the SDP-based KING algorithm in the settings tested. The headline numerical fact is that the depth-5 MC ansatz on an infinite 1D ring reaches per-edge energy $1.3638$, within $1.62\%$ of the exact value $2\ln 2\approx 1.3863$. The analysis also identifies the symmetric (permutation-invariant) starting product state as the obstacle on general QMC instances, where the same circuits do not beat simple classical algorithms.

What carries the argument

The load-bearing object is the light-cone iteration. Because the graph has girth greater than $2p+1$ (or $4p+1$ for the XY ansatz), every depth-$p$ neighborhood is exactly two $D$-ary trees glued at their roots; a single edge's contribution to the energy is a sum over $\pm1$-valued bitstrings $a,b$ of length $2p+1$ (MC) or $4p+1$ (XY), weighted by transition amplitudes $f(a)$, $f'(a)$, and by subtree sums $H_D^{(m)}(a)$ defined recursively via $H_D^{(m)}(a)=\left(\sum_b H_D^{(m-1)}(b)\cos(\Gamma\cdot(ab)/\sqrt D)f(b)\right)^D$. This iteration converts a global random-graph expectation into a single-edge local computation, making the $D\to\infty$ limit and the $p$-layer energies computable, exponentially in $p$.

What would settle it

Simulate the depth-5 MC ansatz with the paper's optimized angles on a cycle of length $N$ (say $N=1000$) for the EPR Hamiltonian, and extrapolate the per-edge energy to $N\to\infty$; the paper's claim predicts convergence to $1.3638$ within the stated high-probability error. If finite cycles or longer-range correlations move the value by more than that, the local-tree reduction fails.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the performance of QAOA-type circuits for 2-local Hamiltonians on high-girth regular graphs can be reduced to a single-edge expectation computed by a recursive tree iteration, and that this yields concrete energy numbers that beat all known competitors on the EPR Hamiltonian at finite degree. The MC ansatz at depth $p$ is the state $|\gamma,\beta\rangle = e^{-i\beta_p B} e^{-i\gamma_p C^z}\cdots e^{-i\beta_1 B} e^{-i\gamma_1 C^z} |+\rangle^{\otimes n}$, with $B=\sum_j X_j$ and $C^z=-D^{-1/2}\sum_{(u,v)}Z_uZ_v$. The equivalent depth-5 circuit on a bipartite graph achieves $1.3638$ per edge on the EPR Hamiltonian, which translates to QMC by a local $Y$-rotation on one bipartition; on the infinite ring this is within $1.62\%$ of the exactly solved ground-state energy density $2\ln 2$ of the antiferromagnetic Heisenberg chain. The same methods show that on non-bipartite QMC and XY models the ans\"atze, started from a permutation-invariant product state, fail to beat ZERO, MATCH, or CUT at depths up to 5, and in the infinite-degree limit they do not beat a maximum cut at the depths probed.

Load-bearing premise

The energy formulas assume the graph has no short cycles (girth above $2p+1$, or $4p+1$ for the XY ansatz), and the reported random-regular-graph numbers assume that the rare short cycles that do occur change the energy on only a vanishing fraction of edges.

Editorial extensions

If this is right

  • A depth-5 MC ansatz prepares a state within $1.62\%$ of the exact ground-state energy of the infinite 1D antiferromagnetic Heisenberg ring, using only constant depth.
  • On the EPR Hamiltonian, the MC ansatz at depth 2 or more beats ZERO, MATCH, CUT, and the SDP-based KING algorithm for every regular degree $d=2,\dots,5$ reported.
  • Because EPR and QMC coincide on bipartite graphs up to local rotation, the same energy improvement carries over to QMC on random regular bipartite graphs at finite degree.
  • For general (non-bipartite) QMC and XY Hamiltonians, the permutation-invariant start prevents the ans\"atze from improving on classical baselines at the depths studied.
  • In the infinite-degree limit, the normalized energy of both ans\"atze on the XY Hamiltonian approaches but does not exceed the Parisi value of a maximum cut at the depths probed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the identified symmetry barrier is the real culprit, warm-starting the same circuits from a good classical product state, such as a near-maximum cut, could make them competitive for QMC; this is a testable modification the paper does not itself run.
  • The depth-1 closed-form formulas for arbitrary graphs could serve as finite-size predictions or as certificates for small quantum-hardware experiments before the infinite-size tree approximation sets in.
  • The depth-5 result on the ring suggests constant-depth circuits may be enough to approximate ground states of integrable spin chains, despite known exact algebraic preparation methods requiring circuit depth that grows with system size; a systematic finite-size scaling study would test this.
  • The near-coincidence between optimal MC-ansatz angles on the XY Hamiltonian and the known MaxCut QAOA angles at high depth hints at transferable parameter schedules across non-commuting Hamiltonians; the paper leaves the mechanism unexplained.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies two QAOA-inspired variational algorithms, the MC ansatz and the XY ansatz, for optimizing three 2-local Hamiltonians (QMC, EPR, XY) on high-girth regular graphs. It derives iterative formulas (Theorems 1 and 2) for the expected per-edge energy at depth p, with time and space exponential in p, and takes the infinite-degree limit (Corollaries 1 and 2). Numerical optimization for degrees up to 5 and depths up to 5 (MC) or 2 to 4 (XY) yields tables comparing with the classical algorithms ZERO, MATCH, CUT, and with King's SDP-based algorithm on edge-transitive graphs. The central findings are that the ansaetze outperform ZERO, MATCH, and CUT for EPR at small degrees and for QMC on bipartite graphs, but not for QMC or XY on general graphs; in the infinite-degree limit they do not beat CUT; and for the 1D Heisenberg ring, MC(5) attains energy within 1.62% of the exact value.

Significance. The paper extends the recursive tree-based analysis of [Bas+22a] from MaxCut to non-commuting 2-local Hamiltonians, and Appendix D generalizes the approach to k-local permutation-invariant terms on hypergraphs. The numerical cross-checks against exact statevector simulation, the released code [Sud24], and the explicit labeling of optimized energies as lower bounds are notable strengths. If the issues below are fixed, the framework constitutes a genuine and useful extension, and the low-degree EPR results provide a concrete separation from simple classical algorithms. The advertised superiority over King's SDP-based method on random regular graphs is not established, which tempers the significance of the headline claim.

major comments (3)
  1. [Abstract; §4.1] The abstract claims the algorithms 'outperform known methods to optimize the EPR Hamiltonian ... on random regular graphs', but the comparison to KING, the state-of-the-art SDP-based algorithm of [Kin23], is restricted to edge-transitive graphs such as regular trees. On regular trees, edge-transitivity forces the SDP angles theta_ij to be uniform, and the energy is then shown to equal MC(1,EPR). The paper itself states that 'it is unclear how to analyze this approach on arbitrary high-girth regular graphs'. Since random regular graphs are not edge-transitive, KING could in principle use edge-dependent theta_ij and exceed the uniform-tree value; at D=4 the reported MC(5,EPR) margin over ZERO is only 0.11639, so this is not a negligible risk. Please either provide a numerical or analytical bound on KING for random regular graphs, or revise the abstract and Section 1.1 to claim outperformance only over ZERO, MATCH, and CUT on random regular graphs and over KING on edge-transitive graphs.
  2. [Theorem 2 / Corollary 2; §3.2] The stated girth condition 'girth > 2p+1' for the XY ansatz is insufficient. The proof in Appendix C.2 explicitly notes that the Heisenberg-evolved operators depend on the subgraph of vertices at distance up to 2p from the edge (L,R), giving n = 2(D^(2p) + ... + D + 1) vertices. For this subgraph to be a pair of glued D-ary trees, the graph must have girth greater than 4p+1, not 2p+1. The same issue appears in the introductory statement of Section 3, which says the formulae for both ansaetze require high-girth (>= 2p+1). Please correct the girth condition for the XY ansatz throughout and confirm that the numerical tables for XY(p) are interpreted with the correct light-cone depth.
  3. [Appendix B] The proof of Theorem 2 states that Lemmas 3, 4, 5, and 6 of [Bas+22a] apply verbatim to the generalized definitions of f, H, Gamma, a', B0, and the relabelling in Eq. (35), but only Lemma 5 is reproduced. The XY derivation relies on parity and reality properties of the sums, for example in passing from Eq. (93) to Eq. (97) and in Lemma 6. Please state the adapted lemmas explicitly or provide short proofs that the hypotheses of the borrowed lemmas hold for the XY definitions. The statevector cross-checks at low depth mitigate the risk, but the paper should be self-contained on this load-bearing point.
minor comments (4)
  1. [§5] The sentence 'For QMC and EPR, it may be the case that starting from a good product state, similar statements may hold' appears to contain a typo; the preceding discussion contrasts QMC and XY with EPR, so the sentence should likely read 'QMC and XY'.
  2. [§4.1] In the final paragraph, 'we outperform the algorithm for for any p >= 2' contains a duplicated word 'for'.
  3. [§3] Theorems 1 and 2 are stated for high-girth graphs, while Tables 2-4 are presented as results on random regular graphs. The brief transfer argument in Section 3 is plausible but informal; please state the precise convergence or concentration claim (e.g., per-edge energy converges to the high-girth value with high probability) and cite a theorem or give a short proof, so the advertised interpretation of the tables is fully justified.
  4. [Fig. 1 caption] The caption says the MC ansatz uses p=5 for degree in [2,5] and p=10 at infinite degree, while Table 2 reports MC values for D=1..4 (degree 2..5) and Table 3 reports p up to 10 only in the infinite-degree limit; please clarify the exact depth choices in each panel to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: reported energies are explicit variational maxima evaluated by derived formulas and benchmarked against independent external values; prior-work citations are reused techniques, not target results.

full rationale

The paper's central quantities are defined as variational maxima: Eq. (11) sets νp(H,A)=max_Θ νp(H,A,Θ), and Section 4 states 'we actually obtain lower bounds for A(p,H)' because numerical optimization lacks a global-optimality certificate. Reporting MC(5,EPR)=1.3638 is therefore the definition of the algorithm's performance, not a fit disguised as a prediction. The benchmarks are external: the Bethe-ansatz value 2 ln 2 ≈ 1.3863 from [Bet31; Fad96], the classical ZERO/MATCH/CUT values in Table 1 with independent matching/cut bounds [AF21; Coj+20; TPM22; AMS23], and King's SDP algorithm [Kin23]. The 1.62% comparison is a ratio between two independently computed numbers. The iteration theorems (Theorems 1 and 2) are proved in Appendix C, and the needed parity/sum lemmas are stated and proved in Appendix B (Lemmas 1-7); where the text says Lemmas 3-6 of [Bas+22a] 'apply in our setting', it explicitly notes they follow by the same logic under the paper's redefinitions and reproduces Lemma 5. The infinite-degree limit formula for H^(m)(a) is taken from [Bas+22a, Section 4.2], a parameter-free published mathematical result about the QAOA recursion, not the EPR/QMC claim being made here; co-authorship of [Bas+22a] does not make that citation circular under the stated rules. No uniqueness theorem is invoked to forbid alternatives, no ansatz is adopted by citation without the paper's own construction, and the high-girth-to-random-regular transfer is a standard local-weak-convergence argument with explicitly stated girth assumptions. The restricted KING comparison on edge-transitive regular trees is a scope limitation for the 'random regular graph' phrasing, but it is not a reduction of a prediction to an input, so it does not count as circularity.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The main tunable inputs are the circuit angles, which are optimized rather than predicted. The high-girth locality reduction and the borrowed lemmas are the key background assumptions. No new physical entities are introduced.

free parameters (2)
  • MC ansatz angles (gamma, beta) = Depth-dependent values listed in Appendix E and the repository (e.g., p=5 for EPR)
    These angles are numerically optimized with BFGS and random restarts to maximize the reported energy. The resulting energies are explicitly lower bounds, and the reported values depend on these fitted parameters.
  • XY ansatz angles (gamma_y, gamma_z, beta) = Depth-dependent values listed in Appendix E, Table 6
    Same as above: numerically optimized to maximize the energy for the XY ansatz, and central to the XY ansatz results.
assumptions (3)
  • domain assumption Random (D+1)-regular graphs of high girth have all depth-p neighborhoods treelike for a vanishing fraction of edge exceptions, so per-edge energy converges to the tree recursion.
    Used in Section 3 and the paragraph on asymptotic equivalence with [Bas+22a] and [Wor81]. The quantitative results inherit this modeling assumption about the graph ensemble.
  • ad hoc to paper The four lemmas from [Bas+22a] (Lemmas 3, 4, 5, 6) apply verbatim to the generalized definitions of f, H, Gamma, a', and B0 used in this paper.
    Asserted in Appendix B without a full proof. Theorem 2 and Corollary 2 rely on these lemmas for the XY ansatz.
  • standard math The Bethe ansatz value 2 ln 2 is the exact maximum per-edge energy of QMC on the infinite 1D ring.
    Used in Section 4.2 and the introduction as the external ground-state benchmark, from [Bet31] and [Fad96].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs." pith.science (2026). https://pith.science/paper/6IROK6YY

@misc{pith2026241215147,
  author       = {Pith},
  title        = {Pith review of: Performance of Variational Algorithms for Local Hamiltonian Problems on Random Regular Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6IROK6YY}},
  note         = {Machine review of arXiv:2412.15147}
}
read the original abstract

We design two variational algorithms to optimize specific 2-local Hamiltonians defined on graphs. Our algorithms are inspired by the Quantum Approximate Optimization Algorithm. We develop formulae to analyze the energy achieved by these algorithms with high probability over random regular graphs in the infinite-size limit, using techniques from [arXiv:2110.14206]. The complexity of evaluating these formulae scales exponentially with the number of layers of the algorithms, so our numerical evaluation is limited to a small constant number of layers. We compare these algorithms to simple classical approaches and a state-of-the-art worst-case algorithm. We find that the symmetry inherent to these specific variational algorithms presents a major \emph{obstacle} to successfully optimizing the Quantum MaxCut (QMC) Hamiltonian on general graphs. Nonetheless, the algorithms outperform known methods to optimize the EPR Hamiltonian of [arXiv:2209.02589] on random regular graphs, and the QMC Hamiltonian when the graphs are also bipartite. As a special case, we show that with just five layers of our algorithm, we can already prepare states within 1.62% error of the ground state energy for QMC on an infinite 1D ring, corresponding to the antiferromagnetic Heisenberg spin chain.

Figures

Figures reproduced from arXiv: 2412.15147 by the authors.

Figure 1
Figure 1. Optimal algorithms for the QMC, EPR, and XY Hamiltonians on random regular graphs (top) and random regular bipartite graphs (bottom). The green boxed regions indicate regimes where our quantum algorithms outperform the classical algorithms ZERO, MATCH, and CUT. For the MC ansatz we use p = 5 when degree ∈ [2, 5], and p = 10 at infinite degree. For the XY ansatz we use p = 2 when degree ∈ [2, 5], and p = 4 at infinit… view at source ↗
Figure 2
Figure 2. Optimal angles by ansatz layer r for the MC ansatz on the XY Hamiltonian in the infinite degree limit at various depths p. p 1 2 3 4 5 νp(XY, MC) 0 0.3086 0.4099 0.4726 0.5157 νp(MC, MC) ([Bas+22a]) 0.3033 0.4075 0.4726 0.5157 0.5476 p 6 7 8 9 10 νp(XY, MC) 0.5476 0.5799 0.6093 0.6321 0.6503 νp(MC, MC) ([Bas+22a]) 0.5721 0.5915 0.5915 0.6073 0.6203 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. We compare the optimal angles γ, β by ansatz layer r in the infinite degree limit for two algorithms: (1) p = 10 MC ansatz on the HXY Hamiltonian, and (2) p = 7 MC ansatz on the HMC Hamiltonian (from [Bas+22a]). Note that the first few optimal parameters are almost exactly equal. For the XY ansatz, we numerically obtain the values for Eq. (103) in [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: Optimal angles γy , γz and βz by ansatz layer r for the XY ansatz on the XY Hamiltonian in the infinite degree limit for various depths p. Here, we no longer recover parameter schedules with monotonically increasing γ and decreasing β inspired by quantum annealing, and…
Figure 5
Figure 5. Figure 5: Optimal values νp obtained by the MC and XY ansatz on the XY Hamiltonian. The optimal values νp obtained by MC on the MC Hamiltonian from [Bas+22a] are given for comparison, as well as a dashed horizontal line indicating the Parisi value, which corresponds to the value…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 3 linked inside Pith

  1. [343]

    Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians

    arXiv: 2204.10306. [Ber23] Thiago Bergamaschi. “Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians”. en. In: Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, 2023.doi: 10.4230/ LIPICS.ICALP.2023.20. arXiv: 2210.08680. [Ber89] Claude Berge. Hypergraphs: Combinatorics of Finite Sets. North-Holland Mathematical Library v. 45. ...

    arXiv 2024

  2. [1231]

    [Tak+23] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh

    arXiv: 2305.15201. [Tak+23] Jun Takahashi, Chaithanya Rayudu, Cunlu Zhou, Robbie King, Kevin Thompson, and Ojas Parekh. An SU(2)-Symmetric Semidefinite Programming Hierarchy for Quantum Max Cut. Aug

    arXiv

  3. [2018]

    Progress towards Practical Quantum Variational Algorithms

    doi: 10.1017/9781316848142. [WHT15] Dave Wecker, Matthew B. Hastings, and Matthias Troyer. “Progress towards Practical Quantum Variational Algorithms”. In: Physical Review A (2015). doi: 10.1103/PhysRevA.92.042303. [Wor81] Nicholas C. Wormald. “The asymptotic distribution of short cycles in random regular graphs”. In: Journal of Combinatorial Theory, Seri...

    doi:10.1017/9781316848142 2015

  4. [2023]

    An explicit vector algorithm for high- girth MaxCut

    arXiv: 2307.15688. [TE24] Reuben Tate and Stephan Eidenbenz. Theoretical Approximation Ratios for Warm-Started QAOA on 3-Regular Max-Cut Instances at Depth p=1 . Oct. 2024. arXiv: 2402.12631. [TPM22] Jessica K Thompson, Ojas Parekh, and Kunal Marwaha. “An explicit vector algorithm for high- girth MaxCut”. In: Symposium on Simplicity in Algorithms (SOSA) ....

    arXiv 1959

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.