STOC Conference 2024 Conference Paper
Improved Stabilizer Estimation via Bell Difference Sampling
- Sabee Grewal
- Vishnu Iyer
- William Kretschmer
- Daniel Liang
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism and obtain the following results: We prove that Ω( n ) T -gates are necessary for any Clifford+ T circuit to prepare computationally pseudorandom quantum states, an exponential improvement over the previously known bound. This bound is asymptotically tight if linear-time quantum-secure pseudorandom functions exist. Given an n -qubit pure quantum state |ψ⟩ that has fidelity at least τ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least τ − ε. The algorithm uses O ( n /(ε 2 τ 4 )) samples and exp( O ( n /τ 4 )) / ε 2 time. In the regime of τ constant, this algorithm estimates stabilizer fidelity substantially faster than the naive exp( O ( n 2 ))-time brute-force algorithm over all stabilizer states. In the special case of τ > cos 2 (π/8), we show that a modification of the above algorithm runs in polynomial time. We exhibit a tolerant property testing algorithm for stabilizer states. The underlying algorithmic primitive in all of our results is Bell difference sampling. To prove our results, we establish and/or strengthen connections between Bell difference sampling, symplectic Fourier analysis, and graph theory.