# Improved Stabilizer Estimation via Bell Difference Sampling

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2023.

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

- [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)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation](https://mlsanity.com/paper/2408.06967/) (2024)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Mildly-Interacting Fermionic Unitaries are Efficiently Learnable](https://mlsanity.com/paper/2504.11318/) (2025)
- [Efficient learning of bosonic Gaussian unitaries](https://mlsanity.com/paper/2510.05531/) (2025)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements](https://mlsanity.com/paper/2308.07175/) (2023)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)

## Abstract (arXiv)

We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: - We prove that Omega(n) T-gates are necessary for any Clifford+T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. - Given an n-qubit pure quantum state |psirangle that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ - varepsilon. The algorithm uses O(n/(varepsilon2τ4)) samples and expleft(O(n/τ4)right) / varepsilon2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the na"ive exp(O(n2))-time brute-force algorithm over all stabilizer states. - In the special case of τ > cos2(π/8), we show that a modification of the above algorithm runs in polynomial time. - We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.