{"ID":6029866,"CreatedAt":"2026-07-08T02:57:47.77373338Z","UpdatedAt":"2026-07-10T16:20:48.775981082Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06472","arxiv_id":"2607.06472","title":"Provable learning separation for predicting time-evolution of quantum many-body systems","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.","short_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...","url_abs":"https://arxiv.org/abs/2607.06472","url_pdf":"https://arxiv.org/pdf/2607.06472v1","authors":"[\"Rahul Bandyopadhyay\",\"Riccardo Molteni\",\"Jens Eisert\",\"Vedran Dunjko\",\"Sofiene Jerbi\"]","published":"2026-07-07T16:30:09Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.AI\",\"cs.LG\"]","methods":"[]","has_code":false}