A New Model of Quantum Analogue Computation

点击翻译按钮获取中文摘要

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.