# Polynomial-time tolerant testing stabilizer states

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2024.

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

- [Mildly-Interacting Fermionic Unitaries are Efficiently Learnable](https://mlsanity.com/paper/2504.11318/) (2025)

## Abstract (arXiv)

We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state |psirangle promised (i) |psirangle is varepsilon1-close to a stabilizer state in fidelity or (ii) |psirangle is varepsilon2-far from all stabilizer states, decide which is the case. We show that for every varepsilon1>0 and varepsilon2≤ varepsilon1C, there is a textsfpoly(1/varepsilon1)-sample and n· textsfpoly(1/varepsilon1)-time algorithm that decides which is the case (where C>1 is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-3 norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.