Polynomial-time tolerant testing stabilizer states

We consider the following task: suppose an algorithm is given copies of an unknown $n$-qubit quantum state $\mathrm{\mid }\psi ⟩$ promised $(i)$ $\mathrm{\mid }\psi ⟩$ is ${\epsilon }_1$-close to a stabilizer state in fidelity or $(ii)$ $\mathrm{\mid }\psi ⟩$ is ${\epsilon }_2$-far from all stabilizer states, decide which is the case. We show that for every ${\epsilon }_1>0$ and ${\epsilon }_2\le {\epsilon }_1^C$, there is a $\mathsf{\text{poly}}(1\mathrm{/}{\epsilon }_1)$-sample and $n\cdot \mathsf{\text{poly}}(1\mathrm{/}{\epsilon }_1)$-time algorithm that decides which is the case (where $C>1$ is a universal constant). Our proof includes a new definition of Gowers norm for quantum states, an inverse theorem for the Gowers-$3$ norm of quantum states and new bounds on stabilizer covering for structured subsets of Paulis using results in additive combinatorics.