On Quantum Learning Advantage Under Symmetries

• URL: http://arxiv.org/abs/2602.02008v2
• Date: Tue, 03 Feb 2026 08:05:53 GMT
• Title: On Quantum Learning Advantage Under Symmetries
• Authors: Tuyen Nguyen, Mária Kieferová, Amira Abbas,
• Abstract summary: We investigate the potential benefits of symmetry within the quantum statistical query ($QSQ$) model.<n>We find that potential advantages may occur under highly skewed orbit distributions.<n>We further identify a tolerance-based separation exists, where quantum learners succeed at noise levels that render classical $SQ$ algorithms ineffective.
• Score: 0.4434230652503028
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• NISQ Security and Complexity via Simple Classical Reasoning [41.17296890645859]
  We give novel lifting theorems for security games in the quantum random oracle model (QROM) in Noisy Intermediate-Scale Quantum (NISQ) settings.<n>We provide, for the first time, a hybrid lifting theorem for hybrid algorithms that can perform both quantum and classical queries.<n>We derive the first direct product theorems in the average case, in the hybrid setting-i.e., an enabling tool to determine the hybrid hardness of solving multi-instance security games.
  arXiv  Detail & Related papers  (2025-09-11T23:31:39Z)
• Non-perturbative switching rates in bistable open quantum systems: from driven Kerr oscillators to dissipative cat qubits [72.41778531863143]
  We use path integral techniques to predict the switching rate in a single-mode bistable open quantum system.<n>Our results open new avenues for exploring switching phenomena in multistable single- and many-body open quantum systems.
  arXiv  Detail & Related papers  (2025-07-24T18:01:36Z)
• Solving graph problems using permutation-invariant quantum machine learning [35.99391901074448]
  In quantum machine learning, the ansatz can be tuned to correspond to the specific symmetry of the problem.<n>We show how the symmetry can be included in the quantum circuit in a straightforward constructive method.
  arXiv  Detail & Related papers  (2025-05-19T06:44:03Z)
• Quantum Algorithms for Stochastic Differential Equations: A Schrödingerisation Approach [29.662683446339194]
  We propose quantum algorithms for linear differential equations.<n>The gate complexity of our algorithms exhibits an $mathcalO(dlog(Nd))$ dependence on the dimensions.<n>The algorithms are numerically verified for the Ornstein-Uhlenbeck processes, Brownian motions, and one-dimensional L'evy flights.
  arXiv  Detail & Related papers  (2024-12-19T14:04:11Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  We take inspiration from Kearns' SQ oracle and Valiant's weak evaluation oracle. We introduce an extensive yet intuitive framework that yields unconditional lower bounds for learning from evaluation queries.
  arXiv  Detail & Related papers  (2023-10-26T18:23:21Z)
• Classical Verification of Quantum Learning [42.362388367152256]
  We develop a framework for classical verification of quantum learning. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents.
  arXiv  Detail & Related papers  (2023-06-08T00:31:27Z)
• SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture [11.404166974371197]
  SnCQA is a set of hardware-efficient variational circuits of equivariant quantum convolutional circuits. Our quantum neural networks are suitable for solving machine learning problems where permutation symmetries are present.
  arXiv  Detail & Related papers  (2022-11-23T05:16:26Z)
• Symmetric Pruning in Quantum Neural Networks [111.438286016951]
  Quantum neural networks (QNNs) exert the power of modern quantum machines. QNNs with handcraft symmetric ansatzes generally experience better trainability than those with asymmetric ansatzes. We propose the effective quantum neural tangent kernel (EQNTK) to quantify the convergence of QNNs towards the global optima.
  arXiv  Detail & Related papers  (2022-08-30T08:17:55Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Learning quantum symmetries with interactive quantum-classical variational algorithms [0.0]
  A symmetry of a state $vert psi rangle$ is a unitary operator of which $vert psi rangle$ is an eigenvector. symmetries provide key physical insight into the quantum system. We develop a variational hybrid quantum-classical learning scheme to systematically probe for symmetries of $vert psi rangle$.
  arXiv  Detail & Related papers  (2022-06-23T20:41:26Z)
• Testing symmetry on quantum computers [3.481985817302898]
  In quantum information and beyond, it is known that quantum states possessing symmetry are not useful for certain information-processing tasks. This paper details several quantum algorithms that test the symmetry of quantum states and channels.
  arXiv  Detail & Related papers  (2021-05-26T18:01:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.