Pith. sign in

REVIEW 1 major objections 8 minor 122 references

Quantum learner predicts many-body dynamics where classical learner provably fails

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-08 04:38 UTC pith:NX2EQ4EU

load-bearing objection Provable quantum-classical learning separation for predicting time-evolution of low-intersection Hamiltonians with O(n) terms the 1 major comments →

arxiv 2607.06472 v1 pith:NX2EQ4EU submitted 2026-07-07 quant-ph cs.AIcs.LG

Provable learning separation for predicting time-evolution of quantum many-body systems

Rahul Bandyopadhyay , Riccardo Molteni , Jens Eisert , Vedran Dunjko , Sofiene Jerbi This is my paper
classification quant-ph cs.AIcs.LG
keywords quantumlearninghamiltonianmathsfclassicalmany-bodysimulationtraining
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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

What carries the argument

low-intersection Feynman-Kitaev clock Hamiltonian whose Pauli coefficients take values in a fixed discrete set, enabling exact recovery from constant-precision estimates

Load-bearing premise

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

What would settle it

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.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 8 minor

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).

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 (1)
  1. 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
minor comments (8)
  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: 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

    Authors: 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: partial

Circularity Check

0 steps flagged

No circularity found: the derivation chain is self-contained against external benchmarks

full rationale

The paper's two main results — quantum learnability (Theorem 1) and classical hardness (Theorem 2/3) — are built from independently verifiable external components, not from self-referential definitions or fitted inputs renamed as predictions. The quantum learning algorithm (Algorithm 1) uses a simplified variant of the Haah-Kothari-Tang Hamiltonian learning protocol [36], which is an independently published, peer-reviewed result with its own rigorous guarantees. The simplification (using time-averaged F_{a,t*} and linear approximation instead of Newton-Raphson) is a genuine modification that the paper justifies on its own terms via tail bounds (Lemma 7) and Hoeffding's inequality, not by citing the authors' own prior work as load-bearing. The classical hardness proof (Theorem 3, Appendix B.3) relies on three external results: the Oliveira-Terhal low-intersection Hamiltonian construction [37], Schapire's boosting theorem [93], and the standard Feynman-Kitaev clock construction. None of these are self-citations. The reduction chain proceeds: (1) embed BQP into Hamiltonian dynamics via [37]; (2) show a hypothetical PAC-learner yields weak learnability under distributions D_mu (Eq. B.151); (3) apply Schapire's theorem [93] to promote to strong learnability, implying BQP ⊆ P/poly. The potential concern flagged by the reader — that Schapire's theorem requires distribution-free weak learnability but the reduction only establishes it for distributions of the form D_mu — is a correctness/generality concern about whether the proof fully satisfies the theorem's hypotheses, not a circularity issue. The paper does not define its learning condition (Def. 8) in terms of the conclusion it seeks to prove; the condition quantifies over a family of distributions {D_i} that is defined independently (Def. 7), and the hardness argument shows that if a learner satisfies this condition, then BQP ⊆ P/poly follows as a logical consequence. The concept class (Def. 6) is defined in terms of Hamiltonian evolution, not in terms of the learning algorithm's output. The quantum learnability proof (Theorem 5) provides explicit sample and time complexity bounds (Eq. C62) derived from independent probabilistic arguments (Hoeffding, Chernoff, tail bounds), not from fitting parameters to the target output. No step in the derivation chain reduces to its inputs by construction. The self-citations present (e.g., Refs. [9, 21, 24, 25] by overlapping author groups) are contextual/related-work, not载

Axiom & Free-Parameter Ledger

4 free parameters · 6 axioms · 3 invented entities

The paper relies on standard complexity-theoretic conjectures (BQP ⊄ P/poly) and well-established results from quantum learning theory, Hamiltonian learning, and classical shadows. No ad hoc axioms or invented physical entities are introduced. The free parameters (t*, N, G, N_tilde) are all derived analytically from precision/confidence requirements, not fitted to data.

free parameters (4)
  • t* (short-time cutoff) = O(ε / (M·T·||O||_∞·(d+1)^2))
    Chosen in Algorithm 1 to control the tail bound error; not fitted to data but derived from the desired precision ε.
  • N (total sample complexity) = O(M^5·T^6·||O||^3·(d+1)^6 / ε^5 · log(M/δ))
    Derived analytically from Hoeffding and Chernoff bounds; not a fitted parameter.
  • G (classical shadows segments) = ceil(2·log(4M/δ))
    Standard classical shadows parameter, set by the failure probability budget.
  • N_tilde (inference copies) = O(1/ε^2 · log(M/δ))
    Standard classical shadows sample complexity, derived from median-of-means.
axioms (6)
  • domain assumption BQP ⊄ P/poly
    Invoked in Theorem 2/3 to establish classical hardness. This is a widely believed complexity-theoretic conjecture, standard in quantum advantage proofs.
  • standard math The Haah-Kothari-Tang Hamiltonian learning protocol [36] is correct and efficient
    Used as a subroutine in the training phase. The paper simplifies this protocol but relies on its core expansion (Eq. 6) and cluster-counting lemma (Lemma 6).
  • domain assumption The Oliveira-Terhal construction [37] yields a low-intersection FK Hamiltonian whose time-evolution simulates BQP-complete circuits
    Invoked in Section VI and Appendix B.1 to construct the classically hard Hamiltonian family H_BQP.
  • standard math Schapire's boosting theorem [93]: weak PAC-learnability under arbitrary distributions implies strong learnability and membership in P/poly
    Used in the proof of Theorem 3 to promote a hypothetical classical learner to a P/poly circuit for BQP.
  • domain assumption Efficient Hamiltonian simulation is possible for low-intersection local Hamiltonians
    Assumed in Algorithm 2 for the inference stage; standard result from quantum simulation literature.
  • standard math The classical shadows protocol [108] provides unbiased estimators with the stated sample complexity
    Used in Algorithm 2 and Lemma 12 for the inference stage.
invented entities (3)
  • Concept class C^H_{U_enc,T} (Def. 6) independent evidence
    purpose: Formalizes the learning task: predicting expectation values of time-evolved states under unknown low-intersection Hamiltonians.
    The concept class is a mathematical definition, not a physical entity. Its learnability is proven, not assumed.
  • Hamiltonian family H_BQP (Section VI) independent evidence
    purpose: The classically hard Hamiltonian family constructed from the Oliveira-Terhal low-intersection FK Hamiltonian.
    Constructed explicitly from known results; its properties (low-intersection, BQP-completeness of dynamics) are proven in Appendix B.
  • Family of input distributions D_i (Def. 7) independent evidence
    purpose: Specifies the distributional setting under which both quantum learnability and classical hardness hold.
    A mathematical definition; the hardness and learnability results are proven for this family.

pith-pipeline@v1.1.0-glm · 52477 in / 3652 out tokens · 546682 ms · 2026-07-08T04:38:44.947218+00:00 · methodology

0 comments
read the original abstract

Given that quantum computers are naturally suited to simulate the behavior of quantum many-body systems, an immediate question arises: can one formulate physically motivated quantum machine learning (QML) tasks that exhibit learning separations? We address this problem by studying the learnability of quantum many-body dynamics from the perspective of probably approximately correct (PAC)-learning. Concretely, we devise a supervised learning problem where the training set consists of specifications of randomized stabilizer probe states, evolution times sampled uniformly from a polynomially large time interval $[0,T]$, coupled with expectation values of certain observables evaluated on the resulting time-evolved state under an unknown Hamiltonian. For this learning task, we provide an efficient quantum procedure whose training phase learns the underlying Hamiltonian from short-time training samples, and whose deployment phase combines Hamiltonian simulation with the classical shadows protocol to perform inference on a newly given data point. By contrast, the existence of $O(\mathsf{poly}(n))$-time instances ensures classical hardness: by embedding a $\mathsf{BQP}$-complete computation into the polynomially long time-dynamics of a low-intersection variant of the Feynman-Kitaev clock Hamiltonian construction, we show that, for a certain family of input distributions, no randomized classical polynomial-time algorithm can fulfill our learning condition, unless $\mathsf{BQP}\subseteq\mathsf{P/poly}$. Furthermore, we show that the classically hard instance maintains quantum learnability. We also give an interpretation of our results in learning-assisted certified quantum simulation. Taken together, our results demonstrate a rigorous learning separation for a natural ML task based on Hamiltonian evolution, while building connections between quantum learning theory, quantum simulation, and QML.

Figures

Figures reproduced from arXiv: 2607.06472 by Jens Eisert, Rahul Bandyopadhyay, Riccardo Molteni, Sofiene Jerbi, Vedran Dunjko.

Figure 1
Figure 1. Figure 1: FIG. 1: A visualization of the key ideas of the present work. (a) Our training samples are generated by the time-evolution [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

122 extracted references · 122 canonical work pages · 28 internal anchors

  1. [1]

    We may therefore runAwith coefficient-estimation precision strictly smaller thanε ′ P /2

    In this case, the difference of the coefficients is εP = 1−e iπ/4 2 − 1√ 2 ≈0.66.(24) After accounting for the normalization factors introduced by the clock-register terms and the twoSWAPoperations, the minimum separation between two distinct admissible coefficients is lower-bounded byε ′ P =ε P /32. We may therefore runAwith coefficient-estimation precis...

    work page

  2. [2]

    switching on

    Then, working within the framework of Ref. [94], they consider aquantumPAC-learnerA, which is given examples of the form |ψc,D⟩ := X x∈{0,1}n p D(x)|x, c(x)⟩,(30) whereD:{0,1} n →[0,1]is an unknown distribution, taken to be fixed in Ref. [38] as opposed to arbitrary, and the learning criteria to be satisfied byAare analogous to those in Def. 1. Additional...

    work page doi:10.3030/101124342

  3. [3]

    P. W. Shor, Proc. 50th Ann. Symp. Found. Comp. Sc. , 124 (1994)

    work page 1994

  4. [4]

    Mind the gaps: The fraught road to quantum advantage

    J. Eisert and J. Preskill, arXiv (2026), arXiv:2510.19928

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  5. [5]

    The vast world of quantum advantage

    H.-Y . Huang, S. Choi, J. R. McClean, and J. Preskill, arXiv (2025), arXiv:2508.05720

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  6. [6]

    Pirnay, V

    N. Pirnay, V . Ulitzsch, F. Wilde, J. Eisert, and J.-P. Seifert, Science Adv.10, eadj5170 (2024)

    work page 2024

  7. [7]

    S. P. Jordan, N. Shutty, M. Wootters, A. Zalcman, A. Schmidhuber, R. King, S. V . Isakov, T. Khattar, and R. Babbush, Nature 646, 831836 (2025)

    work page 2025

  8. [8]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. B ¨artschi, H. Buhrman, C. Coffrin, G. Cortiana, V . Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling, S. Gupta, S. Hadfield, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Korpas, S. Lenk, J. Marecek, V . Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nannici...

    work page 2024

  9. [9]

    Sweke, J.-P

    R. Sweke, J.-P. Seifert, D. Hangleiter, and J. Eisert, Quantum5, 417 (2021)

    work page 2021

  10. [10]

    Y . Liu, S. Arunachalam, and K. Temme, Nature Phys.17, 1013 (2021)

    work page 2021

  11. [13]

    J. Liu, M. Liu, J.-P. Liu, Z. Ye, Y . Wang, Y . Alexeev, J. Eisert, and L. Jiang, Nature Comm.15, 434 (2024)

    work page 2024

  12. [14]

    Lloyd, Science273, 1073 (1996)

    S. Lloyd, Science273, 1073 (1996)

    work page 1996

  13. [15]

    Georgescu, S

    I. Georgescu, S. Ashhab, and F. Nori, Rev. Mod. Phys.86, 153185 (2014)

    work page 2014

  14. [16]

    A. M. Childs, D. Maslov, Y . Nam, N. J. Ross, and Y . Su, Proc. Natl. Ac. Sc.115, 94569461 (2018)

    work page 2018

  15. [17]

    A. J. Daley, I. Bloch, C. Kokail, S. Flannigan, N. Pearson, M. Troyer, and P. Zoller, Nature607, 667 (2022)

    work page 2022

  16. [18]

    Flannigan, N

    S. Flannigan, N. Pearson, G. H. Low, A. Buyskikh, I. Bloch, P. Zoller, M. Troyer, and A. J. Daley, Quant. Sc. Tech.7, 045025 (2022)

    work page 2022

  17. [19]

    Trivedi, A

    R. Trivedi, A. Franco Rubio, and J. I. Cirac, Nature Comm.15, 6507 (2024)

    work page 2024

  18. [20]

    Kashyap, G

    V . Kashyap, G. Styliaris, S. Mouradian, J. I. Cirac, and R. Trivedi, Phys. Rev. X15, 021017 (2025)

    work page 2025

  19. [21]

    J. Rao, J. Eisert, and T. Guaita, arXiv (2025), arXiv:2510.08467

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  20. [22]

    Y . Wang, R. Jiang, Y . Fan, X. Jia, J. Eisert, J. Liu, and J.-P. Liu, arXiv (2025), arXiv:2502.14252

    work page arXiv 2025

  21. [23]

    Exponential separations between classical and quantum learners

    C. Gyurik and V . Dunjko, arXiv (2024), arXiv:2306.16028

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  22. [24]

    Molteni, C

    R. Molteni, C. Gyurik, and V . Dunjko, npj Quant. Inf.12, 19 (2026)

    work page 2026

  23. [25]

    Molteni, S

    R. Molteni, S. C. Marshall, and V . Dunjko, arXiv (2026), arXiv:2504.15964

    work page arXiv 2026

  24. [26]

    Quantum Advantage in Learning Quantum Dynamics via Fourier coefficient extraction

    A. Barthe, M. Y . Rad, M. Grossi, and V . Dunjko, arXiv (2025), arXiv:2506.17089

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  25. [27]

    Bokov, L

    V . Bokov, L. Kohl, S. Schmitt, and V . Dunjko, arXiv (2026), arXiv:2601.22006

    work page arXiv 2026

  26. [28]

    R. P. Feynman, Found. Phys.16, 507 (1986)

    work page 1986

  27. [29]

    Huang, R

    H.-Y . Huang, R. Kueng, G. Torlai, V . V . Albert, and J. Preskill, Science377, 6613 (2022)

    work page 2022

  28. [30]

    Lewis, H.-Y

    L. Lewis, H.-Y . Huang, V . T. Tran, S. Lehner, R. Kueng, and J. Preskill, Nature Comm.15, 895 (2024)

    work page 2024

  29. [31]

    Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms

    M. Wanner, L. Lewis, C. Bhattacharyya, D. Dubhashi, and A. Gheorghiu, arXiv (2024), arXiv:2405.18489

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  30. [32]

    Rouz ´e, D

    C. Rouz ´e, D. Stilck Franc ¸a, E. Onorati, and J. D. Watson, Nature Comm.15, 7755 (2024)

    work page 2024

  31. [33]

    J. I. Cirac and P. Zoller, Nature Phys.8, 264 (2012)

    work page 2012

  32. [34]

    Bloch, J

    I. Bloch, J. Dalibard, and S. Nascimbene, Nature Phys.8, 267 (2012)

    work page 2012

  33. [35]

    I. M. Georgescu, S. Ashhab, and F. Nori, Rev. Mod. Phys.86, 153 (2014)

    work page 2014

  34. [36]

    Probing the relaxation towards equilibrium in an isolated strongly correlated 1D Bose gas

    S. Trotzky, Y .-A. Chen, A. Flesch, I. P. McCulloch, U. Schollw ¨ock, J. Eisert, and I. Bloch, Nature Phys.8, 325 (2012), arXiv:1101.2659

    work page internal anchor Pith review Pith/arXiv arXiv 2012

  35. [37]

    Bakshi, A

    A. Bakshi, A. Liu, A. Moitra, and E. Tang, in2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)(IEEE, 2024) p. 10371050

    work page 2024

  36. [38]

    J. Haah, R. Kothari, and E. Tang, Nature Phys.20, 10271031 (2024)

    work page 2024

  37. [39]

    The complexity of quantum spin systems on a two-dimensional square lattice

    R. Oliveira and B. M. Terhal, arXiv (2005), arXiv:quant-ph/0504050

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  38. [40]

    Arunachalam, A

    S. Arunachalam, A. B. Grilo, and A. Sundaram, SIAM J. Comp.50, 972 (2021)

    work page 2021

  39. [41]

    Provably Efficient Learning of Phases of Matter via Dissipative Evolutions

    E. Onorati, C. Rouz ´e, D. S. Franc ¸a, and J. D. Watson, arXiv (2023), arXiv:2311.07506

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  40. [42]

    Coser and D

    A. Coser and D. Prez-Garca, Quantum3, 174 (2019)

    work page 2019

  41. [43]

    Learning to predict arbitrary quantum processes

    H.-Y . Huang, S. Chen, and J. Preskill, arXiv (2023), arXiv:2210.14894

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  42. [44]

    Huang, R

    H.-Y . Huang, R. Kueng, and J. Preskill, Phys. Rev. Lett.126, 190505 (2021)

    work page 2021

  43. [45]

    S. Chen, J. Cotler, H.-Y . Huang, and J. Li, arXiv (2021), arXiv:2111.05881

    work page internal anchor Pith review Pith/arXiv arXiv 2021

  44. [46]

    Huang, M

    H.-Y . Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Science376, 11821186 (2022)

    work page 2022

  45. [47]

    Aharonov, J

    D. Aharonov, J. Cotler, and X.-L. Qi, Nature Comm.13, 887 (2022)

    work page 2022

  46. [48]

    Vapnik and A

    V . Vapnik and A. Vashist, Neur. Net.22, 544 (2009)

    work page 2009

  47. [49]

    Vapnik and R

    V . Vapnik and R. Izmailov, J. Mach. Learn. Res.16, 2023 (2015)

    work page 2023

  48. [50]

    Exponential quantum advantages in learning quantum observables from classical data

    R. Molteni, C. Gyurik, and V . Dunjko, arXiv (2024), arXiv:2405.02027. 20

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  49. [51]

    N. F. Ramsey, Phys. Rev.78, 695 (1950)

    work page 1950

  50. [52]

    C. M. Caves, Phys. Rev. D23, 1693 (1981)

    work page 1981

  51. [53]

    M. J. Holland and K. Burnett, Phys. Rev. Lett.71, 1355 (1993)

    work page 1993

  52. [54]

    H. Lee, P. Kok, and J. P. Dowling, J. Mod. Opt.49, 23252338 (2002)

    work page 2002

  53. [55]

    Giovannetti, S

    V . Giovannetti, S. Lloyd, and L. Maccone, Science306, 1330 (2004)

    work page 2004

  54. [56]

    de Burgh and S

    M. de Burgh and S. D. Bartlett, Phys. Rev. A72, 042301 (2005)

    work page 2005

  55. [57]

    C. L. Degen, F. Reinhard, and P. Cappellaro, Rev. Mod. Phys.89, 035002 (2017)

    work page 2017

  56. [58]

    J. R. Garrison and T. Grover, Phys. Rev. X8, 021026 (2018)

    work page 2018

  57. [59]

    Bairey, I

    E. Bairey, I. Arad, and N. H. Lindner, Phys. Rev. Lett.122, 020504 (2019)

    work page 2019

  58. [60]

    Qi and D

    X.-L. Qi and D. Ranard, Quantum3, 159 (2019)

    work page 2019

  59. [61]

    Z. Li, L. Zou, and T. H. Hsieh, Phys. Rev. Lett.124, 160502 (2020)

    work page 2020

  60. [62]

    Anshu, S

    A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar, Nature Phys.17, 931 (2021)

    work page 2021

  61. [63]

    Testing and learning structured quantum Hamiltonians

    S. Arunachalam, A. Dutt, and F. E. Gutirrez, arXiv (2025), arXiv:2411.00082

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  62. [65]

    Fawzi, O

    H. Fawzi, O. Fawzi, and S. O. Scalet, Nature Comm.15, 7394 (2024)

    work page 2024

  63. [66]

    L. P. Garca-Pintos, K. Bharti, J. Bringewatt, H. Dehghani, A. Ehrenberg, N. Yunger Halpern, and A. V . Gorshkov, Phys. Rev. Lett.133, 040802 (2024)

    work page 2024

  64. [67]

    Improved algorithms for learning quantum Hamiltonians, via flat polynomials

    S. Narayanan, arXiv (2024), arXiv:2407.04540

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  65. [68]

    S. Chen, J. Cotler, and H.-Y . Huang, arXiv (2025), arXiv:2510.08499

    work page arXiv 2025

  66. [69]

    Hangleiter, I

    D. Hangleiter, I. Roth, J. Fuksa, J. Eisert, and P. Roushan, Nature Comm.15, 9595 (2024)

    work page 2024

  67. [70]

    Wilde, A

    F. Wilde, A. Kshetrimayum, I. Roth, D. Hangleiter, R. Sweke, and J. Eisert, Mach. Learn. Sc. Tech.11, 035002 (2026)

    work page 2026

  68. [71]

    M. C. Caro, ACM Trans. Quant. Comp.5, 153 (2024)

    work page 2024

  69. [72]

    M. P. da Silva, O. Landon-Cardinal, and D. Poulin, Phys. Rev. Lett.107, 210404 (2011)

    work page 2011

  70. [73]

    Flynn, A

    B. Flynn, A. A. Gentile, N. Wiebe, R. Santagati, and A. Laing, New J. Phys.24, 053034 (2022)

    work page 2022

  71. [74]

    D. S. Franc ¸a, T. M¨obus, C. Rouz´e, and A. H. Werner, arXiv (2025), arXiv:2510.08500

    work page arXiv 2025

  72. [75]

    A. A. Gentile, B. Flynn, S. Knauer, N. Wiebe, S. Paesani, C. E. Granade, J. G. Rarity, R. Santagati, and A. Laing, Nature Phys.17, 837 (2021)

    work page 2021

  73. [76]

    H.-Y . Hu, M. Ma, W. Gong, Q. Ye, Y . Tong, S. T. Flammia, and S. F. Yelin, PRX Quantum6, 040315 (2025)

    work page 2025

  74. [77]

    Huang, Y

    H.-Y . Huang, Y . Tong, D. Fang, and Y . Su, Phys. Rev. Lett.130, 200403 (2023)

    work page 2023

  75. [78]

    H. Li, Y . Tong, H. Ni, T. Gefen, and L. Ying, arXiv (2023), arXiv:2307.04690

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  76. [79]

    Kraft, M

    T. Kraft, M. K. Joshi, W. Lam, T. Olsacher, F. Kranzl, J. Franke, L. K. Joshi, R. Blatt, A. Smerzi, D. S. Frana, B. Vermersch, B. Kraus, C. F. Roos, and P. Zoller, arXiv (2025), arXiv:2511.23392

    work page arXiv 2025

  77. [80]

    M. Ma, S. T. Flammia, J. Preskill, and Y . Tong, arXiv (2024), arXiv:2410.18928

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  78. [81]

    Mirani and P

    A. Mirani and P. Hayden, Phys. Rev. A110, 062421 (2024)

    work page 2024

  79. [82]

    H. Ni, H. Li, and L. Ying, arXiv (2024), arXiv:2312.17390

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  80. [83]

    Odake, H

    T. Odake, H. Kristjnsson, A. Soeda, and M. Murao, Phys. Rev. Res.6, l012063 (2024)

    work page 2024

Showing first 80 references.