Current von Neumann-type computers are implemented based on Turing machines introduced by Alan Turing in 1936. Since Turing machine is a very simple and stable model of computation, it is used as a standard model in recursive function theory and computational complexity theory. Many results in complexity theory, however, suggests that deterministic Turing machines cannot efficiently solve hard combinatorial problems, such as NP-complete problems.
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 machine cannot factor integers in polynomial time, it is very likely that QTM is an essentially new model of computation.
Advantages of the QTM
Every finitery realizable physical system can be perfectly simulatedby a QTM.A computer based on the QTM may be capable of dissipating verysmall amount of energy per step.
Faster computations via quantum parallelism :
Deutsch and Jozsa found a problem such that QTM can solvefaster than any other classical models of computation.
Shor showed that a QTM can factor integers and find discrete logarithms in polynomial time with a bounded probability of error.
A Theory of NMR Quantum Computation
Many researchers are studying how to physically implement quantum computers based on QTM. In fact, the methods using iron traps, a single photon, or quantum dots are proposed to realize basic elements of quantum computers. Among others, NMR (Nuclear Magnetic Resonance) offers an appealing prospect for implementation of quantum computers because of a number of reasons. But, so-called bulk quantum computations performed on NMR quantum computers are slightly different from those performed on QTMs. We are developing a theory of bulk quantum computation such as NMR (Nuclear Magnetic Resonance) quantum computation.
Tetsuro Nishino, Takao Shima, Hiroshi Shibata, and Kenji Atsumi : A Theory of Bulk Quantum Computation.
A QTM Simulation of a Non-Linear Quantum Algorithm
D. S. Abrams and S. Lloyd adopted some non-linear transformations in quantum computation based on non-standard Weinberg’s non-linear quantum mechanics. And, they designed an algorithm to solve NP-complete problems in polynomial time. We have shown that the algorithm designed by Abrams and Lloyd can be simulated by a deterministic Turing machine in polynomial space. This suggests that their algorithm, which is based on non-standard quantum mechanics, can be simulated by a standard QTM with exponential time slow down.
Naoki Kanada and Tetsuro Nishino :A Linear Space Simulation of a Nonlinear Quantum Algorithm forNP-Complete Problems.