{"id":"2412a4b8-26ec-4705-a14d-ca44853b585a","arxiv_id":"2509.10239","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Near-optimal certification of quantum Ising Hamiltonians from time evolution, plus sample-efficient learning and certification of their Gibbs states.","lead":"The paper presents fast algorithms to check whether an unknown quantum magnet array (Ising model) matches a known one, and to learn or verify the thermal states of such arrays. One headline result reaches the fastest possible verification speed for Ising Hamiltonians from their time evolution, up to logarithmic factors.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the apparent Result 3/Theorem 15 gap is closed by rescaling, and the Bonami constant has no hidden n-dependence.","rationale":"The reader's conditional verdict rests on two concerns that do not survive scrutiny. The claimed Result 3/Theorem 15 mismatch is resolved by the standard reduction for promise problems: equality is distance 0, and the theorem's close threshold is positive, so setting the theorem parameter to half the desired far distance makes equality fall in the close case and distance >= delta fall in the far case. The intermediate interval is not part of the promise and therefore not a gap in the theorem. The Bonami concern is likewise misplaced: the quoted Montanaro-Osborne bound has constant l^(k/2), so for k=2 it is l, independent of n. I checked the surrounding arguments: Trotterization error is controlled, the Taylor tail is bounded through the Bonami inequality, the iterative scheme in Algorithm 2 maintains the needed promise, and the Gibbs-state learning/certification proofs use the Pinsker/net/shadow framework coherently. The paper's main claims are mathematically plausible and the proofs are detailed; the lack of machine-checked formal verification is not by itself a correctness objection. The constants in Lemma 9 are loose and could be adjusted, but they do not affect the asymptotic statements. I therefore see no reason to keep the conditional verdict; acceptance is appropriate.","tokens_in":16895,"tokens_out":34553,"duration_ms":275895,"concrete_test":"Verify the rescaling corollary by instantiating Theorem 15 with epsilon_th = delta/2 and checking that trace distance 0 satisfies the close-case hypothesis and trace distance >= delta satisfies the far-case hypothesis; and independently recompute the ratio (Tr[|H|^l]/2^n)^(1/l) / (Tr[H^2]/2^n)^(1/2) for a 2-local example such as H = (1/n) sum_i Z_i with k=2, l=4, confirming it stays constant as n grows. If both checks pass, the central theorems stand as stated.","verdict_should_be":"ACCEPT","load_bearing_attack":"After good-faith review, I find no load-bearing flaw in the central claims. The two concerns that might look serious do not land. First, the apparent mismatch between Result 3 and Theorem 15 disappears under the standard promise-testing reading: to decide equality versus distance >= delta, set the theorem parameter to epsilon_th = delta/2; the equality case has trace distance 0, which is below the theorem's close threshold, and the far case has distance >= 2 epsilon_th, which is the theorem's far case. The intermediate interval is outside the promise, so it does not need to be decided. Second, the quantum Bonami Lemma used in Lemma 9 is quoted correctly: Montanaro-Osborne Corollary 8.9 gives (Tr[|H|^l]/2^n)^(1/l) <= l^(k/2) (Tr[H^2]/2^n)^(1/2), i.e. constant l for k=2 with no hidden n-dependence. Consequently the Taylor-remainder bound in Eq. (8) has no n-dependence and the O~(1/epsilon) evolution time follows. The Trotterization, classical shadows, and epsilon-net arguments are internally consistent; the paper's own disclosed limitations (time-inefficient Gibbs-state learning, breakdown for k>2) are accurately stated.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript studies certification and learning of n-qubit Ising (2-local) Hamiltonians in two access models. In the time-evolution model, it gives an algorithm (Theorem 10, via the subroutine of Lemma 9) that, for a known 2-local H0 and an unknown 2-local H, distinguishes ||H-H0||_Fbar <= epsilon from ||H-H0||_Fbar >= 12 epsilon using O~(1/epsilon) total evolution time, matching the Omega(1/epsilon) lower bound up to logarithmic factors. The proof combines a Taylor expansion of Tr[e^{-it Delta H}]/2^n, Trotterization, Pauli sampling, and the quantum Bonami inequality to control the tail of the expansion. The second part develops sample-efficient algorithms for Gibbs states: Theorem 14 learns an unknown Ising Gibbs state in trace norm from O~(n^4 beta^2/epsilon^4) copies (for k=2), using an epsilon-net over Hamiltonians and classical shadows; Theorem 15 certifies closeness versus farness of two Ising Gibbs states with both sample and time complexity polynomial in all parameters. The results extend to constant k-local Hamiltonians. The paper also states clear limitations: the near-optimal certification is restricted to k=2, and the Gibbs-state learning algorithm is time-inefficient.","tokens_in":17043,"tokens_out":39655,"duration_ms":354589,"significance":"If correct, these results give the first nearly optimal Hamiltonian property-testing algorithm in the time-evolution model, the first fully sample-efficient Gibbs-state learning algorithm, and the first sample- and time-efficient Gibbs-state certification protocol, resolving a question attributed to Anshu. The proofs are carefully structured and rely on standard, independently established ingredients. I checked the two potentially fragile points explicitly. First, the Montanaro-Osborne Corollary 8.9 bound gives the l^{k/2} Bonami constant with no hidden n-dependence, so Eq. (8) and Lemma 9 are sound. Second, the apparent mismatch between abstract Result 3 (equality versus epsilon-far) and Theorem 15 (which states a close threshold epsilon^2/(400 beta n^k) and a far threshold 2 epsilon) is not a flaw: applying Theorem 15 with parameter epsilon/2 gives the desired equality-versus-delta promise, since equality satisfies the close condition and the far case is exactly distance at least delta. The limitations disclosed in the paper are accurate and appropriately framed.","major_comments":[],"minor_comments":[{"comment":"Theorem 10 states the result for all epsilon in (0, C_Fbar), but Algorithm 2 sets L = ceil(log_{15/12}(2 C_Fbar/(15 epsilon))), which is negative when epsilon >= C_Fbar/6. In that regime the far case is either impossible or occurs only at the extremal boundary ||Delta H||_Fbar = 2 C_Fbar. Please add an explicit trivial step that outputs CLOSE for epsilon >= C_Fbar/6, or restrict the theorem to epsilon < C_Fbar/6, so that the statement is literally correct over its claimed range.","section":"Section 3, Theorem 10 and Algorithm 2"},{"comment":"Result 2 and the abstract state a sample complexity of O~(n^4 beta^2/epsilon^4), while Theorem 14 gives O(3^k n^{2k} k log(n/delta) (max{beta,1})^2/epsilon^4). These agree only for beta >= 1. Please use max{beta,1}^2 in the informal statements, or explicitly assume beta >= 1.","section":"Section 1.1.2 and abstract Result 2"},{"comment":"Result 3 and Theorem 15 use different promise thresholds: Theorem 15 decides distance at most epsilon^2/(400 beta n^k) versus distance at least 2 epsilon, while the abstract states equality versus distance at least epsilon. The reduction via applying the theorem with parameter epsilon/2 should be stated explicitly, so that readers do not think Theorem 15 leaves the stated task unresolved.","section":"Section 4.2 and abstract Result 3"},{"comment":"The footnote says ||H-H0||_tr <= 200 n^k, but this is false for the unnormalized trace norm: a sum of O(n^k) Pauli strings with coefficients bounded by 1 can have trace norm as large as 2^n times that bound. The intended bound is ||H-H0||_op <= 200 n^k, which does follow by the triangle inequality and does imply ||rho-rho0||_tr <= 400 beta n^k via Eq. (7). Please correct the norm in the footnote.","section":"Footnote after Theorem 15"},{"comment":"The output line of Algorithm 3 should read rho' in S_{epsilon', n, k, beta} rather than S_{epsilon, n.k, beta}, and the Require line should include delta in the logarithm, matching the sample-complexity statement of Theorem 14.","section":"Algorithm 3"},{"comment":"The Require line of Algorithm 4 mentions only single copies of rho, but Step 1 also estimates rho0. It should state that copies of both rho and rho0 are used, in line with Theorem 15.","section":"Algorithm 4"},{"comment":"In the proof of Lemma 9, the quantity that is bounded by 1/(2400 e^6 C^2) is |u_{I^{otimes n}}|^2, not u_{I^{otimes n}}; please correct the notation in that sentence.","section":"Proof of Lemma 9"}],"recommendation":"minor_revision","confidential_remarks":"The only point I would flag for the editor is that Lemma 6 is cited from [ADEG24], a preprint co-authored by one of the present authors. I do not regard this as a circularity problem: the lemma is an auxiliary estimation subroutine, and the central claims rest on the Bonami inequality, Trotterization, Pinsker's inequality, and classical shadows, which are all independently established. No further concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"I read the paper carefully, including the stress-test note. The short version: this is a strong paper and the central claims hold up. The reader's two main worries don't survive contact with the text.\n\nThe genuinely new thing is Theorem 10: certifying an unknown 2-local Hamiltonian against a known one with O~(1/ε) total evolution time, matching the Heisenberg lower bound. The trick—controlling the Taylor remainder with the quantum Bonami lemma—is clever and, as far as I can tell, correct. The lemma is quoted correctly from Montanaro-Osborne: for 2-local H, the l-th moment is bounded by l times the second moment, with no hidden n-dependence. So the remainder estimate in Lemma 9 is O((t||ΔH||)^3), and the iteration in Theorem 10 works. The complexity accounting is careful, including Trotter error and SPAM robustness.\n\nThe Gibbs state results are also solid. Learning the Gibbs state directly, instead of going through Hamiltonian learning, is the right way to dodge the exponential-in-β lower bound. The sample complexity O~(n^4 β^2/ε^4) for 2-local is a real improvement. The certification algorithm is sample- and time-efficient and answers Anshu's question.\n\nThe one thing that might trip a reader is the abstract's Result 3, which says 'decides whether ρ_H(β)=ρ_H0(β) or ||...||≥ε'. Theorem 15 only distinguishes distance ≤ ε^2/(400βnk) from distance ≥ 2ε. That looks like a mismatch, but it isn't: under the standard promise-testing convention, you set the internal parameter to ε/2, and the equality case (distance 0) falls below the close threshold while the far case (≥ε) is above 2ε. The intermediate interval is outside the promise. The theorem's statement is actually more informative; the abstract just uses the usual shorthand. Worth a footnote in revision, but not a flaw.\n\nThe only real weakness is that the Gibbs learning algorithm is not time-efficient, and the authors say so explicitly. The covering-net argument is inherently exponential in the net size. That's a limitation, not an error.\n\nI'm comfortable sending this to peer review. The proofs are detailed, the citations are appropriate, and the claims are honestly stated. I'd bring it to the reading group, and I'd cite the certification result in work on Hamiltonian property testing.","headline":"Near-optimal Hamiltonian certification via the Bonami lemma is the real deal; the apparent abstract/theorem gap is a standard promise-testing artifact.","tokens_in":17670,"tokens_out":2807,"would_cite":true,"duration_ms":301197,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"An Ising Hamiltonian can be certified against a known candidate in $\\widetilde O(1/\\varepsilon)$ evolution time, matching the lower bound up to logs; its Gibbs state can be learned and certified with sample complexity polynomial in $n$…","keywords":["quantum Hamiltonian certification","Ising Hamiltonians","Hamiltonian property testing","Gibbs state learning","quantum state certification","Bonami lemma","hypercontractivity","classical shadows"],"falsifier":"Numerically evaluate the ratio $(\\mathrm{Tr}[|\\Delta H|^l]/2^n)^{1/l}\\big/(\\mathrm{Tr}[\\Delta H^2]/2^n)^{1/2}$ for random traceless $n$-qubit 2-local operators $\\Delta H$ with $\\|\\Delta H\\|_{\\rm op}\\le1$ and $n=4,\\dots,20$, for $l$ up to about $1/\\varepsilon$. If the ratio exceeds $C l$ with $C$ growing like $n^{\\Omega(1)}$, the Taylor-error bound in Lemma 9 fails and the claimed $\\widetilde O(1/\\varepsilon)$ total evolution time does not follow; the same computation for $k>2$ should reproduce the divergence identified in Remark 11.","tokens_in":16634,"feed_emoji":"⚛️","tokens_out":18431,"duration_ms":148310,"temperature":0.7,"pith_summary":"The paper's project is to make the verification and thermal-state characterization of quantum Ising Hamiltonians as efficient as information theory allows. For an unknown $n$-qubit Ising Hamiltonian accessed through its time evolution, it gives a certification test that decides whether the Hamiltonian is within $\\varepsilon$ (normalized Frobenius norm) of a known candidate or at least $12\\varepsilon$ away, using only $\\widetilde O(1/\\varepsilon)$ total evolution time, which matches the $\\Omega(1/\\varepsilon)$ lower bound up to logarithmic factors. For the associated Gibbs states, it gives a learning algorithm using $\\widetilde O(n^4\\beta^2/\\varepsilon^4)$ single copies in trace norm, avoiding the exponential-in-$\\beta$ sample cost that earlier Hamiltonian-learning approaches incurred, and a certification algorithm with the same sample complexity that is also time-efficient. If these results are correct, verifying a candidate quantum-device Hamiltonian and learning its thermal state become feasible at near-information-theoretic cost for the Ising class.","feed_headline":"Ising Hamiltonian test nears the Heisenberg limit","feed_subtitle":"New algorithm matches the fundamental lower bound up to logs; Gibbs states are learned with polynomial sample cost","key_machinery":"The central object for the certification result is the normalized trace of the time-evolution operator of the difference Hamiltonian, $u_{I^{\\otimes n}}=\\mathrm{Tr}[e^{-it\\Delta H}]/2^n$, whose Taylor expansion separates the desired term $-\\frac12(t\\|\\Delta H\\|_{\\bar F})^2$ from a remainder. The mechanism that keeps the remainder small is the quantum Bonami Lemma: for a $k$-local Hamiltonian $H$ and $l\\ge2$, $(\\mathrm{Tr}[|H|^l]/2^n)^{1/l}\\le l^{k/2}(\\mathrm{Tr}[H^2]/2^n)^{1/2}$; for $k=2$ the constant is just $l$ with no dependence on $n$, making the remainder $O((t\\|\\Delta H\\|_{\\bar F})^3)$ at $t=\\Theta(1/\\varepsilon)$. For the Gibbs-state results, the load-bearing identity is the Pinsker-type trace-distance bound $\\|\\rho_H(\\beta)-\\rho_{H'}(\\beta)\\|_{\\rm tr}\\le \\sqrt{2\\beta\\,\\mathrm{Tr}[(\\rho-\\rho')(H'-H)]}$, which converts closeness of Hamiltonian coefficients into closeness of Gibbs states and makes a coarse net an $\\varepsilon$-cover. The readout mechanism is classical shadow tomography, which estimates all low-weight Pauli expectation values of the net simultaneously from few copies.","core_discovery":"The central discovery is that both tasks reduce to estimating a few scalar quantities that depend on the Hamiltonian only through its low-weight Pauli coefficients. For certification from dynamics, the identity coefficient of the time-evolution operator of $\\Delta H=H-H_0$ satisfies $u_{I^{\\otimes n}}=\\mathrm{Tr}[e^{-it\\Delta H}]/2^n = 1-\\frac12 (t\\|\\Delta H\\|_{\\bar F})^2 + O((t\\|\\Delta H\\|_{\\bar F})^3)$, where the quantum Bonami Lemma — a Fourier-analytic hypercontractivity bound for $k$-local operators — controls the tail for $k=2$; estimating $|u_{I^{\\otimes n}}|^2$ by stabilizer-state Pauli sampling and iterating over exponentially decreasing tolerances yields the $\\widetilde O(1/\\varepsilon)$ certification test. For the Gibbs state, the paper proves the Pinsker-type bound $\\|\\rho_H(\\beta)-\\rho_{H'}(\\beta)\\|_{\\rm tr}\\le \\sqrt{2\\beta\\,\\mathrm{Tr}[(\\rho-\\rho')(H'-H)]}\\le O(\\beta n^2 \\max_P |h_P-h'_P|)$, so a coarse integer grid in the space of Ising coefficient vectors is an $\\varepsilon$-covering net of all Ising Gibbs states. Classical shadow tomography estimates every grid observable from $\\widetilde O(n^4\\beta^2/\\varepsilon^4)$ copies, giving a learner and, with a simple threshold on the shadow estimates of Pauli coefficients, a time-efficient certifier. The same scheme extends to $k$-local Hamiltonians with sample complexity $\\widetilde O(n^{2k})$.","pith_inferences":["A testable consequence beyond the paper: for $k>2$, the same Taylor-tail strategy should fail numerically, because the summands grow like $l^{l/2}$, and a direct moment computation on random 3-local Hamiltonians would confirm the divergence predicted by the paper's Remark 11.","Beyond the paper, the Pinsker-type bound on Gibbs-state distances is a transferable primitive: any family of states parameterized by bounded $k$-body coefficients inherits the same covering-net learning guarantee with sample complexity polynomial in $n^k$, $\\beta$, and $1/\\varepsilon$, up to constants.","A natural next step beyond the paper is to replace the brute-force search over the covering net in the Gibbs-state learner by a convex or iterative optimization over the coefficient polytope; the sample bound would stay $\\widetilde O(n^4\\beta^2/\\varepsilon^4)$ while the classical post-processing could become polynomial, turning Theorem 14 into a time-efficient learner."],"forward_implications":["Ising Hamiltonian certification reaches the Heisenberg limit: because no time-evolution algorithm can distinguish $H=\\varepsilon X$ from $H=-\\varepsilon X$ with less than $\\Omega(1/\\varepsilon)$ evolution time, the $\\widetilde O(1/\\varepsilon)$ test is optimal up to logarithmic factors.","For Gibbs states, the sample complexity is polynomial in $\\beta$, $n$, and $1/\\varepsilon$; for $\\beta=\\mathrm{poly}(n)$ and constant $k$, the learner uses $\\widetilde O(n^{2k})$ copies, an exponential speedup over full state tomography, which needs $\\Theta(4^n)$ copies.","Gibbs-state certification is both sample- and time-efficient; for $\\beta=\\mathrm{poly}(n)$ and constant $k$, it is exponentially faster in sample complexity than general state certification, which needs $\\Theta(2^n)$ copies.","The Gibbs-state results generalize to $k$-local Hamiltonians with sample complexity $\\widetilde O(n^{2k})$, whereas the near-optimal Hamiltonian certification is specific to 2-local (Ising) Hamiltonians; the paper's own tail-bound analysis shows the Bonami-based argument diverges for $k>2$."],"supporting_citations":[{"why":"Supplies the quantum Bonami Lemma (Theorem 8) used to bound the Taylor remainder of the time-evolution trace by the second moment of the difference Hamiltonian.","marker":"[MO08]"},{"why":"States the classical Bonami Lemma from Fourier analysis, which the paper identifies as the key ingredient for controlling high-order moments of the difference Hamiltonian.","marker":"[Bon70]"},{"why":"Provides the Trotterization theorem (Theorem 5) used to implement $e^{-it(H-H_0)}$ from access to $H$ and $H_0$ with controlled total evolution time.","marker":"[CST+21]"},{"why":"Proves Lemma 6, the stabilizer-state Pauli sampling routine that estimates $|u_{I^{\\otimes n}}|^2$ with $O(\\log(1/\\delta)/\\varepsilon^2)$ experiments and one unitary query per experiment.","marker":"[ADEG24]"},{"why":"Establishes the $\\Omega(1/\\varepsilon)$ evolution-time lower bound for distinguishing $H=\\varepsilon X$ from $H=-\\varepsilon X$, against which the $\\widetilde O(1/\\varepsilon)$ certification is shown optimal.","marker":"[KL25]"},{"why":"Supplies the classical shadow tomography protocol (Theorem 7) used to estimate all low-weight Pauli expectation values from few copies of the Gibbs state.","marker":"[HKP20]"},{"why":"Proves the exponential-in-$\\beta$ lower bound on learning Hamiltonians from Gibbs states, which the paper's direct Gibbs-state learner avoids by learning the state rather than the Hamiltonian.","marker":"[HKT22]"},{"why":"Prior sample-efficient Hamiltonian learning from Gibbs states whose inherited approach implied exponential-in-$\\beta$ sample cost for learning the state; this is the baseline the new learner improves.","marker":"[AAKS21]"}],"fun_headline_variants":["Ising Hamiltonian certification hits Heisenberg limit up to logs","Nearly optimal Ising Hamiltonian testing via Bonami lemma","Sample-efficient learning and certification of Ising Gibbs states","From Ising to k-local: efficient Gibbs state learning","Time-optimal Hamiltonian certification and Gibbs learning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire near-optimal certification speed rests on the 2-local quantum Bonami Lemma holding with constant $l$ and no hidden dependence on the number of qubits — $(\\mathrm{Tr}[|\\Delta H|^l]/2^n)^{1/l}\\le l(\\mathrm{Tr}[\\Delta H^2]/2^n)^{1/2}$ — since if the correct constant grew with $n$, the Taylor remainder in the certification proof would be too large and the $\\widetilde O(1/\\varepsilon)$ evolution time would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Ising Hamiltonian certification hits Heisenberg limit up to logs","Nearly optimal Ising Hamiltonian testing via Bonami lemma","Sample-efficient learning and certification of Ising Gibbs states","From Ising to k-local: efficient Gibbs state learning","Time-optimal Hamiltonian certification and Gibbs learning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000659,"raw_usage":{"total_tokens":3100,"prompt_tokens":1115,"completion_tokens":1985,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":731,"completion_tokens_details":{"reasoning_tokens":1909}},"tokens_in":731,"tokens_out":1985,"duration_ms":11802,"temperature":1.0,"reasoning_tokens":1909,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:57:26.900739+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Numerically evaluate the ratio $(\\mathrm{Tr}[|\\Delta H|^l]/2^n)^{1/l}\\big/(\\mathrm{Tr}[\\Delta H^2]/2^n)^{1/2}$ for random traceless $n$-qubit 2-local operators $\\Delta H$ with $\\|\\Delta H\\|_{\\rm op}\\le1$ and $n=4,\\dots,20$, for $l$ up to about $1/\\varepsilon$. If the ratio exceeds $C l$ with $C$ growing like $n^{\\Omega(1)}$, the Taylor-error bound in Lemma 9 fails and the claimed $\\widetilde O(1/\\varepsilon)$ total evolution time does not follow; the same computation for $k>2$ should reproduce the divergence identified in Remark 11.","supporting_citations":[],"review_version":1}