# Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 29 references that are in the map.
- First posted on arXiv 29 Sep 2022.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [(Pseudo) Random Quantum States with Binary Phase](https://mlsanity.com/paper/1906.10611/) (2019)
- [Optimal algorithms for learning quantum phase states](https://mlsanity.com/paper/2208.07851/) (2022)

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements](https://mlsanity.com/paper/2308.07175/) (2023)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an n-qubit pure state |psirangle, we give an efficient algorithm that distinguishes whether |psirangle is (i) Haar-random or (ii) a state with stabilizer fidelity at least frac1k (i.e., has fidelity at least frac1k with some stabilizer state), promised that one of these is the case. With black-box access to |psirangle, our algorithm uses O!left( k12 log(1/δ)right) copies of |psirangle and O!left(n k12 log(1/δ)right) time to succeed with probability at least 1-δ, and, with access to a state preparation unitary for |psirangle (and its inverse), O!left( k3 log(1/δ)right) queries and O!left(n k3 log(1/δ)right) time suffice. As a corollary, we prove that ω(log(n)) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.