{"id":"1c86b2dd-a0c4-4ec2-a0e6-3ce10d45c3fd","arxiv_id":"2607.06472","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":4,"one_line_summary":"A provable exponential quantum-classical learning separation is established for predicting expectation values of time-evolved quantum states under unknown low-intersection Hamiltonians, assuming BQP ⊄ P/poly.","lead":"This paper proves that a quantum computer can learn to predict the time-evolution of quantum many-body systems exponentially faster than any classical learner, assuming BQP is not in P/poly. The separation is physically motivated: training data comes from short-time evolution experiments, while hardness arises from BQP-complete long-time dynamics.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Boosting step requires distribution-free weak learnability, but the reduction only establishes weak learnability under distributions D_μ that are structurally constrained by Def. 7 — the gap is narrow but real.","rationale":"The reader correctly identified the distribution-family restriction as the structural fragility. However, the reader assessed this as the weakest assumption without fully probing whether it actually breaks the boosting argument. The concern is more specific: Schapire's theorem requires distribution-free weak learnability, and the reduction only demonstrates weak learnability under the constrained family {D_i}. The paper is transparent about quantifying over {D_i} rather than all distributions (Def. 8), and the construction of D_μ for arbitrary μ is clever. But the gap between 'weak learnability under all D_μ' and 'distribution-free weak learnability of L' is not explicitly closed. The paper's argument would be strengthened by showing that the concept class on the x_1=1 subspace, when restricted to the relevant bits z, is equivalent to a standard PAC concept class over z for which weak learnability under all μ suffices for Schapire's theorem. This is plausible — the time-averaging step (Eq. B.140-B.141) reduces the problem to a function of z alone — but the formal verification that this reduction preserves the conditions needed for boosting is not explicitly provided. The quantum learnability side (Algorithms 1-2, Theorem 1) is well-constructed and does not depend on this concern. The Hamiltonian learning protocol is a clean simplification of Haah-Kothari-Tang, and the sample complexity analysis is thorough. The BQP-completeness of the FK Hamiltonian construction (Lemma 2, Lemma 4) is sound and builds on established results. The concern is narrowly about the classical hardness argument's final step. If the boosting application is verified to be correct under the restricted distribution family, the verdict should return to ACCEPT. If not, the hardness claim weakens substantially, though the quantum learnability contribution stands independently.","tokens_in":49663,"tokens_out":1146,"duration_ms":856957,"concrete_test":"Formally verify that Schapire's boosting theorem applies given the restricted distribution family {D_i}. Specifically: (a) Check whether weak learnability under all D_μ (which constrain t~Unif[0,T], x_1~Unif{0,1}, and x_{m+2:p(n)}=0 when x_1=1) is sufficient to invoke the theorem, or whether the theorem requires weak learnability under all distributions over (x,t). (b) If the latter, construct a distribution D' over (x,t) not in {D_i} for which the learner could fail, and check whether Def. 8's quantification over {D_i} alone leaves the hardness claim unsubstantiated. (c) Alternatively, verify that the concept class restricted to x_1=1 with fixed remaining bits is equivalent (for boosting purposes) to a distribution-free concept class over z alone.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The classical hardness proof (Theorem 3, Appendix B.3) reduces a hypothetical PAC-learner to a P/poly circuit for BQP via Schapire's boosting theorem. The key chain is: (1) the learner satisfies the PAC condition of Def. 8 for all distributions in the family {D_i} of Def. 7; (2) for any distribution μ over z∈{0,1}^m, one constructs D_μ ∈ {D_i} and shows the learner yields a hypothesis h(z) with error ≤1/4 under μ (Eq. B.151); (3) Schapire's theorem then promotes this to strong learnability, implying BQP ⊆ P/poly. The load-bearing question is whether step (2) genuinely establishes distribution-free weak learnability in the sense Schapire's theorem requires. The distributions D_μ are not arbitrary over the full input space (x,t): they are constrained so that t is uniform on [0,T], x_1 is uniform, and conditioned on x_1=1, the bits z follow μ while remaining bits are fixed to 0. Schapire's theorem requires that for every distribution over the input domain, a weak learner exists. The reduction shows this only for distributions of the specific form D_μ. If the concept class restricted to the x_1=1 subspace is not known to be weakly learnable under distributions that do not factor through this structure, the boosting argument has a gap. The paper's Def. 8 is carefully formulated to quantify over {D_i}, not all distributions, which is internally consistent. But the application of Schapire's theorem implicitly requires that weak learnability under {D_i} suffices — and this holds only if the concept class on the x_1=1 subspace is rich enough that weak learnability under all D_μ translates to distribution-free weak learnability of the BQP language L. The structural constraint that D_μ fixes x_{m+2,...,p(n)}=0 and requires uniform t means the learner is only exercised on a measure-zero slice of the full input space. A classical learner could in principle satisfy the PAC condition on all D_μ while failing on distributions that place mass on other (x,t) regions — but Def. 8 only","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"This paper formulates a supervised learning task for predicting expectation values of quantum states time-evolved by unknown low-intersection Hamiltonians with O(n) terms. The authors provide an efficient quantum learning algorithm (Algorithms 1 and 2) whose training phase uses a simplified variant of the Haah-Kothari-Tang Hamiltonian learning protocol on short-time samples, and whose inference phase combines Hamiltonian simulation with classical shadows. They prove classical hardness by embedding BQP-complete computations into the polynomial-time dynamics of a low-intersection Feynman-Kitaev clock Hamiltonian (via the Oliveira-Terhal construction), showing that no randomized polynomial-time classical algorithm can satisfy the PAC-learning condition for a certain family of input distributions, unless BQP ⊆ P/poly. The separation is established for a physically motivated concept class (Def. 6) and a structured family of input distributions (Def. 7). The technical apparatus includes tail bounds (Lemma 7), error propagation (Lemma 8), sample complexity analysis (Lemmas 9-13), and a detailed classical hardness proof (Theorem 3, Appendix B).","tokens_in":50420,"tokens_out":1405,"duration_ms":973465,"significance":"The paper makes a substantive contribution to the program of identifying physically motivated quantum learning separations. A notable strength is the use of low-intersection Hamiltonians with O(n) terms, which is more general than the O(log n)-parameter families considered in prior work (Ref. [24]). The quantum learnability result is rigorous, with explicit sample and time complexity bounds. The classical hardness proof is carefully constructed: the Oliveira-Terhal low-intersection Feynman-Kitaev construction is leveraged to maintain quantum learnability while embedding BQP-complete computations, and the discrete coefficient structure (Lemma 2) enabling zero-error learning of the hard instance is a clean observation. The interpretation in terms of learning-assisted certified quantum simulation adds conceptual value. The work is honest about its limitations, particularly that the separation arises at the evaluation stage rather than the identification stage.","major_comments":[{"comment":"Appendix B.3, proof of Theorem 3, Eqs. (B135)-(B151): The reduction from a hypothetical classical PAC-learner to a P/poly circuit for BQP proceeds by constructing, for any distribution μ over z ∈ {0,1}^m, a distribution D_μ from the family {D_i} of Def. 7, and showing the learner yields a hypothesis h(z) with error ≤ 1/4 under μ (Eq. B151). Schapire's boosting theorem is then invoked to promote this to strong learnability, implying BQP ⊆ P/poly. The load-bearing question is whether weak learnability under the distributions {D_μ} — which are structurally constrained (t uniform on [0,T], x_1 uniform, and conditioned on x_1=1, the bits z follow μ while remaining bits are fixed to 0) — suffices for the application of Schapire's theorem, which requires distribution-free weak learnability over the full input domain. The paper's Def. 8 is carefully formulated to quantify over {D_i}, making theP","section":null}],"minor_comments":[{"comment":"Eq. (18): The notation for the shadow norm bound combines two expressions with a brace labeled 'for Pauli measurements'. Clarifying whether this is a specialization or an inequality would aid readability.","section":null},{"comment":"Def. 7: The phrase 'any possible distribution over {0,1}^{p-1}' for the x_1=1 case is slightly ambiguous. Specifying that this ranges over all distributions on {0,1}^{p-1} would be clearer.","section":null},{"comment":"Algorithm 1, line 1: The choice t* ← O(ε/(MT·||O||_∞·(d+1)^2)) references 'the observable being predicted', but the algorithm predicts M observables (Q_a)_{a∈[M]}. Clarifying which observable's norm is meant, or taking a max, would be helpful.","section":null},{"comment":"Section VI.A, proof sketch of Theorem 2: The statement that 'the resulting function q(z) approximates the BQP computation deciding L up to good margin' is made informally. A forward reference to the formal margin analysis in Appendix B.3 (Eqs. B130-B134) would help the reader.","section":null},{"comment":"Lemma 4: The computation of p_diag involves a boundary term 3/(2(L+2)) from the j=L summand. The derivation (Eqs. B60-B65) is correct but a brief remark explaining the special treatment of j=L-1 → j=L would help.","section":null},{"comment":"Remark after Theorem 3: The claim that hardness can be pushed to ε = 1/2 - 1/poly(n) by adjusting parameters is interesting but stated without proof. A brief justification or reference would be welcome.","section":null},{"comment":"The paper would benefit from stating Theorem 5 (the formal quantum learnability result) in the main text rather than deferring it entirely to Appendix C.4, as it is a central result.","section":null},{"comment":"References: Some arXiv references appear to have future dates (e.g., 2026). These may be preprints with projected dates but should be checked for consistency.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The stress-test concern about the boosting step requiring distribution-free weak learnability is the most substantive issue to verify. On careful reading, the paper's Def. 8 quantifies over the family {D_i} which includes D_μ for every μ over z, and the reduction shows weak learnability (error ≤ 1/4) for every such D_μ. The key question is whether Schapire's theorem can be applied in this restricted-distribution setting. The standard formulation requires weak learnability under every distribution over the input domain. The paper's argument implicitly assumes that weak learnability under {D_i} suffices because the BQP computation only depends on z, and the distributions D_μ cover all distributions over z. This is a subtle point that deserves explicit justification. If the authors can clarify this step convincingly, the result stands; if not, the hardness claim may need to be weakened. This is the single most important point for the authors to address, but it is a clarification/justification issue rather than a fundamental error, hence minor revision rather than major."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful and constructive report. The referee's single major comment concerns whether the structured family of input distributions {D_μ} in Definition 7 suffices for the application of Schapire's boosting theorem in the classical hardness proof (Theorem 3, Appendix B.3). We address this below.","responses":[{"response":"We thank the referee for identifying this as the load-bearing step of the hardness argument. The referee's concern is that Schapire's boosting theorem requires distribution-free weak learnability, whereas our Definition 8 quantifies only over the structured family {D_i} of Definition 7, and the reduction in Eqs. (B135)–(B151) only establishes weak learnability under these structured distributions. We believe the argument as written is correct, and explain why the gap the referee identifies does not arise. The key observation is that the reduction in Appendix B.3 does not require the learner to be weakly learnable under arbitrary distributions over the full input domain (x, t). Rather, it requires that for every distribution μ over z ∈ {0,1}^m, there exists a distribution D_μ in the family {D_i} such that the learner achieves error ≤ 1/4 on the induced classifier h(z) under μ. This is precisely what Eqs. (B135)–(B151) establish: for any μ, one constructs D_μ ∈ {D_i} (by setting the bits z = x_2···x_{m+1} to follow μ when x_1 = 1, fixing the remaining bits to 0, and sampling t uniformly), and the PAC-learning guarantee from Definition 8 — which quantifies over all D_i ∈ {D_i} — then yields a hypothesis h(x,t) with low error under D_μ. Restricting to x_1 = 1 and averaging over t then produces the classifier h(z) with error ≤ 1/4 under μ (Eq. B151). Now, the crucial point is that μ was arbitrary. This means that for every distribution over the BQP input strings z, the learner produces a hypothesis that weakly learns the target Boolean function (the BQP language L) under that distribution. This is exactly the hypothesis of Schapire's theorem: the concept class being boosted is the class of Boolean functions {z ↦ sign(q(z))} corresponding to BQP computations, and the weak-学习r","revision_made":"partial","referee_comment":"Appendix B.3, proof of Theorem 3, Eqs. (B135)-(B151): The reduction from a hypothetical classical PAC-learner to a P/poly circuit for BQP proceeds by constructing, for any distribution μ over z ∈ {0,1}^m, a distribution D_μ from the family {D_i} of Def. 7, and showing the learner yields a hypothesis h(z) with error ≤ 1/4 under μ (Eq. B151). Schapire's boosting theorem is then invoked to promote this to strong learnability, implying BQP ⊆ P/poly. The load-bearing question is whether weak learnability under the distributions {D_μ} — which are structurally constrained (t uniform on [0,T], x_1 uniform, and conditioned on x_1=1, the bits z follow μ while remaining bits are fixed to 0) — suffices for the application of Schapire's theorem, which requires distribution-free weak learnability over the full input domain. The paper's Def. 8 is carefully formulated to quantify over {D_i}, making theP"}],"tokens_in":49175,"tokens_out":765,"duration_ms":290818,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper proves an exponential quantum-classical learning separation for predicting expectation values of time-evolved states under unknown low-intersection Hamiltonians with O(n) terms, extending beyond the O(log n)-parameter setting of prior work (Barthe et al., Ref. [24]). The separation is conditional on BQP not subset P/poly, which is standard. The quantum learner works by learning the Hamiltonian from short-time samples via a simplified Haah-Kothari-Tang protocol, then doing inference via Hamiltonian simulation and classical shadows. Classical hardness comes from embedding BQP-complete computations into the long-time dynamics of a low-intersection Feynman-Kitaev Hamiltonian (Oliveira-Terhal construction), combined with Schapire's boosting to promote a hypothetical classical learner to a P/poly circuit for BQP. The technical work is solid: the tail bound (Lemma 7), error propagation (Lemma 8), sample complexity analysis (Lemmas 9-12), and the full classical hardness reduction (Theorem 3, Appendix B) are worked out in detail. The simplified Hamiltonian learning algorithm exploiting randomized-time training data (Algorithm 1) is a genuine simplification over the Newton-Raphson inversion in Haah et al., made possible by the uniform time sampling. The observation that the Oliveira-Terhal FK Hamiltonian has constant-precision parameters (Lemma 2), enabling exact recovery and zero generalization error, is clean and useful. The paper is transparent about its limitations: the advantage is in evaluation (inference), not identification (training), and the training data model is stronger than in Ref. [24]. Now, the soft spots. The stress-test concern about the boosting step is worth addressing but I think it does not actually land. The concern is that Schapire's theorem requires distribution-free weak learnability, but the reduction only establishes weak learnability under distributions D_mu constrained by Def. 7. On reading the proof carefully, the key is that Def. 8 quantifies over the family {D_i}, and for any distribution mu over z, one constructs D_mu in that family. The PAC condition then yields a hypothesis with error at most 1/4 under mu (Eq. B.151). Since mu is arbitrary, this is distribution-free weak learnability of the BQP language L. The structural constraints on D_mu (fixing x_{m+2,...}=0, uniform t) do not restrict mu, so Schapire's theorem applies. The gap the stress-test worries about does not exist. The more genuine limitation is that the separation holds only for this specific family of distributions, not for all distributions over (x,t). A classical learner could in principle satisfy the PAC condition on all D_i while failing on distributions outside the family. The paper acknowledges this by defining hardness over {D_i}. This is a real but proportionate limitation — it is standard in learning separation papers to define the distribution class carefully. The training data model is strong (vector-valued labels enabling Hamiltonian learning), which the paper honestly flags as a limitation relative to Ref. [24]'s more frugal single-expectation-value labels. This is a fair trade-off: richer data for a more general Hamiltonian class. Who is this for? Researchers in quantum learning theory and quantum simulation. It connects Hamiltonian learning, PAC-learning, classical shadows, and complexity theory in a way that is technically sound and physically motivated. It deserves a serious referee. Recommend accept for peer review.","headline":"Provable quantum-classical learning separation for predicting time-evolution of low-intersection Hamiltonians with O(n) terms","tokens_in":50817,"tokens_out":785,"would_cite":true,"duration_ms":127905,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"Quantum learner predicts many-body dynamics where classical learner provably fails","keywords":[],"falsifier":"A randomized polynomial-time classical algorithm that, given the specified training data format (vectors of expectation values from short-time-evolved randomized stabilizer probes), produces a hypothesis satisfying the PAC-learning condition of Definition 8 with constant error below 1/48 for the BQP-hard Hamiltonian family and the specified family of input distributions.","tokens_in":49782,"feed_emoji":"⚛️","tokens_out":848,"duration_ms":160626,"temperature":0.7,"pith_summary":"This paper constructs a supervised learning task rooted in quantum physics — predicting expectation values of states evolved under an unknown low-intersection Hamiltonian — and proves that a quantum computer can learn it efficiently while no classical polynomial-time algorithm can, unless BQP ⊆ P/poly. The learning task works as follows: training data consists of randomized stabilizer probe states evolved for random times under an unknown Hamiltonian, labeled by vectors of expectation values. The quantum learner splits training into two phases. In the training phase, it uses only short-time samples to recover the Hamiltonian parameters via a simplified Hamiltonian learning protocol — this step is entirely classical. In the inference phase, it uses a quantum computer to simulate the learned Hamiltonian for potentially long evolution times and predicts expectation values via the classical shadows protocol. The classical hardness comes from embedding a BQP-complete computation into the long-time dynamics of a low-intersection variant of the Feynman-Kitaev clock Hamiltonian. Any classical learner that could predict expectation values for polynomially long evolution times would, via Schapire's boosting theorem, yield polynomial-size classical circuits for BQP-complete languages, implying BQP ⊆ P/poly. The separation thus arises not from the difficulty of identifying the Hamiltonian (which is classically learnable from short-time data) but from the difficulty of evaluating the learned concept at long times, where the dynamics encode quantum computation.","feed_headline":"Quantum learner predicts many-body dynamics classical ML provably cannot","feed_subtitle":"A physically motivated learning task where short-time data reveals the Hamiltonian but long-time prediction encodes BQP-complete computation","key_machinery":"low-intersection Feynman-Kitaev clock Hamiltonian whose Pauli coefficients take values in a fixed discrete set, enabling exact recovery from constant-precision estimates","core_discovery":"The paper identifies a specific structural feature that enables a clean quantum-classical learning separation: the distinction between identification and evaluation in PAC-learning. The Hamiltonian governing the dynamics can be recovered from short-time training data using only classical processing, because the first-order term in the time-expansion of certain expectation values directly exposes each Hamiltonian coefficient. This makes the training phase classically efficient. However, once the Hamiltonian is known, predicting its expectation values at polynomially long evolution times requires simulating dynamics that can encode BQP-complete computations. The low-intersection property of a ","pith_inferences":[],"forward_implications":["The separation framework could extend to other physical settings such as predicting properties of Gibbs states, where high-temperature samples enable Hamiltonian learning and low-temperature regimes ensure classical hardness.","The identification-versus-evaluation distinction suggests a taxonomy of quantum learning advantages: separations can arise from either hard-to-identify concepts or hard-to-evaluate concepts, and this paper realizes the latter type.","The result connects to learning-assisted certified quantum simulation: rather than certifying long-time dynamics directly, one can learn the Hamiltonian from short-time data and use a quantum computer for long-time prediction with rigorous guarantees.","The discrete coefficient structure of the hard Hamiltonian instance, which allows exact recovery and zero-error generalization, may inform the design of other provably learnable quantum concept classes."],"fun_headline_variants":["Quantum learner predicts many-body dynamics classical ML provably cannot","Learning quantum dynamics: provable separation between quantum and classical ML","PAC-learning task separates quantum from classical for many-body dynamics","Short-time training, long-time prediction: provable quantum-classical learning gap","Provably learnable quantum dynamics task resists classical polynomial time"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The classical hardness argument requires that the learning condition holds not just for a single fixed distribution but for a family of distributions where, conditioned on a flag bit, the remaining input bits follow an arbitrary distribution. This distribution-family requirement is what lets Schapire's boosting theorem convert a hypothetical classical learner into polynomial-size circuits for BQP. If the learning condition were restricted to one fixed distribution, the boost","fun_headline_variants_meta":{"raw":{"variants":["Quantum learner predicts many-body dynamics classical ML provably cannot","Learning quantum dynamics: provable separation between quantum and classical ML","PAC-learning task separates quantum from classical for many-body dynamics","Short-time training, long-time prediction: provable quantum-classical learning gap","Provably learnable quantum dynamics task resists classical polynomial time"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":751,"prompt_tokens":663,"completion_tokens":88,"prompt_tokens_details":null},"tokens_in":663,"tokens_out":88,"duration_ms":49986,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T04:38:44.947218+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A randomized polynomial-time classical algorithm that, given the specified training data format (vectors of expectation values from short-time-evolved randomized stabilizer probes), produces a hypothesis satisfying the PAC-learning condition of Definition 8 with constant error below 1/48 for the BQP-hard Hamiltonian family and the specified family of input distributions.","supporting_citations":[],"review_version":1}