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