dorsal/arxiv
View SchemaDeutsch's Universal Quantum Turing Machine (Revisited)
| Authors | Willem Fouché, Johannes Heidema, Glyn Jones, Petrus H. Potgieter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0701108 |
| URL | https://arxiv.org/abs/quant-ph/0701108 |
Abstract
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.
{
"annotation_id": "150f5848-0eba-405f-aff4-6e526889435c",
"date_created": "2026-03-02T18:02:33.580000Z",
"date_modified": "2026-03-02T18:02:33.580000Z",
"file_hash": "7e95758ed025bd923d86fb58c4a518051b5c23e6c544d131b2b086afe27482c9",
"private": false,
"record": {
"abstract": "Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal\nphysical simulation procedure. Much of the writing about quantum Turing\nmachines has shown how these machines can simulate an arbitrary unitary\ntransformation on a finite number of qubits. This interesting problem has been\naddressed most famously in a paper by Deutsch, and later by Bernstein and\nVazirani. Quantum Turing machines form a class closely related to deterministic\nand probabilistic Turing machines and one might hope to find a universal\nmachine in this class. A universal machine is the basis of a notion of\nprogrammability. The extent to which universality has in fact been established\nby the pioneers in the field is examined and a key notion in theoretical\ncomputer science (universality) is scrutinised. In a forthcoming paper, the\nauthors will also consider universality in the quantum gate model.",
"arxiv_id": "quant-ph/0701108",
"authors": [
"Willem Fouch\u00e9",
"Johannes Heidema",
"Glyn Jones",
"Petrus H. Potgieter"
],
"categories": [
"quant-ph"
],
"title": "Deutsch\u0027s Universal Quantum Turing Machine (Revisited)",
"url": "https://arxiv.org/abs/quant-ph/0701108"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "6ac14542-c39b-468a-aafc-14314e4d6d60",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}