Tolerant Testing of Stabilizer States with a Polynomial Gap via a Generalized Uncertainty Relation

We prove a conjecture of Arunachalam & Dutt [3] on the existence of a tolerant stabilizer testing algorithm, and achieve an exponential improvement in the parameters of the tester. Key to our argument is a generalized uncertainty relation for sets of Pauli operators, based on the Lovász theta function. CCS Concepts • Theory of computation → Quantum complexity theory.