Rahul Bandyopadhyay, Riccardo Molteni, Jens Eisert, Vedran Dunjko, Sofiene Jerbi
This theoretical study proves a quantum-classical learning separation for predicting the time evolution of quantum many-body systems. It shows that learning the dynamics under an unknown Hamiltonian is efficiently possible for a quantum algorithm but generally hard for a classical algorithm, embedding a BQP-complete computation.
Given that quantum computers are naturally suited for simulating quantum many-body systems, it is crucial to determine if physically motivated QML tasks exhibit learning separations. Specifically, it must be proven whether learning quantum dynamics under an unknown Hamiltonian is quantumly efficient but classically hard.
From a PAC-learning perspective, a supervised learning task is devised using randomized stabilizer probe states, uniformly sampled evolution times, and expectation values of observables. An efficient quantum procedure is presented that learns the Hamiltonian from short-time training samples and performs inference using Hamiltonian simulation combined with the classical shadows protocol. Classical hardness is proven by embedding a BQP-complete computation into a low-intersection variant of the Feynman-Kitaev clock Hamiltonian.
The study presents a quantum procedure that learns in polynomial time and proves that no classical polynomial-time algorithm can satisfy the learning condition for a certain input distribution family unless BQP ⊆ P/poly. It also shows that the classically hard instance remains quantumly learnable. These results demonstrate a rigorous learning separation for a natural ML task based on Hamiltonian evolution, building connections between quantum learning theory, quantum simulation, and QML.