Improved Bounds for Testing Low Stabilizer Complexity States

Abstract

Stabilizer states are fundamental families of quantum states with crucial applications such as error correction, quantum computation, and simulation of quantum circuits. In this paper, we study the problem of testing how close or far a quantum state is to a stabilizer state. We make two contributions: First, we improve the state-of-the-art parameters for the tolerant testing of stabilizer states. In particular, we show that there is an efficient quantum primitive to distinguish if the maximum fidelity of a quantum state with a stabilizer state is ≥ є1 or ≤ є2, given one of them is the case, provided that є2 ≤ є1O(1). This result improves the parameters in the previous work which assumed є2 ≤ e− 1/є1O(1). Our proof technique extends the toolsets developed in before by applying a random Clifford map which balances the characteristic function of a quantum state, enabling the use of standard proof techniques from higher-order Fourier analysis for Boolean functions, where improved testing bounds are available. Second, we study the problem of testing low stabilizer rank states. We show that if for an infinite family of quantum states stabilizer rank is lower than a constant independent of system size, then stabilizer fidelity is lower bounded by an absolute constant. Using a result on estimating stabilizer fidelity of quantum states, one of the implications of this result is that low approximate stabilizer rank states are not pseudo-random.