Tolerant testing stabilizer states

We consider the following task: suppose an algorithm is given copies of an unknown n-qubit quantum state |ψ promised $(i)$ |ψ is ε₁-close to a stabilizer state in fidelity or $(ii)$ |ψ is ε₂-far from all stabilizer states, decide which is the case. We give a poly(1/ε₁)-sample and n· poly(1/ε₁)-time algorithm for this task for every ε₁>0 and ε₂≤ 2-poly(1/ε₁). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.