# Stabilizer bootstrapping: A recipe for efficient agnostic tomography and magic estimation

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 66 references that are in the map.
- First posted on arXiv 13 Aug 2024.

## 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)
- [Information-theoretic bounds on quantum advantage in machine learning](https://mlsanity.com/paper/2101.02464/) (2021)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [Quantum state certification](https://mlsanity.com/paper/1708.06002/) (2017)
- [Improved Stabilizer Estimation via Bell Difference Sampling](https://mlsanity.com/paper/2304.13915/) (2023)
- [Optimal learning of quantum Hamiltonians from high-temperature Gibbs states](https://mlsanity.com/paper/2108.04842/) (2021)

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

- [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)
- [The Stabilizer Bootstrap of Quantum Machine Learning with up to 10000 qubits](https://mlsanity.com/paper/2412.11356/) (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 study the task of agnostic tomography: given copies of an unknown n-qubit state ρ which has fidelity τ with some state in a given class C, find a state which has fidelity ≥ τ - ε with ρ. We give a new framework, stabilizer bootstrapping, for designing computationally efficient protocols for this task, and use this to get new agnostic tomography protocols for the following classes: Stabilizer states: We give a protocol that runs in time poly(n,1/ε)· (1/τ)O(log(1/τ)), answering an open question posed by Grewal, Iyer, Kretschmer, Liang [43] and Anshu and Arunachalam [6]. Previous protocols ran in time exp(Theta(n)) or required τ>cos2(π/8). States with stabilizer dimension n - t: We give a protocol that runs in time n3·(2t/τ)O(log(1/ε)), extending recent work on learning quantum states prepared by circuits with few non-Clifford gates, which only applied in the realizable setting where τ = 1 [33, 40, 49, 66]. Discrete product states: If C = Kotimes n for some μ-separated discrete set K of single-qubit states, we give a protocol that runs in time (n/μ)O((1 + log (1/τ))/μ)/ε2. This strictly generalizes a prior guarantee which applied to stabilizer product states [42]. For stabilizer product states, we give a further improved protocol that runs in time (n2/ε2)· (1/τ)O(log(1/τ)). As a corollary, we give the first protocol for estimating stabilizer fidelity, a standard measure of magic for quantum states, to error ε in n3 quasipoly(1/ε) time.