这篇论文给量子机器学习找了个硬核任务：预测多体系统时间演化，量子算法能学，经典学不了，除非BQP进P/poly。理论结果很扎实。
该研究从PAC学习角度研究量子多体动力学可学习性。他们设计了一个监督学习任务：训练集包含随机稳定子探针态、均匀采样自[0,T]的演化时间以及特定可观测量期望值。量子算法通过短时训练样本学习未知哈密顿量，并结合哈密顿量模拟与经典阴影协议进行推理。通过将BQP完全计算嵌入Feynman-Kitaev时钟哈密顿量的长时间动力学，他们证明除非BQP⊆P/poly，否则没有经典多项式时间算法能完成该任务。同时经典困难实例仍保持量子可学习性。
Provable learning separation for predicting time-evolution of quantum many-body systems
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.