A New Model of Quantum Analogue Computation

1985年，David Deutsch引入了量子图灵机（简称QTMs）作为图灵机，可以执行所谓的量子并行计算。然后，在1994年，Peter Shor证明了QTM可以在多项式时间内分解任意小误差概率的整数。由于人们普遍认为任何确定性图灵机都不能在多项式时间内分解整数，因此QTM很可能是一种本质上新的计算模型。另一方面，许多研究人员正在研究如何在物理上实现量子计算机。在本研究中，我们提出了一个量子模拟计算模型来解决已知是np完全的图3-可色性问题。我们的计算机模拟表明，由于许多原因，该模型为量子计算机的实现提供了一个有吸引力的前景。

In 1985, David Deutsch introduced quantum Turing machines (QTMs for short) as Turing machines which can perform so called quantum parallel computations. Then, in 1994, Peter Shor showed that QTM can factor integers with arbitrary small error probability in polynomial time. Since it is widely believed that any deterministic Turing machines cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation. On the other hand, many researchers are studying how to physically implement quantum computers. In this research, we propose a quantum analogue computation model solving the graph 3-colorability problem which is known to be NP-complete. Our computer simulation shows that this model offers an appealing prospect for implementation of quantum computers because of a number of reasons.