dorsal/arxiv
View SchemaModels of Quantum Turing machines
| Authors | Paul Benioff |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9708054 |
| URL | https://arxiv.org/abs/quant-ph/9708054 |
| DOI | 10.1002/(SICI)1521-3978(199806)46:4/5<423::AID-PROP423>3.0.CO;2-G |
| Journal | Fortsch.Phys. 46 (1998) 423-442 |
Abstract
Quantum Turing machines are discussed and reviewed in this paper. Most of the paper is concerned with processes defined by a step operator $T$ that is used to construct a Hamiltonian $H$ according to Feynman's prescription. Differences between these models and the models of Deutsch are discussed and reviewed. It is emphasized that the models with $H$ constructed from $T$ include fully quantum mechanical processes that take computation basis states into linear superpositions of these states. The requirement that $T$ be distinct path generating is reviewed. The advantage of this requirement is that Schr\"{o}dinger evolution under $H$ is one dimensional along distinct finite or infinite paths of nonoverlapping states in some basis $B_{T}$. It is emphasized that $B_{T}$ can be arbitrarily complex with extreme entanglements between states of component systems. The new aspect of quantum Turing machines introduced here is the emphasis on the structure of graphs obtained when the states in the $B_{T}$ paths are expanded as linear superpositions of states in a reference basis such as the computation basis $B_{C}$. Examples are discussed that illustrate the main points of the paper. For one example the graph structures of the paths in $B_{T}$ expanded as states in $B_{C}$ include finite stage binary trees and concatenated finite stage binary trees with or without terminal infinite binary trees. Other examples are discussed in which the graph structures correspond to interferometers and iterations of interferometers.
{
"annotation_id": "9e29424c-9cd1-4878-8c1e-3565578c1b19",
"date_created": "2026-03-02T18:02:41.608000Z",
"date_modified": "2026-03-02T18:02:41.608000Z",
"file_hash": "3903ca87bb7003f141682ff1b90592f6a15695e286a7469c378d843ed502ec8a",
"private": false,
"record": {
"abstract": "Quantum Turing machines are discussed and reviewed in this paper. Most of the\npaper is concerned with processes defined by a step operator $T$ that is used\nto construct a Hamiltonian $H$ according to Feynman\u0027s prescription. Differences\nbetween these models and the models of Deutsch are discussed and reviewed. It\nis emphasized that the models with $H$ constructed from $T$ include fully\nquantum mechanical processes that take computation basis states into linear\nsuperpositions of these states. The requirement that $T$ be distinct path\ngenerating is reviewed. The advantage of this requirement is that\nSchr\\\"{o}dinger evolution under $H$ is one dimensional along distinct finite or\ninfinite paths of nonoverlapping states in some basis $B_{T}$. It is emphasized\nthat $B_{T}$ can be arbitrarily complex with extreme entanglements between\nstates of component systems. The new aspect of quantum Turing machines\nintroduced here is the emphasis on the structure of graphs obtained when the\nstates in the $B_{T}$ paths are expanded as linear superpositions of states in\na reference basis such as the computation basis $B_{C}$. Examples are discussed\nthat illustrate the main points of the paper. For one example the graph\nstructures of the paths in $B_{T}$ expanded as states in $B_{C}$ include finite\nstage binary trees and concatenated finite stage binary trees with or without\nterminal infinite binary trees. Other examples are discussed in which the graph\nstructures correspond to interferometers and iterations of interferometers.",
"arxiv_id": "quant-ph/9708054",
"authors": [
"Paul Benioff"
],
"categories": [
"quant-ph"
],
"doi": "10.1002/(SICI)1521-3978(199806)46:4/5\u003c423::AID-PROP423\u003e3.0.CO;2-G",
"journal_ref": "Fortsch.Phys. 46 (1998) 423-442",
"title": "Models of Quantum Turing machines",
"url": "https://arxiv.org/abs/quant-ph/9708054"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "e738da98-bf70-4b9b-b55c-8b4a2d4068dc",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}