Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
This addresses the challenge of characterizing pseudorandomness in quantum computing, providing a foundational lower bound that impacts cryptographic and complexity theory applications.
The paper tackles the problem of distinguishing quantum states with low stabilizer complexity from Haar-random states, showing an efficient algorithm that uses O(k^12 log(1/δ)) copies and O(n k^12 log(1/δ)) time to succeed with probability at least 1-δ, and proves that ω(log(n)) T-gates are necessary for Clifford+T circuits to prepare pseudorandom quantum states.
We show that quantum states with "low stabilizer complexity" can be efficiently distinguished from Haar-random. Specifically, given an $n$-qubit pure state $|ψ\rangle$, we give an efficient algorithm that distinguishes whether $|ψ\rangle$ is (i) Haar-random or (ii) a state with stabilizer fidelity at least $\frac{1}{k}$ (i.e., has fidelity at least $\frac{1}{k}$ with some stabilizer state), promised that one of these is the case. With black-box access to $|ψ\rangle$, our algorithm uses $O\!\left( k^{12} \log(1/δ)\right)$ copies of $|ψ\rangle$ and $O\!\left(n k^{12} \log(1/δ)\right)$ time to succeed with probability at least $1-δ$, and, with access to a state preparation unitary for $|ψ\rangle$ (and its inverse), $O\!\left( k^{3} \log(1/δ)\right)$ queries and $O\!\left(n k^{3} \log(1/δ)\right)$ time suffice. As a corollary, we prove that $ω(\log(n))$ $T$-gates are necessary for any Clifford+$T$ circuit to prepare computationally pseudorandom quantum states, a first-of-its-kind lower bound.