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

arXiv: https://arxiv.org/abs/2607.06472 · HTML: https://mlsanity.com/paper/2607.06472/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 110 references that are in the map.
- First posted on arXiv 7 Jul 2026.

## Builds on (most cited first, 13 of 13)

- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Exponential separations between classical and quantum learners](https://mlsanity.com/paper/2306.16028/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Learning k-body Hamiltonians via compressed sensing](https://mlsanity.com/paper/2410.18928/) (2024)
- [Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms](https://mlsanity.com/paper/2405.18489/) (2024)
- [Towards efficient quantum algorithms for diffusion probabilistic models](https://mlsanity.com/paper/2502.14252/) (2025)
- [Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances](https://mlsanity.com/paper/2509.09813/) (2025)
- [Quantum Probe Tomography](https://mlsanity.com/paper/2510.08499/) (2025)
- [Testing and learning structured quantum Hamiltonians](https://mlsanity.com/paper/2411.00082/) (2024)
- [Improved algorithms for learning quantum Hamiltonians, via flat polynomials](https://mlsanity.com/paper/2407.04540/) (2024)
- [Optimal detection of dissipation in Lindbladian dynamics](https://mlsanity.com/paper/2603.17736/) (2026)
- [Heisenberg-limited Hamiltonian learning without short-time control](https://mlsanity.com/paper/2604.27838/) (2026)

## Built on by (most cited first, 1 of 1)

- [Cautious optimism for deep parameterized quantum circuits](https://mlsanity.com/paper/2607.21409/) (2026)

## Abstract (arXiv)

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(mathsfpoly(n))-time instances ensures classical hardness: by embedding a mathsfBQP-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 mathsfBQPsubseteqmathsfP/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.