Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines
| dc.creator | Qiu, Daowen | |
| dc.date | 2005-01-30 | |
| dc.date | 2005-06-06 | |
| dc.date.accessioned | 2026-07-07T06:12:03Z | |
| dc.date.available | 2026-07-07T06:12:03Z | |
| dc.description | 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. | |
| dc.description | 25 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0501176 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0501176 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92672 | |
| dc.subject | Quantum Physics | |
| dc.title | Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines | |
| dc.type | text |