# On the Hardness of PAC-learning Stabilizer States with Noise

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 47 references that are in the map.
- First posted on arXiv 9 Feb 2021.

## Builds on (most cited first, 10 of 10)

- [An Equivalence Between Private Classification and Online Prediction](https://mlsanity.com/paper/2003.00563/) (2020)
- [Superpolynomial Lower Bounds for Learning One-Layer Neural Networks using Gradient Descent](https://mlsanity.com/paper/2006.12011/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Optimal Quantum Sample Complexity of Learning Algorithms](https://mlsanity.com/paper/1607.00932/) (2016)
- [Statistical Queries and Statistical Algorithms: Foundations and Applications](https://mlsanity.com/paper/2004.00557/) (2020)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [The Learnability of Unknown Quantum Measurements](https://mlsanity.com/paper/1501.00559/) (2015)
- [Stabiliser states are efficiently PAC-learnable](https://mlsanity.com/paper/1705.00345/) (2017)
- [Experimental learning of quantum states](https://mlsanity.com/paper/1712.00127/) (2017)

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Learnability of the output distributions of local quantum circuits](https://mlsanity.com/paper/2110.05517/) (2021)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [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)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)

## Abstract (arXiv)

We consider the problem of learning stabilizer states with noise in the Probably Approximately Correct (PAC) framework of Aaronson (2007) for learning quantum states. In the noiseless setting, an algorithm for this problem was recently given by Rocchetto (2018), but the noisy case was left open. Motivated by approaches to noise tolerance from classical learning theory, we introduce the Statistical Query (SQ) model for PAC-learning quantum states, and prove that algorithms in this model are indeed resilient to common forms of noise, including classification and depolarizing noise. We prove an exponential lower bound on learning stabilizer states in the SQ model. Even outside the SQ model, we prove that learning stabilizer states with noise is in general as hard as Learning Parity with Noise (LPN) using classical examples. Our results position the problem of learning stabilizer states as a natural quantum analogue of the classical problem of learning parities: easy in the noiseless setting, but seemingly intractable even with simple forms of noise.