{"id":"3bb04873-a8e0-422a-9bba-d9767c073af0","arxiv_id":"2411.16163","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A dequantized classical algorithm solves the guided local Hamiltonian problem at constant accuracy for general k-local Hamiltonians, removing the previous operator-norm constraint, and at arbitrary constant accuracy when the guiding-state overlap is at least 1/sqrt(2).","lead":"The authors give a classical algorithm that estimates ground-state energies of local quantum Hamiltonians without requiring the Hamiltonian to have bounded operator norm, by dequantizing a randomized imaginary-time evolution method. In general this works only at constant accuracy, and arbitrary constant accuracy requires a guiding state with overlap at least 1/sqrt(2) with the ground state.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's allowed parameter range includes β≤0: under Eq. (4) with ε>ε* and γ²ε>1 the termination lemma fails, so the central dequantization claim is not established as stated.","rationale":"The reader's conditional verdict identified Assumption 1 and the [E_a,E_max] issue as weak points. My concern is adjacent but more specific: within the theorem's own stated parameter range, β can be negative, in which case the RQITE termination criterion is not merely unproven but demonstrably wrong. The two-level example is a concrete instantiation satisfying ε>ε*, Eq. (4), and γ=1/√2, yet it makes R(x)<0 for all x≤E0 while the threshold is positive, so the algorithm terminates immediately at the wrong point. This is an internal inconsistency in the statement of Theorem 2, not just a missing proof. It is fixable by adding a positivity condition on β and a correct stopping rule, but as written the central limited-accuracy claim fails. I therefore move the verdict from CONDITIONAL to REJECT, while noting that the analytic-continuation and cluster-expansion machinery may still be salvageable in a revised version.","tokens_in":28181,"tokens_out":19823,"duration_ms":218394,"concrete_test":"Run Lemma 2 on H=Δ|1><1| with p0=γ²=1/2, ε=20 (so ε>ε* for d≥1 and Eq. C6 holds trivially). For β=ln(1/10)/Δ<0, compute R(E_a)=Dβ(H-E_a)-D2β(H-E_a) at E_a≤0; show R(E_a)<0<Ξ, so the stated stop rule terminates at E_a. If the authors instead intend β>0, re-run the lemma with γ=0.1, ε=20 (β=ln5/Δ>0) and verify both inequalities in Eq. C8; also check whether the algorithm can locate the interval [E_max,E0] without first stopping at E_a when E_a<E_max, since Lemma 2 gives no bound on R in [E_a,E_max].","verdict_should_be":"REJECT","load_bearing_attack":"Load-bearing concern: the central limited-accuracy theorem (Theorem 2, detailed as Theorem 8) is stated for ε>ε*=2e²d(d+1) under Assumption 1, but nothing in this domain forces β>0. With β=Δ^{-1}ln(γ^{-2}ε^{-1}) (Eq. C7), whenever γ²ε>1 the logarithm is negative, and Assumption 1 is vacuous because the right-hand side of Eq. C6 is negative. Example: γ=1/√2, ε=20 gives β=-(ln10)/Δ<0. In that regime e^{-β(H-x)} is not trace-nonincreasing on x≤E0, and for a two-level Hamiltonian R(x)=Dβ-D2β is strictly negative for every x≤E0 while the termination threshold Ξ=(β/2+1)p0ε (Eq. C9) can be positive; the RQITE stop rule therefore fires at the first grid point E_a and outputs an energy that is not within ε of E0. Because the dequantized algorithm in Theorem 2 uses exactly this RQITE termination step, the claimed parameter range is not valid as written. A revision must either require γ²ε<1 (or otherwise enforce β>0) and handle the interval [E_a,E_max], or replace Lemma 2 with a termination rule that works for β≤0.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a classical dequantized algorithm for the guided local Hamiltonian (GLH) problem, based on a randomized quantum imaginary-time evolution (RQITE) scheme. The main result, Theorem 2/8, claims a classical algorithm solving the ground state energy estimation problem for general k-local Hamiltonians without the operator-norm constraint, for limited accuracy ε > ε* = 2e²d(d+1), with runtime polynomial in the system parameters up to a log-type exponent in 1/(1−β/β*). A second result, Theorem 3/10, claims arbitrary constant accuracy when the guiding state has overlap γ = 1/√2 and is prepared by a constant-depth circuit, using analytic continuation and a zero-free-region argument. The paper also gives corollaries for normalized Hamiltonians and discusses the boundary between classical and quantum computational power.","tokens_in":28400,"tokens_out":19754,"duration_ms":193802,"significance":"If the technical gaps were repaired, the cluster-expansion dequantization would be a meaningful advance: it provides an explicit classical algorithm for an interesting regime of the GLH problem, with concrete runtime formulas and a clear comparison to prior dequantized QSVT approaches. The paper correctly identifies the role of the cluster-expansion threshold β* and connects the limitations to hardness results for Gibbs-state partition functions. Strengths include a reasonably detailed cluster-expansion derivation following Ref. [30], explicit dependence on the Hamiltonian interaction degree d, and a serious discussion of prior work. However, as written, the central termination and parameter-range arguments contain load-bearing errors, so the main theorems are not established in their stated form.","major_comments":[{"comment":"The stopping rule in Lemma 2 does not separate the two energy regimes. For x∈[Emax,E0−ε] the lemma only proves R(x)>p0βε, while the threshold is Ξ=(β/2+1)p0ε = p0ε + (p0/2)βε. Under Assumption 1 one has βε≤1, so Ξ is strictly larger than the lower bound p0βε; for example, with βε=0.1, R(E0−ε)≈p0(e^{−0.1}−e^{−0.2})≈0.086p0, whereas Ξ≈0.105p0. The condition R(x)<Ξ can therefore be satisfied at grid points several ε below E0, so the RQITE algorithm can terminate before its output is within ε of E0. This invalidates the termination protocol used by Theorem 5 and inherited by Theorems 2 and 8.","section":"Appendix C.1, Lemma 2 (Eqs. C8–C9)"},{"comment":"The theorem's parameter range includes β≤0. With β=Δ^{-1} ln(γ^{-2}ε^{-1}) (Eq. C7), β is positive only when γ²ε<1. Assumption 1 as stated in Eq. C6 is vacuous when γ²ε>1 because the right-hand side is negative, and Theorem 2/8 allows ε>ε* without any condition on γ²; e.g. γ=1/√2 and ε=20 give β=−ln10/Δ<0. In that regime e^{−β(H−x)} is not trace non-increasing, every term in R(x)=Dβ−D2β is non-positive for x≤E0, and the positive threshold Ξ causes immediate termination at the first grid point, outputting an energy not within ε of E0. The theorem must either explicitly assume β>0 (e.g., γ²ε<1) and handle x∈[Ea,Emax], or replace Lemma 2 with a termination rule valid for β≤0. The proof also states 'we know that βϵ ≥ 1', which contradicts Assumption 1/Lemma 2, where βϵ≤1; the claimed accuracy threshold ε>ε* is not derived by the argument given.","section":"Appendix E.1, Theorem 8; main-text Eq. (4) and Theorem 2"},{"comment":"The normalization corollary appears to invert the accuracy threshold. Applying Theorem 8 to ~H=H/‖H‖ with relative accuracy ε>ε* gives an absolute error ‖H‖ε for the original problem, i.e. a threshold ε_abs>‖H‖ε*, not ε_abs>ε*/‖H‖. To reach ε_abs>ε*/‖H‖ one would need relative accuracy ε*/‖H‖², which is inverse-polynomial and outside the theorem's range. As stated, Table I and Corollary 1 claim a stronger result than the proof supports.","section":"Main text, Corollary 1"}],"minor_comments":[{"comment":"The text says 'e^{-β(H-x)} ≼ 0 is a trace non-increasing operator'; the semidefinite notation is wrong, and the intended meaning appears to be that e^{-β(H-x)} is positive semidefinite and trace non-increasing for x≤E0.","section":"Appendix C.1, Eq. (C16)"},{"comment":"The proof says zero points of the partition function are determined by 'the second part in the last line of Eq. (C10)', but the relevant expression Sβ(H) is defined in Eq. (E4), not Eq. (C10); the cross-reference should be corrected.","section":"Appendix E.2, proof of Theorem 9"},{"comment":"There are several presentation typos, including 'decades monotonically' for 'decays monotonically', 'Hamdard test circuit' for 'Hadamard test circuit', and 'the algorithm outputs the estimation E′0 when R(x) decays below the termination threshold' where the sentence structure is repetitive.","section":"Main text, around Eq. (3) and Fig. 1"}],"recommendation":"major_revision","confidential_remarks":"The two main technical gaps are in the termination rule and in the parameter range allowing β≤0; both are load-bearing for the central dequantization claims. The Corollary 1 direction error suggests the normalization claims should be re-examined carefully. I think the paper could become publishable if the stopping rule is corrected, the parameter conditions are stated precisely (e.g., requiring β>0 and non-vacuous Assumption 1), and the accuracy thresholds are rederived consistently. I would not accept the manuscript in its current form."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi,\n\nThe short version: this paper has a real idea—dequantizing imaginary-time evolution via cluster expansion to remove the operator-norm constraint in guided local Hamiltonian solvers—but the main theorem as stated is too broad. The good news is the fix looks straightforward. The bad news is the proof as written has a hole that matters.\n\nWhat's new: this is the first dequantized GSEE algorithm I know that works for general k-local Hamiltonians with polynomial norm, without the constant operator-norm assumption. The cluster expansion treatment of the partition function is standard but applied here to a new object, and the comparison with prior dequantized QSVT and 2D dynamics work is thorough. The limited-accuracy result, once corrected, would be a solid step forward.\n\nThe soft spots, in order of importance:\n\n1. The parameter range in Theorem 2 includes β ≤ 0. For constant γ and ε > ε*, e.g., γ = 1/√2 and ε = 20, the quantity β = Δ^{-1} ln(γ^{-2} ε^{-1}) is negative. The proof of Lemma 2 requires β > 0 and βε ≤ 1; nothing in the theorem statement enforces either. The termination threshold and cluster expansion convergence proofs fail for negative β. This is not a sign typo; it is a load-bearing gap in the theorem's declared range. The likely fix is to add the condition γ²ε < 1 and to handle the [Ea, Emax] interval where R(x) is increasing.\n\n2. The termination protocol is under-specified. The algorithm starts at Ea, but R(x) first rises to Emax before falling. Lemma 2 bounds R only on [Emax, E0 − ε] and [E0 − ε/2, E0]. Without a rule for the initial increasing segment, the algorithm could stop at Ea.\n\n3. Theorem 8's proof contains a sign error: it states βε ≥ 1 where Lemma 2 and Assumption 1 give βε ≤ 1. This is likely just a typo, but it does not inspire confidence.\n\n4. The analytic continuation section (Theorem 3) is genuinely sketchy. The bounds rely on unstated assumptions about coefficient magnitudes (e.g., |ϕ_x| ≥ 2^{-poly(n)}) and a reverse triangle inequality argument that I do not fully trust. This part needs a much more careful write-up.\n\nOverall: the core approach is promising and the errors look repairable. I would send this to a serious referee, but I would expect a major revision. The main theorem needs restatement with the correct parameter range, and the analytic continuation needs to be checked line by line. If the authors fix these, this becomes a solid result worth citing.\n\nFor the reading group: maybe—it is a good case study in how dequantization claims can overreach their assumptions.","headline":"The paper has a real idea—dequantizing imaginary-time evolution to remove the operator-norm constraint—but the main theorem's parameter range is too broad and the proof has a load-bearing gap that looks fixable.","tokens_in":28968,"tokens_out":7216,"would_cite":false,"duration_ms":61220,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Ac","03.67.-a"],"model":"deepseek-v4-flash","headline":"This paper claims that a classical algorithm can solve the guided local Hamiltonian problem for general k-local Hamiltonians without an operator-norm constraint, reaching limited constant accuracy generally and arbitrary constant accuracy…","keywords":["guided local Hamiltonian","ground-state energy estimation","dequantization","randomized quantum imaginary-time evolution","cluster expansion","analytic continuation","spectral gap","quantum advantage"],"falsifier":"Compute the cluster-expansion truncation error for a concrete k-local Hamiltonian at $\\beta$ just below $\\beta_{*}=(2e^{2}d(d+1))^{-1}$: if the error exceeds $|S|(2e^{2}d(d+1)|\\beta|)^{M+1}/(1-2e^{2}d(d+1)|\\beta|)$, the classical estimator fails. Alternatively, search numerically for a zero of $D_{\\beta}(H)$ with $\\mathrm{Re}(\\beta)>0$ for a guiding state with overlap $\\gamma^2\\ge1/2$; finding one would disprove the zero-free lemma on which the arbitrary-constant-accuracy result rests.","tokens_in":27934,"feed_emoji":"⚛️","tokens_out":10516,"duration_ms":88801,"temperature":0.7,"pith_summary":"The paper tries to establish that the guided local Hamiltonian problem, a ground-state energy estimation task that is BQP-complete when a good guiding state is supplied, can often be solved by a classical computer. Its vehicle is a dequantized, and therefore classically simulatable, version of a randomized quantum imaginary-time evolution algorithm. The key move is to evaluate the relevant partition function with cluster expansion, which removes the constant operator-norm constraint that made earlier dequantizations inapplicable to physically realistic Hamiltonians. The results give polynomial-time classical solutions when the required accuracy sits above a constant threshold $\\epsilon_{*} = 2e^{2}d(d+1)$, and when the guiding state has overlap at least $1/\\sqrt{2}$, analytic continuation extends the accuracy to any constant. If the claims hold, the boundary between classical and quantum computational power for ground-state problems shifts, with quantum advantage surviving only in more restricted regimes.","feed_headline":"Classical algorithm solves guided ground-state energy problem","feed_subtitle":"Cluster expansion drops the operator-norm cap; large guiding overlap buys arbitrary constant accuracy.","key_machinery":"The load-bearing object is the shifted imaginary-time partition function $D_{\\beta}(H-x)=\\langle\\psi_I|e^{-\\beta(H-x)}|\\psi_I\\rangle$, which equals a convolution of the guiding state's spectral function with the filter $e^{\\beta x}$. The residue function $R(x)=D_{\\beta}(H-x)-D_{2\\beta}(H-x)$ falls monotonically as $x$ approaches the ground-state energy and serves as the termination threshold. Classically, this quantity is computed through a cluster expansion of $\\log\\langle y|e^{-\\beta(H-x)}|x\\rangle$: terms factor over connected clusters of the Hamiltonian's interaction graph, and the graph degree $d$ controls the convergence radius $\\beta_{*}=(2e^{2}d(d+1))^{-1}$. For the arbitrary-accuracy result, the map $\\beta\\mapsto\\beta\\phi(z)$ with $\\phi(z)=\\log(1-z/\\nu)/\\log(1-1/\\nu')$ performs analytic continuation, and the zero-free region $\\mathrm{Re}(\\beta)>0$ guaranteed when $\\gamma\\ge 1/\\sqrt{2}$ makes $\\log D_{\\beta}(H)$ analytic so that the complex Taylor approximation applies.","core_discovery":"The central claim is that there is a classical algorithm that solves the ground-state energy estimation problem for general k-local Hamiltonians, with no bound on the operator norm of $H$, provided the spectral gap is not too small compared with the desired accuracy and the guiding state has a semiclassical form that is classically accessible. The algorithm estimates the shifted partition function $D_{\\beta}(H-x)=\\langle\\psi_I|e^{-\\beta(H-x)}|\\psi_I\\rangle$ by cluster-expanding its logarithm, and uses the residue $R(x)=D_{\\beta}(H-x)-D_{2\\beta}(H-x)$ as a monotone termination test to locate $E_0$. Cluster expansion converges when $\\beta<\\beta_{*}=(2e^{2}d(d+1))^{-1}$, giving accuracy $\\epsilon>\\epsilon_* = 2e^{2}d(d+1)$ with runtime $R^2|S|/\\epsilon$ times a factor polynomial in $(|S|/(\\gamma^2\\beta\\epsilon[1-\\beta/\\beta_*]))^{\\log(\\beta_*/\\beta)}$. When the guiding state has overlap $\\gamma\\ge 1/\\sqrt{2}$, the logarithm of the partition function has no zeros for $\\mathrm{Re}(\\beta)>0$, so analytic continuation extends the imaginary time to an arbitrary constant and yields arbitrary constant accuracy, at the cost of a runtime of order $(e^{2\\pi\\beta/\\beta_*}/(\\beta\\epsilon^2)\\mathrm{poly}(|S|))^{e^{2\\pi\\beta/\\beta_*}}$. Normalizing the Hamiltonian improves the accuracy threshold to $\\epsilon > \\epsilon_*/\\|H\\|$.","pith_inferences":["An implicit corollary of the accuracy threshold is that the real boundary for quantum advantage may be set by the required precision relative to the spectral gap, not by the Hamiltonian's norm; a matching hardness result for $\\epsilon\\le\\epsilon_*$ would make this crisp.","The $\\gamma=1/\\sqrt2$ overlap threshold is where the zero-free proof becomes tight, so a natural test is whether overlaps just below $1/\\sqrt2$ make constant-accuracy estimation classically hard, possibly by locating zeros of the partition function.","The method's dependence on Assumption 1 suggests testing it on molecular systems with known large gaps; if the gap-to-accuracy condition fails in practice, a resummed or higher-order cluster expansion would be needed to extend the approach.","For guiding states prepared by deeper circuits, the similarity-transformed Hamiltonian's interaction degree $d'$ grows and the accuracy threshold worsens; quantifying this growth on concrete circuit families would show how far the analytic-continuation route can go."],"forward_implications":["For classically accessible guiding states, exponential quantum advantage is not expected when only constant accuracy above $\\epsilon_*$ is required; the problem is classically solvable in time polynomial in the system size for fixed gap and accuracy.","Removing the operator-norm constraint makes the method applicable to realistic Hamiltonians with $\\|H\\|=\\mathrm{poly}(n)$, such as Ising-type models; normalizing $H$ further relaxes the accuracy threshold to $\\epsilon_*/\\|H\\|$.","With overlap at least $1/\\sqrt{2}$, the classical algorithm reaches arbitrary constant accuracy, though its runtime has an exponent that grows doubly exponentially with the inverse gap.","The BQP-hardness of the guided local Hamiltonian problem depends on demanding arbitrarily small inverse-polynomial accuracy; for the classically accessible instances considered here, constant accuracy is not enough to guarantee quantum advantage.","The accuracy threshold $\\epsilon_* = 2e^{2}d(d+1)$ is determined by the interaction-graph degree, so sparser Hamiltonians admit tighter accuracies before the cluster expansion breaks down."],"supporting_citations":[{"why":"Introduces the randomized Fourier estimation and Hadamard-test framework that RQITE adapts to the imaginary-time filter.","marker":"[18]"},{"why":"Supplies the sample-complexity lemma and the gap larger than accuracy condition (Assumption 1) used to set beta and the termination threshold.","marker":"[20]"},{"why":"Formalizes the guided local Hamiltonian problem, proves BQP-hardness, and gives the earlier dequantization under ||H||<=1 that this work removes.","marker":"[23]"},{"why":"Establishes BQP-completeness of the guided local Hamiltonian problem, the complexity-theoretic backdrop for the dequantization.","marker":"[24]"},{"why":"Recent classical algorithm for constant approximation of ground-state energies, a baseline this work improves by dropping the operator-norm constraint.","marker":"[26]"},{"why":"Provides the analytic-continuation technique for classical simulation of short-time quantum dynamics and a related dequantization of RFE for 2D systems.","marker":"[29]"},{"why":"Supplies the cluster expansion, the connected-cluster bound, and the complex Taylor approximation underlying both dequantization results.","marker":"[30]"},{"why":"Gives algorithmic cluster expansions and hardness results for Gibbs-state partition functions that bound how far beta can be extended in general.","marker":"[32]"},{"why":"Defines semiclassical subset states, justifying the classically accessible guiding-state model the dequantized algorithm assumes.","marker":"[38]"}],"fun_headline_variants":["Classical algorithm removes operator-norm cap for guided Hamiltonians","Guided local Hamiltonian cracked classically without norm cap","Dequantized GLH: arbitrary constant accuracy with strong overlap","Cluster expansion dequantizes guided Hamiltonian, lifts norm limit"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction depends on the gap-to-accuracy condition $\\Delta/\\epsilon \\ge \\ln(\\gamma^{-2}\\epsilon^{-1})$, which keeps the imaginary-time parameter $\\beta$ small enough that $\\beta\\epsilon\\le1$ and the cluster expansion converges; if the gap is smaller or the accuracy demand is tighter, the dequantized algorithm loses its efficiency guarantee.","fun_headline_variants_meta":{"raw":{"variants":["Classical algorithm removes operator-norm cap for guided Hamiltonians","Guided local Hamiltonian cracked classically without norm cap","Dequantized GLH: arbitrary constant accuracy with strong overlap","Cluster expansion dequantizes guided Hamiltonian, lifts norm limit"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000875,"raw_usage":{"total_tokens":3872,"prompt_tokens":1121,"completion_tokens":2751,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":737,"completion_tokens_details":{"reasoning_tokens":2683}},"tokens_in":737,"tokens_out":2751,"duration_ms":20794,"temperature":1.0,"reasoning_tokens":2683,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T13:30:15.789158+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the cluster-expansion truncation error for a concrete k-local Hamiltonian at $\\beta$ just below $\\beta_{*}=(2e^{2}d(d+1))^{-1}$: if the error exceeds $|S|(2e^{2}d(d+1)|\\beta|)^{M+1}/(1-2e^{2}d(d+1)|\\beta|)$, the classical estimator fails. Alternatively, search numerically for a zero of $D_{\\beta}(H)$ with $\\mathrm{Re}(\\beta)>0$ for a guiding state with overlap $\\gamma^2\\ge1/2$; finding one would disprove the zero-free lemma on which the arbitrary-constant-accuracy result rests.","supporting_citations":[{"cited_title":"Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers","cited_arxiv_id":null,"evidence_quote":"Supplies the sample-complexity lemma and the gap larger than accuracy condition (Assumption 1) used to set beta and the termination threshold."},{"cited_title":"Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation","cited_arxiv_id":null,"evidence_quote":"Formalizes the guided local Hamiltonian problem, proves BQP-hardness, and gives the earlier dequantization under ||H||<=1 that this work removes."},{"cited_title":"Dequantizing algorithms to understand quantum advantage in machine learning","cited_arxiv_id":null,"evidence_quote":"Supplies the cluster expansion, the connected-cluster bound, and the complex Taylor approximation underlying both dequantization results."},{"cited_title":"Classical simulation of short-time quantum dynamics","cited_arxiv_id":null,"evidence_quote":"Gives algorithmic cluster expansions and hardness results for Gibbs-state partition functions that bound how far beta can be extended in general."},{"cited_title":"Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions","cited_arxiv_id":null,"evidence_quote":"Defines semiclassical subset states, justifying the classically accessible guiding-state model the dequantized algorithm assumes."}],"review_version":1}