论文标题
低稳定器 - 复杂量子状态不是伪态
Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
论文作者
论文摘要
我们表明，具有“低稳定器复杂性”的量子状态可以有效地与HAAR随机区分开。具体而言，给定$ n $ qubit的纯状态$ |ψ\ rangle $，我们给出了一种有效的算法，以区分$ |ψ\ rangle $是（i）haar-random还是（ii）（ii）具有稳定富度的状态，至少$ \ frac {1} {1} {k} $（i.e.稳定器状态），承诺就是其中之一。使用Black-box访问$ |ψ\ rangle $，我们的算法使用$ o \！\ left（k^{12}} \ log（1/δ）\右）$ copies of $ | |ψ\ rangle $ and $ o \！\！\！ $ |ψ\ rangle $（及其倒数）的状态准备工作，$ o \！\ left（k^{3} \ log（1/δ）\ right）$ QUERIES和$ o \！\！\！ 作为推论，我们证明$ω（\ log（n））$ $ t $ - 盖特对于任何Clifford+$ t $电路都是必需的，以准备计算上的pseudorandom量子态，这是一个首要的下限。
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.
