Physics – Quantum Physics
Scientific paper
2005-01-30
Physics
Quantum Physics
25 pages
Scientific paper
As was well known, in classical computation, Turing machines, circuits, multi-stack machines, and multi-counter machines are equivalent, that is, they can simulate each other in polynomial time. In quantum computation, Yao [11] first proved that for any quantum Turing machines $M$, there exists quantum Boolean circuit $(n,t)$-simulating $M$, where $n$ denotes the length of input strings, and $t$ is the number of move steps before machine stopping. However, the simulations of quantum Turing machines by quantum multi-stack machines and quantum multi-counter machines have not been considered, and quantum multi-stack machines have not been established, either. Though quantum counter machines were dealt with by Kravtsev [6] and Yamasaki {\it et al.} [10], in which the machines count with $0,\pm 1$ only, we sense that it is difficult to simulate quantum Turing machines in terms of this fashion of quantum computing devices, and we therefore prove that the quantum multi-counter machines allowed to count with $0,\pm 1,\pm 2,...,\pm n$ for some $n>1$ can efficiently simulate quantum Turing machines. Therefore, our mail goals are to establish quantum multi-stack machines and quantum multi-counter machines with counts $0,\pm 1,\pm 2,...,\pm n$ and $n>1$, and particularly to simulate quantum Turing machines by these quantum computing devices.
No associations
LandOfFree
Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-349052