Learning Stabilizer Structure of Quantum States

We consider the task of learning a structured stabilizer decomposition of an arbitrary n-qubit quantum state |ψ⟩: for every ε > 0, output a succinctly describable state |ϕ⟩ with stabilizerrank poly(1/ε) such that |ψ⟩ = |ϕ⟩ + |ϕ ′ ⟩ where |ϕ ′ ⟩ has stabilizer fidelity at most ε. We firstly show the existence of such decompositions using the inverse theorem for the Gowers-3 norm of quantum states that was recently established [AD25, STOC'25].

Algorithmizing the inverse theorem is key to learning such a decomposition. To this end, we initiate the task of self-correction of a state |ψ⟩ with respect to the class of states C: given copies of |ψ⟩ which has fidelity ≥ τ with a state in C, output |ϕ⟩ ∈ C with fidelity |⟨ϕ|ψ⟩| 2 ≥ Ω(τ C ) for some constant C > 1. Assuming the algorithmic polynomial Frieman-Rusza (APFR) conjecture in the high-doubling regime (whose combinatorial version was resolved in a recent breakthrough [GGMT25, Annals of Math.'25]), we give a poly(n, 1/ε)-time algorithm for selfcorrection of stabilizer states.

Given access to the state preparation unitary U ψ for |ψ⟩ and its controlled version conU ψ , we give a poly(n, 1/ε)-time protocol that learns a structured stabilizer decomposition of |ψ⟩. Without assuming APFR, we give a poly(n, (1/ε) log 1/ε )-time protocol for the same task. Our techniques extend to finding structured decompositions over high stabilizer-dimension states, by giving a new tolerant tester for these states.

As our main application, we give learning algorithms for states |ψ⟩ promised to have stabilizer extent ξ, given access to U ψ and conU ψ . We give a protocol that outputs |ϕ⟩ which is constantclose to |ψ⟩ in time poly(n, ξ log ξ ), which can be improved to poly(n, ξ) assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank κ states in time poly(n, κ κ 2 ). As far as we know, efficient learning arbitrary states with even stabilizer-rank κ ≥ 2 was unknown.