Learning stabilizer structure of quantum states

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|² 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^k2\). As far as we know, learning arbitrary states with even stabilizer-rank 2 was unknown.