On Quantum Learning Advantage Under Symmetries

Symmetry underlies many of the most effective classical and quantum learning algorithms, yet whether quantum learners can gain a fundamental advantage under symmetry-imposed structures remains an open question. Based on evidence that classical statistical query $SQ$ frameworks have revealed exponential query complexity in learning symmetric function classes, we ask: can quantum learning algorithms exploit the problem symmetry better? In this work, we investigate the potential benefits of symmetry within the quantum statistical query $QSQ$ model, which is a natural quantum analog of classical SQ. Our results uncover three distinct phenomena: (i) we obtain an exponential separation between QSQ and SQ on a permutation-invariant function class; (ii) we establish query complexity lower bounds for QSQ learning that match, up to constant factors, the corresponding classical SQ lower bounds for most commonly studied symmetries; however, the potential advantages may occur under highly skewed orbit distributions; and (iii) we further identify a tolerance-based separation exists, where quantum learners succeed at noise levels that render classical SQ algorithms ineffective. Together, these findings provide insight into when symmetry can enable quantum advantage in learning.