{"id":"3880e0a1-adc5-4f58-b802-ff52c2f960ce","arxiv_id":"2505.06478","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A new algorithm and lower bound tightly determine the total evolution time needed to test whether a Hamiltonian is local or far from local.","lead":"This paper gives a faster quantum algorithm for deciding whether a Hamiltonian is local, using only forward time evolution and measurements. It also proves a lower bound on how little evolution time any such test can use, nearly settling the question.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 rests on a quoted lemma that is false as stated: for H=Z1Z2 with ε1 approaching ε2, the lemma's lower bound stays O(1) while the true quantity vanishes with the evolution time.","rationale":"Reading the paper in good faith, the forward-only algorithm (Theorem 1) and the lower bound (Theorem 2) are supported by detailed arguments and appear sound; I did not find a structural flaw in the main result. There is a presentational inconsistency in Section 4.1: with t=√Δ/(2ε2) and α=Δ/(100ε2), the number of iterations must be m=50/√Δ, not 50√Δ, for the proof's query-count algebra to close. This should be corrected but is a typographical issue rather than a conceptual one. The load-bearing weakness is in the appendix: Theorem 4's proof applies Lemma 24 and then amplitude-estimates ∥U_{>k}∥₂². The lemma as quoted is false, as shown by the explicit H=Z1Z2 counterexample above, so the claimed matching O(1/(ε2−ε1)) reverse-evolution algorithm is unproven as written. The reader identified the same general area—Theorem 4 and Lemma 24—but with a partly incorrect justification: for ε1=0, a k-local H does not imply U_{>k}=0 because e^{-iHα} can have nonlocal Pauli support through powers of H. The correct failure is that the lemma's lower bound fails to vanish with α. The trace-free WLOG issue is real but potentially fixable. Because the main forward-only and lower-bound results appear sound, I keep the CONDITIONAL verdict: the paper can be accepted after Theorem 4 is either supplied with a correct lemma and derivation, or clearly marked as conditional on a corrected version of [ADG24, Lemma 3.1].","tokens_in":18583,"tokens_out":22175,"duration_ms":206918,"concrete_test":"Evaluate Lemma 24 for H=Z1Z2, k=1, ε1=0.9999, ε2=1, c=1, α=(ε2−ε1)/(3c). Compute ∥U_{>k}∥₂² = sin²(α) ≈ 1.23×10⁻⁸, and compare with the lemma's lower bound ((ε2−ε1)ε1+2ε2)²/(9c)² ≈ 0.0495. If the inequality is violated, obtain the correct statement of [ADG24, Lemma 3.1] and re-derive Theorem 4; if the corrected lemma carries an additional factor of α, the claimed query and evolution-time bounds in Theorem 4 must be recomputed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The matching reverse-evolution result, Theorem 4, depends entirely on Lemma 24 quoted from [ADG24, Lemma 3.1]. As printed, that lemma is quantitatively false. Take k=1, H=Z1Z2, so ∥H∥∞=1 and H is ε2=1-far from 1-local, and set ε1=1−δ with δ small and c any fixed constant. Then α=(ε2−ε1)/(3c)=δ/(3c), U=e^{-iHα}=cos(α)I − i sin(α)Z1Z2, and the component of U|σ_I⟩ on Paulis of weight >1 has squared norm sin²(α) ≈ δ²/(9c²). Lemma 24's lower bound claims this is at least ((δ(1−δ)+2)/(9c))² ≈ 4/(81c²), a constant independent of δ. For δ=10⁻⁴ and c=1, the true value is about 1.23×10⁻⁸ while the lower bound is about 0.0495, a violation by more than six orders of magnitude. Thus the separation on which Theorem 4's proof relies is not established. The reader's stated reason for doubting the lemma—that ε1=0 forces U_{>k}=0—is not the correct objection, since a k-local H can generate nonlocal components of e^{-iHα} through powers of H; the real failure is the δ-independence of the lower bound. Separately, the trace-free WLOG in Section 3.1 is not justified if controlled oracle applications are used, although this second issue may be fixable by constructing controlled reflections from uncontrolled U and U†.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies tolerant Hamiltonian locality testing: given query access to the time evolution operator e^{-iHt}, decide whether H is ε1-close to a k-local Hamiltonian or ε2-far from every k-local Hamiltonian, with distance measured by normalized Frobenius norm. The main results are Theorem 1, a forward-only, non-adaptive algorithm using O(sqrt(ε2/(ε2-ε1)^5 log(1/δ))) total evolution time and O(sqrt(ε2/(ε2-ε1)^7 log(1/δ))) queries; Theorem 2, an Ω(1/(ε2-ε1)) evolution-time lower bound that also applies to algorithms with reverse or controlled access; and Theorem 4, a matching O(1/(ε2-ε1)) algorithm when reverse evolution and controlled operations are allowed. The upper bound is obtained by a Trotterized postselection procedure that approximately implements the evolution of the nonlocal part H_{>k} of the Hamiltonian, while the lower bound uses a pair of commuting Hamiltonians whose time evolutions are close in diamond distance. Theorem 4 uses amplitude estimation on the nonlocal component of e^{-iHα} with a step size α proportional to ε2-ε1.","tokens_in":18947,"tokens_out":12359,"duration_ms":123411,"significance":"If Theorems 1 and 2 are correct, the paper gives the tightest known bounds for Hamiltonian locality testing in the tolerant setting, improves the previous evolution-time upper bounds, and supplies the first lower bound that works for arbitrary ε1, ε2. The forward-only algorithm is notable because it avoids reverse evolution and controlled oracle access, and the proof is built from explicit, mostly self-contained lemmas. Theorem 4 would close the problem by showing that the lower bound is tight when inverse queries are available. However, the proof of Theorem 4 depends on a quoted lemma that is false as stated, so that part of the paper's central claim is currently unsupported. The main forward-only upper bound and the lower bound appear structurally sound and are the paper's strongest contribution.","major_comments":[{"comment":"Lemma 24 is false as stated, and Theorem 4's proof collapses with it. Take k=1, H=Z1Z2 so that ||H||∞=1, let ε2=1, ε1=1-δ, and let c be any fixed constant. Then α=(ε2-ε1)/(3c)=δ/(3c), and U=e^{-iHα}=cos(α)I - i sin(α)Z1Z2. Since H has only the identity and the weight-2 Pauli Z1Z2, the projected component U_{>1} has squared norm ||U_{>1}||₂²=sin²(α)≈δ²/(9c²). Lemma 24's lower bound for the ε2-far case is ((δ(1-δ)+2)/(9c))²≈4/(81c²), which is independent of δ. For δ=10^{-4} and c=1, the true value is about 1.23×10^{-8} while the lemma's lower bound is about 4.95×10^{-2}. Thus the claimed separation between the close and far cases, and hence the query and time bounds derived from it in the proof of Theorem 4, is not established. A corrected lemma would need the projected norm to depend on (ε2-ε1)², not on a constant; the proof of Theorem 4 must be reworked or the theorem withdrawn.","section":"Appendix A, Lemma 24"},{"comment":"The number of postselection iterations is stated inconsistently. The text defines α=(ε2²-ε1²)/(100ε2), t=sqrt(ε2²-ε1²)/(2ε2), and then claims m:=t/α=50√(ε2²-ε1²). But t/α = [sqrt(Δ)/(2ε2)]·[100ε2/Δ] = 50/√Δ, where Δ=ε2²-ε1². Algorithm 1's loop is also written as 'for 50√ε2²-ε1² iterations'. With the stated m=50√Δ, the total evolution time would be mα=Δ^{3/2}/(2ε2), contradicting the definition t=√Δ/(2ε2) and invalidating the error bounds in Lemmas 14 and 18. The later query-count algebra in Theorem 1, which produces a Δ^{-7/2} dependence, is consistent only with m=50/√Δ. This appears to be a typo, but it must be corrected in both the algorithm statement and the definition of m, since the algorithm as printed does not implement the analyzed procedure.","section":"Section 4.1, Algorithm 1 and definitions"},{"comment":"The trace-free assumption Tr(H)=0 is justified only for algorithms that do not use controlled applications of the time evolution operator, yet Theorem 4 and its proof use controlled operations through the amplitude-estimation subroutine. The manuscript should either restrict the WLOG to the uncontrolled algorithms or provide the missing justification for the controlled setting. The issue is likely fixable: the reflection R_ψ used in Lemma 25 is phase-invariant, and the implementation via U and U† applies the global phase in conjugate pairs, so the identity component of H may cancel. But this needs to be stated explicitly, because as written the WLOG in Section 3.1 does not cover the algorithm in Appendix A.","section":"Section 3.1"}],"minor_comments":[{"comment":"The statement of Lemma 21 writes the diamond-distance bound as 2(ε1-ε2)t, which is negative for ε1<ε2; it should be 2|ε1-ε2|t or 2(ε2-ε1)t. The proof's final inequality correctly uses (ε2-ε1)t.","section":"Lemma 21"},{"comment":"In the query-count display near the end of the proof of Theorem 1, the exponent 7/2 in the denominator is correct only after the iteration count m is corrected to 50/√(ε2²-ε1²). As printed, with m=50√(ε2²-ε1²), the algebraic step from s′m to the Δ^{-7/2} bound is incorrect. This should be fixed together with the m definition in Section 4.1.","section":"Theorem 1 proof"},{"comment":"The statement of Lemma 25 says the algorithm makes calls to controlled versions of RΠ and R_ψ, but the proof then says R_ψ is implemented by conjugating the Grover diffusion operator by U and U†. It would help to spell out how controlled-R_ψ is obtained from controlled or uncontrolled U and U†, especially because the controlled-U oracle may include a global phase when H is not trace-free.","section":"Appendix A, Lemma 25"}],"recommendation":"major_revision","confidential_remarks":"The core forward-only upper bound and the lower bound appear to be in good shape and are substantial contributions. The main obstacle is Theorem 4: the quoted Lemma 24 is quantitatively false, so the matching upper bound for reverse evolution is currently unproven. This is fixable in principle if a correct first-order estimate of the projected nonlocal component is substituted, but the authors must either provide a rigorous corrected proof or clearly downgrade the claim. There is also a small but consequential typo in the iteration count of Algorithm 1 that must be corrected before the paper is usable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The forward-only tester (Theorem 1) and the lower bound (Theorem 2) are solid and well argued; the Trotterized postselection idea genuinely beats the Taylor-series barrier, and the lower bound via diamond distance between ε1Z and ε2Z is clean. The matching reverse-evolution algorithm (Theorem 4) is not supported as written, because the key Lemma 24 quoted from ADG24 is false.\n\nHere is the concrete failure. Take H=Z1Z2, k=1, ε2=1, ε1=1−δ, α=(ε2−ε1)/(3c). Then U=e^{-iHα} has nonlocal weight-2 component sin²α ≈ δ²/(9c²). Lemma 24's far-case lower bound is ((δ(1−δ)+2)/(9c))² ≈ 4/(81c²), a constant independent of δ. For δ=10⁻⁴ the two differ by six orders of magnitude. So the separation Theorem 4 relies on is not established. The reader's ε1=0 objection is not the right one: powers of a local H do generate nonlocal components of e^{-iHα}, so the close-case upper bound being nonzero is not itself a bug. The real bug is the far-case bound's independence from the gap.\n\nThere is a second gap in Theorem 4: Section 3.1 assumes Tr(H)=0 WLOG because a global phase is unobservable, but that is only true without controlled applications. Theorem 4 explicitly uses controlled U and U† for amplitude estimation, where the phase matters. Probably fixable, but not fixed.\n\nNone of this undermines Theorems 1 and 2. The analysis there (Lemmas 13, 14, 17, 18) is detailed and looks internally consistent, with a query/time tradeoff that beats the previous O(gap⁻³) and O(gap⁻²·⁵ ε₂⁻⁰·⁵) bounds. The lower bound is genuinely the first for arbitrary ε in the tolerant setting, and it covers controlled and reverse access. Citation pattern is fine; the [GIKL23] self-citation is backed by standard amplitude estimation.\n\nWho is this for: people working on Hamiltonian locality testing, quantum property testing, and Heisenberg-limited Hamiltonian learning. It deserves a serious referee. I would send it to review and ask the referee to scrutinize Theorem 4; if the authors cannot repair it, the matching claim should be withdrawn, but Theorems 1 and 2 should stand.","headline":"Forward-only tester and lower bound are solid; the matching reverse-evolution bound rests on a false lemma and needs repair.","tokens_in":19515,"tokens_out":8621,"would_cite":true,"duration_ms":76942,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper nearly closes the complexity of Hamiltonian locality testing, with near-optimal forward-only bounds and a Heisenberg-limited algorithm when reverse evolution is allowed.","keywords":["Hamiltonian locality testing","tolerant property testing","quantum query complexity","Trotterized postselection","time evolution oracle","Bell basis sampling","k-local Hamiltonian","Heisenberg limit"],"falsifier":"Set $\\varepsilon_1=0$, take $H$ to be exactly $k$-local with $\\|H\\|_\\infty=1$, and compute $\\|U_{>k}\\|_2^2$ for any step $\\alpha$: the exact value is $0$. The lemma quoted from [ADG24] in the proof of Theorem 4 asserts a strictly positive upper bound in this setting, so the printed lemma is false; checking whether a corrected lemma still yields the $O(1/\\Delta)$ query count settles the matching-upper-bound claim.","tokens_in":18364,"feed_emoji":"⚛️","tokens_out":13608,"duration_ms":115400,"temperature":0.7,"pith_summary":"The paper studies Hamiltonian locality testing: decide whether an $n$-qubit Hamiltonian $H$ is $\\varepsilon_1$-close to a $k$-local Hamiltonian or $\\varepsilon_2$-far from all such, given access to the evolution operator $e^{-iHt}$, with cost measured by total evolution time. It establishes three results: a forward-only, non-adaptive algorithm using $O(\\sqrt{\\varepsilon_2/(\\varepsilon_2-\\varepsilon_1)^5}\\,\\log(1/\\delta))$ total evolution time; a lower bound $\\Omega(1/(\\varepsilon_2-\\varepsilon_1))$ that holds even for algorithms with reverse or controlled queries; and, when reverse evolution is allowed, a matching $O(\\log(1/\\delta)/(\\varepsilon_2-\\varepsilon_1))$ algorithm. The engine is a new technique, Trotterized postselection, which simulates evolution under only the non-local part of $H$ by repeatedly evolving for a short time and postselecting on the subspace of non-local (or identity) Bell states. If correct, the reverse-query version makes the tolerant locality testing problem Heisenberg-limited, and the lower bound identifies the tolerance gap $\\varepsilon_2-\\varepsilon_1$ as the fundamental resource.","feed_headline":"Hamiltonian locality testing hits the Heisenberg limit","feed_subtitle":"Reverse evolution yields a matching optimal algorithm; forward-only queries get a near-optimal bound.","key_machinery":"Trotterized postselection. Starting from the maximally entangled Bell state $|\\sigma_{I^{\\otimes n}}\\rangle$, the algorithm repeatedly applies $I\\otimes e^{-i\\alpha H}$ for a small step $\\alpha$ and measures the projector $\\Pi_D$ onto the subspace spanned by identity and non-local Pauli Bell states, postselecting on success. The effective map per step is $e^{-i\\alpha A}+O(\\alpha^2)$ with $A=\\Pi_D(I\\otimes H)\\Pi_D$; because the identity (trace) component of $H$ has been removed, $A|\\sigma_{I^{\\otimes n}}\\rangle=(I\\otimes H_{>k})|\\sigma_{I^{\\otimes n}}\\rangle$, so $\\langle\\sigma_I|A^2|\\sigma_I\\rangle=\\|H_{>k}\\|_2^2$ is exactly the squared distance to $k$-locality. This suppresses the higher-order Taylor terms that forced earlier algorithms to use step size $t\\approx\\varepsilon$, allowing $t=\\Theta(\\sqrt{\\varepsilon_2^2-\\varepsilon_1^2}/\\varepsilon_2)$ and yielding the improved query count.","core_discovery":"The central claim is that the tolerance gap $\\Delta=\\varepsilon_2-\\varepsilon_1$, not the distance scale $\\varepsilon_2$, controls the cost of Hamiltonian locality testing. Concretely, Theorem 1 gives an $O(\\sqrt{\\varepsilon_2/\\Delta^5}\\,\\log(1/\\delta))$-time algorithm requiring only forward evolutions and no controlled gates, and Theorem 2 shows any algorithm, even with reverse or controlled access, needs $\\Omega(1/\\Delta)$ evolution time. Theorem 4 then closes the gap when reverse evolution is available: amplitude estimation on the step-$\\alpha$ propagator yields an $O(\\log(1/\\delta)/\\Delta)$-time tester, so the problem is Heisenberg-limited in $\\Delta$. The technical core is that the $O(\\alpha^2)$ error per step of the postselected evolution against $e^{-iAt}$ (where $A=\\Pi_D(I\\otimes H)\\Pi_D$) accumulates only to $O(\\alpha t)$, because the postselection succeeds with high probability in each small step.","pith_inferences":["The postselection idea should transfer to other Hamiltonian properties defined by dropping Pauli terms, such as bounded interaction graph or limited Pauli weight, and may yield Heisenberg-limited testers there too.","The trace-free step is only valid without controlled queries, so the reverse-query algorithm has an unaccounted phase issue: either the controlled amplitude-estimation calls observe the global phase and break the reduction, or the algorithm needs a phase-tracking variant.","The frontier left open is the forward-only complexity: between the $\\Omega(1/\\Delta)$ lower bound and the $O(\\sqrt{\\varepsilon_2/\\Delta^5})$ upper bound there is a substantial gap, and closing it likely needs a genuinely different technique than postselection."],"forward_implications":["Any tester for the tolerant locality gap must use $\\Omega(1/(\\varepsilon_2-\\varepsilon_1))$ total evolution time, even when reverse or controlled queries are available.","With forward-only queries, the paper's algorithm achieves the best known scaling, $O(\\sqrt{\\varepsilon_2/(\\varepsilon_2-\\varepsilon_1)^5}\\,\\log(1/\\delta))$ total evolution time, using non-adaptive queries and $n$ ancilla qubits.","With reverse evolution allowed, the $O(\\log(1/\\delta)/(\\varepsilon_2-\\varepsilon_1))$ algorithm matches the lower bound, making the tolerant problem Heisenberg-limited in the gap.","The lower bound is witness-robust: it holds for normalized Frobenius distance and, by the same diagonal witness $\\varepsilon Z_{1:k}$, also for operator norm, normalized Schatten $p$-norms, and Pauli decomposition $p$-norms."],"supporting_citations":[{"why":"It introduces the Hamiltonian locality testing problem and the normalized-Frobenius distance convention used throughout.","marker":"[BCO24]"},{"why":"It gives the prior $O((\\varepsilon_2-\\varepsilon_1)^{-7})$ simple algorithm and the intuition of evolving by the non-local part.","marker":"[Gut24]"},{"why":"It supplies the improved $O((\\varepsilon_2-\\varepsilon_1)^{-3})$ analysis and the quoted Lemma 24 on which Theorem 4's matching algorithm depends.","marker":"[ADG24]"},{"why":"It provides the Bell-basis sampling fact that $I\\otimes U$ applied to $|\\sigma_{I^{\\otimes n}}\\rangle$ samples from the squared Pauli spectrum of $U$.","marker":"[MO10]"},{"why":"It gives the Taylor-series truncation bound used to control higher-order terms in each Trotterized step.","marker":"[CMN+18]"},{"why":"It supplies the diamond-distance-to-spectral-norm comparison used to prove the lower bound.","marker":"[HKOT23]"},{"why":"It provides the amplitude-estimation corollary used to implement the reverse-query optimal algorithm.","marker":"[GIKL23]"}],"fun_headline_variants":["Hamiltonian locality testing hits Heisenberg limit","Locality testing optimal time set by tolerance gap","Reverse evolution yields optimal Hamiltonian locality test","Forward-only locality testing near-optimal in gap","Heisenberg-limited locality testing from reverse evolution"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The reverse-query optimal algorithm rests on a quoted lemma from [ADG24] whose stated bound is inconsistent at $\\varepsilon_1=0$, and separately on a trace-free simplification that is only valid without controlled queries, while Theorem 4 uses controlled applications where the global phase can be observed.","fun_headline_variants_meta":{"raw":{"variants":["Hamiltonian locality testing hits Heisenberg limit","Locality testing optimal time set by tolerance gap","Reverse evolution yields optimal Hamiltonian locality test","Forward-only locality testing near-optimal in gap","Heisenberg-limited locality testing from reverse evolution"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000643,"raw_usage":{"total_tokens":2973,"prompt_tokens":975,"completion_tokens":1998,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":591,"completion_tokens_details":{"reasoning_tokens":1931}},"tokens_in":591,"tokens_out":1998,"duration_ms":15114,"temperature":1.0,"reasoning_tokens":1931,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:43:28.103340+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $\\varepsilon_1=0$, take $H$ to be exactly $k$-local with $\\|H\\|_\\infty=1$, and compute $\\|U_{>k}\\|_2^2$ for any step $\\alpha$: the exact value is $0$. The lemma quoted from [ADG24] in the proof of Theorem 4 asserts a strictly positive upper bound in this setting, so the printed lemma is false; checking whether a corrected lemma still yields the $O(1/\\Delta)$ query count settles the matching-upper-bound claim.","supporting_citations":[],"review_version":1}