Improved simulation of stabilizer circuits
Improved simulation of stabilizer circuits
复制标题
DOI：
10.1103/physreva.70.052328
复制
发表时间：
2004-11-01
影响因子：
2.9
通讯作者：
Gottesman, D
中科院分区：
文献类型：
--
作者：
Aaronson, S;Gottesman, D
哥特斯曼-克尼尔定理说，稳定器电路--即只由受控非门(CNOT)、阿达玛门和相位门组成的量子电路--可以在经典计算机上高效地进行模拟。本文从几个方面对该定理进行了改进。首先，通过消除高斯消除的需要，我们使模拟算法更快，但代价是表示状态所需的比特数增加了2倍。我们已经在一个免费的程序CHP(CNOT-Hadamard-PASE)中实现了改进的算法，该程序可以很容易地处理数千个量子比特。其次，我们证明了对于经典复杂性类+L，稳定器电路的模拟问题是完全的，这意味着稳定器电路对于经典计算甚至可能不是通用的。第三，我们给出了计算两个稳定器状态之间的内积的有效算法，将任何n个量子比特的稳定器电路放入至多需要O(n(2)/logn)门的“典范形式”，以及其他有用的任务。第四，我们将我们的模拟算法扩展到作用于混合态的电路、包含有限数量的非稳定器门的电路以及作用于一般张量积初始状态但仅包含有限数量测量的电路。
The Gottesman-Knill theorem says that a stabilizer circuit - that is, a quantum circuit consisting solely of controlled-NOT (CNOT), Hadamard, and phase gates - can be simulated efficiently on a classical computer. This paper improves that theorem in several directions. First, by removing the need for Gaussian elimination, we make the simulation algorithm much faster at the cost of a factor of 2 increase in the number of bits needed to represent a state. We have implemented the improved algorithm in a freely available program called CHP (CNOT-Hadamard-phase), which can handle thousands of qubits easily. Second, we show that the problem of simulating stabilizer circuits is complete for the classical complexity class +L, which means that stabilizer circuits are probably not even universal for classical computation. Third, we give efficient algorithms for computing the inner product between two stabilizer states, putting any n-qubit stabilizer circuit into a "canonical form" that requires at most O(n(2) /log n) gates, and other useful tasks. Fourth, we extend our simulation algorithm to circuits acting on mixed states, circuits containing a limited number of nonstabilizer gates, and circuits acting on general tensor-product initial states but containing only a limited number of measurements.