# Clifford Circuits can be Properly PAC Learned if and only if textsfRP=textsfNP

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 51 references that are in the map.
- First posted on arXiv 13 Apr 2022.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [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)
- [Complexity theoretic limitations on learning DNF's](https://mlsanity.com/paper/1404.3378/) (2014)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [Private learning implies quantum stability](https://mlsanity.com/paper/2102.07171/) (2021)
- [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)
- [Quantum hardness of learning shallow classical circuits](https://mlsanity.com/paper/1903.02840/) (2019)

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)

## Abstract (arXiv)

Given a dataset of input states, measurements, and probabilities, is it possible to efficiently predict the measurement probabilities associated with a quantum circuit? Recent work of Caro and Datta (2020) studied the problem of PAC learning quantum circuits in an information theoretic sense, leaving open questions of computational efficiency. In particular, one candidate class of circuits for which an efficient learner might have been possible was that of Clifford circuits, since the corresponding set of states generated by such circuits, called stabilizer states, are known to be efficiently PAC learnable (Rocchetto 2018). Here we provide a negative result, showing that proper learning of CNOT circuits is hard for classical learners unless textsfRP = textsfNP. As the classical analogue and subset of Clifford circuits, this naturally leads to a hardness result for Clifford circuits as well. Additionally, we show that if textsfRP = textsfNP then there would exist efficient proper learning algorithms for CNOT and Clifford circuits. By similar arguments, we also find that an efficient proper quantum learner for such circuits exists if and only if textsfNP subseteq textsfRQP.