Provably Efficient Machine Learning for Quantum Many-Body Problems
summary
Proves that classical ML using classical shadow (randomized Pauli) can learn ground states and phases for smooth families of geometrically local Hamiltonians with a constant spectral gap, using training size polynomial in the number of control parameters and independent of system size; each training example can be one single-shot measurement per training point, yields constant average error ε with training/prediction time polynomial in m and linear in n, and shows a provable separation: a non-ML polynomial algorithm achieving the same would solve NP-complete problems in randomized poly time. Introduces a shadow kernel computed in O(n T^2); numerics: 20–100 training points match DMRG and unsupervised clustering finds phases while CNNs fail on topological cases.
AI-written summary · about