Tolerant Testing of Stabilizer States with Mixed State Inputs

We study the problem of tolerant testing of stabilizer states. In particular, we give the first such algorithm that accepts mixed state inputs. Formally, given a mixed state ρ that either has fidelity at least varepsilon1 with some stabilizer pure state or fidelity at most varepsilon2 with all such states, where varepsilon2 ≤ varepsilon1O(1), our algorithm distinguishes the two cases with sample complexity poly(1/varepsilon1) and time complexity O(n · poly(1/varepsilon1)).