# Stabiliser states are efficiently PAC-learnable

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 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)
- [Artificial intelligence for representing and characterizing quantum systems](https://mlsanity.com/paper/2509.04923/) (2025)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Learnability of the output distributions of local quantum circuits](https://mlsanity.com/paper/2110.05517/) (2021)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)
- [Learning Energy-Based Representations of Quantum Many-Body States](https://mlsanity.com/paper/2304.04058/) (2023)
- [Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP](https://mlsanity.com/paper/2204.06638/) (2022)

## Abstract (arXiv)

The exponential scaling of the wave function is a fundamental property of quantum systems with far reaching implications in our ability to process quantum information. A problem where these are particularly relevant is quantum state tomography. State tomography, whose objective is to obtain a full description of a quantum system, can be analysed in the framework of computational learning theory. In this model, quantum states have been shown to be Probably Approximately Correct (PAC)-learnable with sample complexity linear in the number of qubits. However, it is conjectured that in general quantum states require an exponential amount of computation to be learned. Here, using results from the literature on the efficient classical simulation of quantum systems, we show that stabiliser states are efficiently PAC-learnable. Our results solve an open problem formulated by Aaronson [Proc. R. Soc. A, 2088, (2007)] and propose learning theory as a tool for exploring the power of quantum computation.