Towards tolerant testing stabilizer states

We consider the following task: suppose an algorithm is given copies of an unknown $n$-qubit quantum state $|\psi\rangle$ promised $(i)$ $|\psi\rangle$ is $\varepsilon_1$-close to a stabilizer state in fidelity or $(ii)$ $|\psi\rangle$ is $\varepsilon_2$-far from all stabilizer states, decide which is the case. We show two results: (i) Assuming $|\psi\rangle$ is a phase state, i.e., $|\psi\rangle=\frac{1}{\sqrt{2^n}}\sum \limits_{x \in \{0,1\}^n} {f(x)}|x\rangle$ where $f:\{0,1\}^n\rightarrow \{-1,1\}$, then we give a $\textsf{poly}(1/\varepsilon_1)$ sample and $n\cdot \textsf{poly}(1/\varepsilon_1)$ time algorithm for every $\varepsilon_1 > 0$ and $\varepsilon_2 \leq \textsf{poly}(\varepsilon_1)$, for tolerant testing stabilizer states. (ii) For arbitrary quantum states $|\psi\rangle$, assuming a conjecture in additive combinatorics, we give a $\textsf{poly}(1/\varepsilon_1)$-sample and $n\cdot \textsf{poly}(1/\varepsilon_1)$-time algorithm for this task for every $\varepsilon_1>0$ and $\varepsilon_2\leq 2^{-\textsf{poly}(1/\varepsilon_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.