dorsal/arxiv
View SchemaSimulations of Quantum Turing Machines by Quantum Multi-Stack Machines
| Authors | Daowen Qiu |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0501176 |
| URL | https://arxiv.org/abs/quant-ph/0501176 |
Abstract
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.
{
"annotation_id": "277387eb-ae32-44cf-9c47-1b5b1896f0c4",
"date_created": "2026-03-02T18:02:13.523000Z",
"date_modified": "2026-03-02T18:02:13.523000Z",
"file_hash": "3d06f0843bc8cd845e594b89308c6d77f405925e974db9de37b7cfd81dad44d8",
"private": false,
"record": {
"abstract": "As was well known, in classical computation, Turing machines, circuits,\nmulti-stack machines, and multi-counter machines are equivalent, that is, they\ncan simulate each other in polynomial time. In quantum computation, Yao [11]\nfirst proved that for any quantum Turing machines $M$, there exists quantum\nBoolean circuit $(n,t)$-simulating $M$, where $n$ denotes the length of input\nstrings, and $t$ is the number of move steps before machine stopping. However,\nthe simulations of quantum Turing machines by quantum multi-stack machines and\nquantum multi-counter machines have not been considered, and quantum\nmulti-stack machines have not been established, either. Though quantum counter\nmachines were dealt with by Kravtsev [6] and Yamasaki {\\it et al.} [10], in\nwhich the machines count with $0,\\pm 1$ only, we sense that it is difficult to\nsimulate quantum Turing machines in terms of this fashion of quantum computing\ndevices, and we therefore prove that the quantum multi-counter machines allowed\nto count with $0,\\pm 1,\\pm 2,...,\\pm n$ for some $n\u003e1$ can efficiently simulate\nquantum Turing machines.\n Therefore, our mail goals are to establish quantum multi-stack machines and\nquantum multi-counter machines with counts $0,\\pm 1,\\pm 2,...,\\pm n$ and $n\u003e1$,\nand particularly to simulate quantum Turing machines by these quantum computing\ndevices.",
"arxiv_id": "quant-ph/0501176",
"authors": [
"Daowen Qiu"
],
"categories": [
"quant-ph"
],
"title": "Simulations of Quantum Turing Machines by Quantum Multi-Stack Machines",
"url": "https://arxiv.org/abs/quant-ph/0501176"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "de5d1aab-f7bc-4e3d-a9a3-e2d80923637f",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}