# Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 52 references that are in the map.
- First posted on arXiv 22 May 2023.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Improved Stabilizer Estimation via Bell Difference Sampling](https://mlsanity.com/paper/2304.13915/) (2023)
- [(Pseudo) Random Quantum States with Binary Phase](https://mlsanity.com/paper/1906.10611/) (2019)
- [Fast and robust quantum state tomography from few basis measurements](https://mlsanity.com/paper/2009.08216/) (2020)
- [Optimal algorithms for learning quantum phase states](https://mlsanity.com/paper/2208.07851/) (2022)
- [Efficient Tomography of Non-Interacting Fermion States](https://mlsanity.com/paper/2102.10458/) (2021)
- [Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom](https://mlsanity.com/paper/2209.14530/) (2022)

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Artificial intelligence for representing and characterizing quantum systems](https://mlsanity.com/paper/2509.04923/) (2025)
- [On the sample complexity of purity and inner product estimation](https://mlsanity.com/paper/2410.12712/) (2024)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Mildly-Interacting Fermionic Unitaries are Efficiently Learnable](https://mlsanity.com/paper/2504.11318/) (2025)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and O(log n) non-Clifford gates. Specifically, for an n-qubit state |psirangle prepared with at most t non-Clifford gates, our algorithms use mathsfpoly(n,2t,1/varepsilon) time and copies of |psirangle to learn |psirangle to trace distance at most varepsilon. The first algorithm for this task is more efficient, but requires entangled measurements across two copies of |psirangle. The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension k if it is stabilized by an abelian group of 2k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.