Improved Stabilizer Estimation Via Bell Difference Sampling

Abstract

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 $\Omega (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 $|\psi ⟩$ that has fidelity at least $\tau$ with some stabilizer state, we give an algorithm that outputs a succinct description of a stabilizer state that witnesses fidelity at least $\tau -ϵ$. The algorithm uses $O(n/({ϵ}^2{\tau }^4))$ samples and $\exp \left(O(n/{\tau }^4)\right)/{ϵ}^2$ time. In the regime of $\tau$ constant, this algorithm estimates stabilizer fidelity substantially faster than the na\"ive $\exp (O(n^2))$-time brute-force algorithm over all stabilizer states.