# Classical Verification of Quantum Learning

arXiv: https://arxiv.org/abs/2306.04843 · HTML: https://mlsanity.com/paper/2306.04843/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 31 of its 97 references that are in the map.
- First posted on arXiv 8 Jun 2023.

## Builds on (most cited first, 30 of 31)

- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [On the Quantum versus Classical Learnability of Discrete Distributions](https://mlsanity.com/paper/2007.14451/) (2020)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Pseudo-dimension of quantum circuits](https://mlsanity.com/paper/2002.01490/) (2020)
- [Testing distributional assumptions of learning algorithms](https://mlsanity.com/paper/2204.07196/) (2022)
- [A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity](https://mlsanity.com/paper/2211.13312/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Efficient Testable Learning of Halfspaces with Adversarial Label Noise](https://mlsanity.com/paper/2303.05485/) (2023)
- [An Efficient Tester-Learner for Halfspaces](https://mlsanity.com/paper/2302.14853/) (2023)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [The Complexity of NISQ](https://mlsanity.com/paper/2210.07234/) (2022)
- [Private quantum computation: An introduction to blind quantum computing and related protocols](https://mlsanity.com/paper/1611.10107/) (2016)
- [The Learnability of Unknown Quantum Measurements](https://mlsanity.com/paper/1501.00559/) (2015)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [Two new results about quantum exact learning](https://mlsanity.com/paper/1810.00481/) (2018)
- [Learning low-degree functions from a logarithmic number of random queries](https://mlsanity.com/paper/2109.10162/) (2021)
- [Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes](https://mlsanity.com/paper/2211.09101/) (2022)
- [PAC Verification of Statistical Algorithms](https://mlsanity.com/paper/2211.17096/) (2022)
- [Binary Classification with Classical Instances and Quantum Labels](https://mlsanity.com/paper/2006.06005/) (2020)
- [Optimal lower bounds for Quantum Learning via Information Theory](https://mlsanity.com/paper/2301.02227/) (2023)
- [Verification of quantum computation: An overview of existing approaches](https://mlsanity.com/paper/1709.06984/) (2017)

## Built on by (most cited first, 6 of 6)

- [Quantum delegated and federated learning via quantum homomorphic encryption](https://mlsanity.com/paper/2409.19359/) (2024)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Quantum Artificial Intelligence for Mission-Critical Systems: Foundations, Architectural Elements, and Future Directions](https://mlsanity.com/paper/2511.09884/) (2025)
- [Protocols for Verifying Smooth Strategies in Bandits and Games](https://mlsanity.com/paper/2507.10567/) (2025)
- [The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)](https://mlsanity.com/paper/2602.01054/) (2026)

## Abstract (arXiv)

Quantum data access and quantum processing can make certain classically intractable learning tasks feasible. However, quantum capabilities will only be available to a select few in the near future. Thus, reliable schemes that allow classical clients to delegate learning to untrusted quantum servers are required to facilitate widespread access to quantum learning advantages. Building on a recently introduced framework of interactive proof systems for classical machine learning, we develop a framework for classical verification of quantum learning. We exhibit learning problems that a classical learner cannot efficiently solve on their own, but that they can efficiently and reliably solve when interacting with an untrusted quantum prover. Concretely, we consider the problems of agnostic learning parities and Fourier-sparse functions with respect to distributions with uniform input marginal. We propose a new quantum data access model that we call "mixture-of-superpositions" quantum examples, based on which we give efficient quantum learning algorithms for these tasks. Moreover, we prove that agnostic quantum parity and Fourier-sparse learning can be efficiently verified by a classical verifier with only random example or statistical query access. Finally, we showcase two general scenarios in learning and verification in which quantum mixture-of-superpositions examples do not lead to sample complexity improvements over classical data. Our results demonstrate that the potential power of quantum data for learning tasks, while not unlimited, can be utilized by classical agents through interaction with untrusted quantum entities.