Another Quantum Turing Machines

The quantum Turing machines by Bernstein & Vazirani are based on vectors and matrices as in quantum mechanics, so that it is difficult to make clear difference between the quantum Turing machines and the usual probabilistic Turing machines. This paper gives another formulation which can make difference clear. We consider that the superposition of configurations, a basic concept of the quantum Turing machines, should also be applied to the probabilistic Turing machines. From this viewpoint we first give a new definition of the probabilistic Turing machines. Then we define the quantum Turing machine as an extension of the probabilistic Turing machine. We show the relationship between Bernstein & Vazirani's definition and ours. In both types of the quantum Turing machines there still remains another difficulty that the machines are required to be time-bounded in order for users to get results explicitly from the machines. We overcome this difficulty by modifying our quantum Turing machines, and show that our new machines can solve the satisfiability and the validity problems in polynomial time.