2025/10/07 by Arunachalam, Srinivasan, Dutt, Arkopal
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2510.05890
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 \textsfpoly(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 |⟨ ϕ| ψ⟩|2 ≥ τ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 \textsfpoly(n,ξlog ξ), which can be improved to polynomial-time assuming APFR. This gives an unconditional learning algorithm for stabilizer-rank k states in time \textsfpoly(n,kk2). As far as we know, learning arbitrary states with even stabilizer-rank 2 was unknown.