Molina Abel, Watrous John
Institute for Quantum Computing and School of Computer Science, University of Waterloo, Waterloo, Canada.
Proc Math Phys Eng Sci. 2019 Jun;475(2226):20180767. doi: 10.1098/rspa.2018.0767. Epub 2019 Jun 12.
Yao's 1995 publication 'Quantum circuit complexity' in , pp. 352-361, proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: ≥ steps of a quantum Turing machine running on an input of length can be simulated by a uniformly generated family of quantum circuits with size quadratic in , and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, which is the more challenging of the two simulation tasks, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in , rather than quadratic depth, and can be extended to variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of method described by Arright, Nesme and Werner in 2011 in , 372-378. (doi:10.1016/j.jcss.2010.05.004), that allows for the localization of causal unitary evolutions.
姚期智1995年发表于第352 - 361页的《量子电路复杂性》证明，量子图灵机和量子电路是多项式等价的计算模型：长度为(n)的输入上运行的量子图灵机的(T(n))步操作，可以由一族规模为(n^2)的均匀生成的量子电路模拟，并且一族多项式时间均匀生成的量子电路可以由在多项式时间内运行的量子图灵机模拟。我们重新审视用均匀生成的量子电路模拟量子图灵机这一问题，它是这两个模拟任务中更具挑战性的一个，并给出姚期智所采用模拟方法的一种变体及其分析。该分析表明，量子图灵机的模拟可以由深度为(n)线性而非二次的量子电路来执行，并且可以扩展到量子图灵机的变体，比如具有多维磁带的量子图灵机。我们的分析基于2011年阿莱特、内斯梅和维尔纳在第372 - 378页（doi:10.1016/j.jcss.2010.05.004）所描述方法的扩展，该扩展允许对因果酉演化进行局部化。
