Tolerant testing stabilizer states
<|reference_start|>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 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.<|reference_end|>
@article{arunachalam2024polynomial-time,
    title={Polynomial-time tolerant testing stabilizer states},
    author={Srinivasan Arunachalam, Arkopal Dutt},
    journal={arXiv preprint arXiv:2408.06289},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06289},
    primaryClass={quant-ph cs.CC cs.DS}
}