School of Mathematical Sciences, Zhejiang University, Hangzhou, Zhejiang 310027, China.
Department of Physics, Harvard University, Cambridge, Massachusetts 02138, USA.
Phys Rev Lett. 2019 Oct 25;123(17):170502. doi: 10.1103/PhysRevLett.123.170502.
We investigate the problem of evaluating the output probabilities of Clifford circuits with nonstabilizer product input states. First, we consider the case when the input state is mixed, and give an efficient classical algorithm to approximate the output probabilities, with respect to the l_{1} norm, of a large fraction of Clifford circuits. The running time of our algorithm decreases as the inputs become more mixed. Second, we consider the case when the input state is a pure nonstabilizer product state, and show that a similar efficient algorithm exists to approximate the output probabilities, when a suitable restriction is placed on the number of qubits measured. This restriction depends on a magic monotone that we call the Pauli rank. We apply our results to give an efficient output probability approximation algorithm for some restricted quantum computation models, such as Clifford circuits with solely magic state inputs, Pauli-based computation, and instantaneous quantum polynomial time circuits. Finally, we discuss the relationship between Pauli rank and stabilizer rank.
我们研究了评估非稳定子乘积输入态 Clifford 电路输出概率的问题。首先，当输入态是混合态时，我们考虑了一种有效率的经典算法来逼近输出概率，在 l_{1} 范数下，我们对很大一部分 Clifford 电路进行了近似。当输入变得更加混合时，我们算法的运行时间会减少。其次，当输入态是纯非稳定子乘积态时，我们表明存在一种类似的有效算法来逼近输出概率，当对测量的量子比特数施加适当的限制时。这个限制取决于我们称之为 Pauli 秩的一个魔术单调。我们应用我们的结果来给出一些受限量子计算模型的有效输出概率逼近算法，例如仅具有魔术态输入的 Clifford 电路、基于 Pauli 的计算和瞬时量子多项式时间电路。最后，我们讨论了 Pauli 秩和稳定子秩之间的关系。
