Polynomial-time tolerant testing stabilizer states

We consider the following task: suppose an algorithm is given copies of an unknown $n$ qubit quantum state $\ket{\phi}$ promised $(i)$ $\ket{\phi}$ is $\varepsilon_1$-close to a stabilizer state in fidelity or $(ii)$ $\ket{\phi}$ is $\varepsilon_2$-far from all stabilizer states, decide which is the case. We show that for every $\varepsilon_1)>0$ and $\varepsilon_2$ ≤ $\varepsilon_1{C}$ there is a poly $(1/\varepsilon_1)$ sample and $n$ poly $(1/\varepsilon_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.