Noisy quantum learning theory

While known quantum learning speedups operate in idealized noiseless regimes, coupling to uncharacterized systems is a noisy process even given fault-tolerant devices. Here we show that noise can eliminate exponential quantum advantages of unphysical, noiseless learners, while demonstrating more nuanced directions towards meaningful quantum speedups in noisy experiments. We introduce the complexity class $\mathrm{NBQP}$ ("noisy BQP"), modeling noisy fault-tolerant quantum computers that cannot generally error-correct the oracle systems they query. We prove that while natural $\mathrm{NBQP}$ learners may be exponentially weaker than their idealized counterparts, a superpolynomial gap remains between $\mathrm{NISQ}$ and fault-tolerant devices. Turning to canonical learning tasks, we find that the exponential advantage for purity testing collapses under local depolarizing noise. We then analyze noisy Pauli tomography, deriving lower bounds characterizing how instance size, quantum memory and noise jointly control sample complexity. We further study noise-dependent limitations on Heisenberg-limited metrology. Nevertheless, we identify a setting in which physical structure restores the purity testing speedup and highlight a noise-dependent polynomial speedup for Pauli tomography. Our results demonstrate that the primitives underlying quantum-enhanced experiments are fundamentally fragile to noise, and that realizing meaningful quantum advantages in future experiments will require interfacing noise-robust physics with available algorithmic techniques.