Learning stabilizer structure of quantum states

We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|\psi\rangle$: for $\epsilon > 0$, output a state $|\phi\rangle$ with stabilizer-rank $\textsf{poly}(1/\epsilon)$ such that $|\psi\rangle=|\phi\rangle+|\phi'\rangle$ where $|\phi'\rangle$ has stabilizer fidelity $< \epsilon$. We first show the existence of such decompositions using the recently established inverse theorem for the Gowers-3 norm of states [AD,STOC'25].

To learn this structure, we initiate the task of self-correction of a state $|\psi\rangle$ with respect to a class of states $S$: given copies of $|\psi\rangle$ which has fidelity $\geq \tau$ with a state in $S$, output $|\phi\rangle \in S$ with fidelity $|\langle \phi | \psi \rangle|^2 \geq \tau^C$ for a constant $C>1$. Assuming the algorithmic polynomial Frieman-Rusza (APFR) conjecture in the high doubling regime (whose combinatorial version was recently resolved [GGMT,Annals of Math.'25]), we give a polynomial-time algorithm for self-correction of stabilizer states. Given access to the state preparation unitary $U_\psi$ for $|\psi\rangle$ and its controlled version $cU_\psi$, we give a polynomial-time protocol that learns a structured decomposition of $|\psi\rangle$. Without assuming APFR, we give a quasipolynomial-time protocol for the same task.

As our main application, we give learning algorithms for states $|\psi\rangle$ promised to have stabilizer extent $\xi$, given access to $U_\psi$ and $cU_\psi$. We give a protocol that outputs $|\phi\rangle$ which is constant-close to $|\psi\rangle$ in time $\textsf{poly}(n,\xi^{\log \xi})$, which can be improved to polynomial-time assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank $k$ states in time $\textsf{poly}(n,k^{k^2})$. As far as we know, learning arbitrary states with even stabilizer-rank 2 was unknown.