Quantum Advantage for Learning Sparse Parities with a Single Clean Qubit

arXiv:2505.09343

A. Chen, M. Patel, S. Okada

We prove a rigorous learning-theoretic separation showing that a quantum learner with access to a single clean qubit and mixed states can efficiently learn sparse parity functions that remain hard for classical algorithms under standard cryptographic assumptions.