Title: Polynomial-time tolerant testing stabilizer states
Abstract: We study the problem of testing whether an unknown n-qubit quantum state |yñ is e1-close to a stabilizer state in fidelity or e2 far from all stabilizer states, promised one of them is the case. Our main result is a tolerant testing algorithm that, given copies of |yñ, accomplishes the above task using poly(1/e1) sample complexity and n × poly(1/e1) time complexity for every e1 > 0 and e2 £ e1C (where C is a universal constant).
To establish the above result, we give a new definition of Gowers norm for quantum states and prove an inverse theorem for the Gowers-3 norm of quantum states which asserts that quantum states that have high Gowers-3 norm must necessarily have high fidelity with a stabilizer state. In the process, we also give new bounds on stabilizer coverings of structured subsets of Paulis.