mlsanityData to 7 Oct 2026

Sample Complexity of Learning Parametric Quantum Circuits

arXiv 2107.09078 ↗First posted 19 Jul 2021quant-ph cs.LG math-phcited by 15

Not on the map. Why?

Abstract (arXiv)

Quantum computers hold unprecedented potentials for machine learning applications. Here, we prove that physical quantum circuits are PAC (probably approximately correct) learnable on a quantum computer via empirical risk minimization: to learn a parametric quantum circuit with at most nc gates and each gate acting on a constant number of qubits, the sample complexity is bounded by tildeO(nc+1). In particular, we explicitly construct a family of variational quantum circuits with O(nc+1) elementary gates arranged in a fixed pattern, which can represent all physical quantum circuits consisting of at most nc elementary gates. Our results provide a valuable guide for quantum machine learning in both theory and practice.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 6 of its 22 references that are in the map. First posted on arXiv 19 Jul 2021.

Builds on

6 of 22 references.

References · 6

  1. 2021Encoding-dependent generalization bounds for parametrized quantum circuitscited by 81
  2. 2016Optimal Quantum Sample Complexity of Learning Algorithmscited by 32
  3. 2021On the statistical complexity of quantum circuitscited by 25
  4. 2020Quantum statistical query learningcited by 19
  5. 2018Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problemcited by 16
  6. 2021A Theoretical Framework for Learning from Quantum Datacited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 1; 2022: 5; 2023: 4; 2024: 2; 2025: 2; 2026: 1.

15 papers.

Sort:

By area:

  1. 2021Generalization in quantum machine learning from few training datacited by 214
  2. 2022Exponential concentration in quantum kernel methodscited by 89
  3. 2022Out-of-distribution generalization for learning quantum dynamicscited by 49
  4. 2023Quantum Recurrent Neural Networks for Sequential Learningcited by 24
  5. 2022Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrixcited by 22
  6. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  7. 2022Problem-Dependent Power of Quantum Neural Networks on Multi-Class Classificationcited by 20
  8. 2022Dynamical simulation via quantum machine learning with provable generalizationcited by 15
  9. 2023Learning quantum states and unitaries of bounded gate complexitycited by 15
  10. 2023Generalization of Quantum Machine Learning Models Using Quantum Fisher Information Metriccited by 10
  11. 2024Comparative Performance Analysis of Quantum Machine Learning Architectures for Credit Card Fraud Detectioncited by 10
  12. 2023Transition Role of Entangled Data in Quantum Machine Learningcited by 5
3 more
  1. 2025Data re-uploading in Quantum Machine Learning for time series: application to traffic forecastingcited by 5
  2. 2025Quantum automated learning with provable and explainable trainabilitycited by 0
  3. 2026SAQNN: Spectral Adaptive Quantum Neural Network as a Universal Approximatorcited by 0