Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond
Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond
复制标题
量子计算的经典模拟、戈特斯曼-尼尔定理以及稍稍超出的定理
DOI：
10.26421/qic10.3-4-6
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
M. Nest
中科院分区：
文献类型：
--
作者：
M. Nest
我们以Gottesman-Knill定理为出发点，研究量子计算的经典模拟。我们展示了如何每个克利福德电路可以减少到一个等效的，显然可模拟的电路（正常形式）。这提供了一个简单的证明Gottesman-Knill定理，而不诉诸稳定器技术。正规形式强调了为什么Clifford电路的计算能力如此有限，尽管它们的纠缠能力很高。同时，规范形式显示了克利福德电路的经典模拟如何适合于将经典计算嵌入量子电路模型的标准方式。这导致简单的扩展Clifford电路是经典的模拟。这些电路可以有效地模拟经典采样（“弱模拟”），即使精确计算这些电路的测量结果（“强模拟”）的问题被证明是P-完全的，从而表明量子计算的弱和强经典模拟之间存在分离。
We study classical simulation of quantum computation, taking the Gottesman-Knilltheorem as a starting point. We show how each Clifford circuit can be reduced to anequivalent, manifestly simulatable circuit (normal form). This provides a simple proofof the Gottesman-Knill theorem without resorting to stabilizer techniques. The normalform highlights why Clifford circuits have such limited computational power in spiteof their high entangling power. At the same time, the normal form shows how theclassical simulation of Clifford circuits fits into the standard way of embedding classicalcomputation into the quantum circuit model. This leads to simple extensions of Cliffordcircuits which are classically simulatable. These circuits can be efficiently simulated byclassical sampling ("weak simulation") even though the problem of exactly computingthe outcomes of measurements for these circuits ("strong simulation") is proved to be#P-complete-thus showing that there is a separation between weak and strong classicalsimulation of quantum computation.