{"id":"b2e5c636-81ea-4f06-892a-160cee75551d","arxiv_id":"2412.15147","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"QAOA-style circuits starting from symmetric states beat classical baselines for the EPR Hamiltonian at small degree and reach 1.62% error on the infinite 1D Heisenberg ring, but not for general Quantum Max Cut.","lead":"This paper studies two quantum variational algorithms, inspired by QAOA, for optimizing 2-local quantum Hamiltonians on random regular graphs, and derives formulas for their energy at small depth. It shows the algorithms beat simple classical baselines for the EPR Hamiltonian and prepare states within 1.62 percent of the ground energy on the infinite Heisenberg spin chain, while revealing a symmetry barrier on general Quantum Max Cut.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claim that the ansätze beat KING on random regular EPR is unsupported: the only KING comparison is for edge-transitive regular trees, where SDP angles are forced uniform. Random regular graphs allow edge-dependent SDP angles, so KING may exceed the reported energies.","rationale":"The reader's explicit weakest assumption is the high-girth-to-random-regular transfer, but the verdict rationale also flags the abstract's overgeneralization of the KING comparison. I see the KING gap as the more load-bearing concern for the central advertised claim. The high-girth reduction is supported by a standard local-weak-convergence argument: a random regular graph has O(1) cycles of any fixed length, so a vanishing fraction of edges have non-treelike light cones, and the per-edge energy converges to the high-girth value for fixed parameters. The optimized parameters are fixed constants, so no new concentration issue arises. The KING comparison, however, is genuinely incomplete: Section 4.1 analyzes KING only on regular trees, exploiting edge-transitivity to force uniform SDP angles. On random regular graphs, the SDP can break uniformity, and no argument or computation bounds the resulting energy. The margin over ZERO is small (e.g., 1.11639 vs 1.0 at D=4), so even a modest improvement from nonuniform angles could overturn the claim. A direct SDP computation on random regular graphs would settle the question. I therefore agree with the CONDITIONAL verdict, but for a somewhat different reason than the reader's stated weakest assumption.","tokens_in":38760,"tokens_out":13245,"duration_ms":128617,"concrete_test":"Solve King's SDP from [Kin23] for the EPR Hamiltonian on random (D+1)-regular graphs with D=4 (degree 5) and n=500, averaging over at least 10 graph samples. Compute the per-edge energy of King's one-layer circuit with the SDP-derived edge angles, and compare with MC(5,EPR)=1.11639 from Table 2. If the KING per-edge energy exceeds 1.11639, the abstract's claim that the ansätze outperform KING on random regular EPR is false. If it stays below, the claim gains empirical support, though a rigorous bound for all random regular graphs would still be needed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract asserts that the algorithms 'outperform known methods to optimize the EPR Hamiltonian ... on random regular graphs,' and the reader's strongest claim includes beating KING on EPR. But the paper's KING comparison (Section 4.1) is explicitly restricted to edge-transitive graphs: for regular trees, edge-transitivity forces θ_ij = θ, and the energy is then shown to equal MC(1,EPR). The paper even states 'it is unclear how to analyze this approach on arbitrary high-girth regular graphs.' Random regular graphs are not edge-transitive, so King's SDP can assign different θ_ij to different edges and potentially achieve higher energy than the uniform-tree value. Since KING outputs max(ZERO, the SDP-assisted circuit), it always achieves at least ZERO's per-edge energy 1.0. The reported MC(5,EPR) values are only modestly above this (e.g., 1.11639 at D=4), leaving a narrow margin. Without a bound on KING's energy on random regular graphs, or a numerical comparison on such graphs, the central claim of outperforming the state-of-the-art quantum algorithm in the advertised regime is not established. The high-girth-to-random-regular transfer, by contrast, is a standard local-weak-convergence argument and is likely sound; the sharper gap is the missing KING analysis.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":39080,"tokens_out":15467,"duration_ms":126883,"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":[{"comment":"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.","section":"Abstract; §4.1"},{"comment":"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.","section":"Theorem 2 / Corollary 2; §3.2"},{"comment":"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.","section":"Appendix B"}],"minor_comments":[{"comment":"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'.","section":"§5"},{"comment":"In the final paragraph, 'we outperform the algorithm for for any p >= 2' contains a duplicated word 'for'.","section":"§4.1"},{"comment":"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.","section":"§3"},{"comment":"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.","section":"Fig. 1 caption"}],"recommendation":"major_revision","confidential_remarks":"The core technical contribution is sound in its main lines, and the authors are transparent about lower bounds and code availability. The main action item is the KING claim: either add a numerical comparison to KING on random regular graphs or narrow the claim. The girth condition in Theorem 2 is a clear typo that should be corrected, and the borrowed lemmas in Appendix B should be stated explicitly. These fixes are within the scope of a revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know one thing up front: this is a careful, mostly honest paper, and the advertised headline is slightly oversold. The genuinely new part is the recursion machinery. They extend the Basso–Farhi–Marwaha–Villalonga–Zhou analysis to non-commuting 2-local Hamiltonians (QMC, EPR, XY) for both the MC ansatz and a new XY ansatz, and they push it to k-local hypergraph generalizations in Appendix D. The formulas are cross-checked against exact statevector simulation at small depth, the code is available, and the 1.62% error on the infinite Heisenberg ring is real and striking, even if concurrent work reaches 1.05% with a different ansatz. They are also transparent that their numerical energies are lower bounds from local optimization and that the symmetric-initial-state setup creates a barrier for QMC on general graphs. That transparency earns credit.\n\nThe soft spot is the comparison to KING. The abstract says the algorithms outperform known methods on random regular graphs, but the KING analysis in Section 4.1 only covers edge-transitive graphs. For regular trees, edge-transitivity forces all SDP angles equal, so KING reduces to the depth-1 MC ansatz. Random regular graphs are not edge-transitive: King's algorithm can assign edge-dependent angles, and the paper explicitly says it is unclear how to analyze KING there. So the claim that they beat the state-of-the-art algorithm on random regular graphs is not established by the evidence in the paper. What is established is beating ZERO, MATCH, and CUT on EPR at small finite degree, and matching KING on edge-transitive trees at depth 1. That is still a useful result.\n\nThe other concerns are minor. Theorem 2 borrows four lemmas from [Bas+22a] without re-proving them; the authors flag this, and the lemmas look standard, but it does make the proof less self-contained. The high-girth-to-random-regular-graph transfer is a standard local weak convergence argument and I am not worried about it. The D-to-infinity results are negative but plausible and consistent with monogamy intuition.\n\nBottom line: this deserves a serious referee. The abstract and the KING comparison need to be reworded or substantiated with a numerical comparison on random regular graphs, but the recursion machinery and the EPR benchmarks are a real contribution. I would bring it to the reading group and would cite it for the techniques.","headline":"Good recursion analysis for QAOA-style circuits on QMC/EPR/XY, but the abstract overstates the KING comparison on random regular graphs.","tokens_in":39606,"tokens_out":1581,"would_cite":true,"duration_ms":15850,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","05C80"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["variational quantum algorithms","Quantum Approximate Optimization Algorithm","Quantum MaxCut","EPR Hamiltonian","random regular graphs","local Hamiltonian problems","Heisenberg spin chain","QAOA"],"falsifier":"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.","tokens_in":38542,"feed_emoji":"⚛️","tokens_out":7982,"duration_ms":63440,"temperature":0.7,"pith_summary":"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.","feed_headline":"Five-layer quantum circuit hits 1.62% of exact spin ground state","feed_subtitle":"The depth-5 circuit also beats classical and SDP baselines on the EPR Hamiltonian over random regular graphs.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the high-girth recurrence, the light-cone bitstring iteration and subtree sums, which the paper generalizes from MaxCut to QMC, EPR, and XY.","marker":"[Bas+22a]"},{"why":"Introduces the EPR Hamiltonian and the SDP-based KING algorithm; the paper's EPR results are compared against it and beat it at depth 2 or more.","marker":"[Kin23]"},{"why":"Gives the exact ground-state energy density $2\\ln 2$ of the 1D antiferromagnetic Heisenberg chain used as the benchmark for the depth-5 result.","marker":"[Bet31]"},{"why":"Supplies the matching-based baseline and the star-graph monogamy argument used to explain the large-degree limitation.","marker":"[AGM20]"},{"why":"Provides the depth-1 QAOA expectation formulas that the paper extends to arbitrary graphs for the MC ansatz.","marker":"[Wan+18]"},{"why":"Gives the Parisi-value maximum-cut baseline in the infinite-degree limit used to show the circuits do not beat CUT.","marker":"[AMS23]"},{"why":"Establishes that random regular graphs have few short cycles with high probability, justifying the transfer from high-girth to random regular graphs.","marker":"[Wor81]"}],"fun_headline_variants":["Depth-5 circuit within 1.62% of spin chain ground state","QAOA-inspired ansatz beats SDP on EPR Hamiltonian","Five layers to near-exact spin chain ground state","Symmetry obstacle foils QMC optimization on general graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Depth-5 circuit within 1.62% of spin chain ground state","QAOA-inspired ansatz beats SDP on EPR Hamiltonian","Five layers to near-exact spin chain ground state","Symmetry obstacle foils QMC optimization on general graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00115,"raw_usage":{"total_tokens":4829,"prompt_tokens":1070,"completion_tokens":3759,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":686,"completion_tokens_details":{"reasoning_tokens":3688}},"tokens_in":686,"tokens_out":3759,"duration_ms":25292,"temperature":1.0,"reasoning_tokens":3688,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:35:28.635307+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}