Learning stabilizer structure of quantum states

Abstract

We consider the task of learning a structured stabilizer decomposition of an arbitrary $n$-qubit quantum state $|ψ\rangle$: for $ε> 0$, output a state $|φ\rangle$ with stabilizer-rank $\textsf{poly}(1/ε)$ such that $|ψ\rangle=|φ\rangle+|φ'\rangle$ where $|φ'\rangle$ has stabilizer fidelity $< ε$. 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 $|ψ\rangle$ with respect to a class of states $S$: given copies of $|ψ\rangle$ which has fidelity $\geq τ$ with a state in $S$, output $|φ\rangle \in S$ with fidelity $|\langle φ| ψ\rangle|^2 \geq τ^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_ψ$ for $|ψ\rangle$ and its controlled version $cU_ψ$, we give a polynomial-time protocol that learns a structured decomposition of $|ψ\rangle$. Without assuming APFR, we give a quasipolynomial-time protocol for the same task. As our main application, we give learning algorithms for states $|ψ\rangle$ promised to have stabilizer extent $ξ$, given access to $U_ψ$ and $cU_ψ$. We give a protocol that outputs $|φ\rangle$ which is constant-close to $|ψ\rangle$ in time $\textsf{poly}(n,ξ^{\log ξ})$, 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.