dorsal/arxiv
View SchemaROM-based computation: quantum versus classical
| Authors | B. C. Travaglione, M. A. Nielsen, H. M. Wiseman, A. Ambainis |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0109016 |
| URL | https://arxiv.org/abs/quant-ph/0109016 |
| Journal | Quantum Information and Computation, Vol. 2, No. 4 (2002) |
Abstract
We introduce a model of computation based on read only memory (ROM), which allows us to compare the space-efficiency of reversible, error-free classical computation with reversible, error-free quantum computation. We show that a ROM-based quantum computer with one writable qubit is universal, whilst two writable bits are required for a universal classical ROM-based computer. We also comment on the time-efficiency advantages of quantum computation within this model.
{
"annotation_id": "222769cf-ab65-49d9-9b2f-39814b4409ce",
"date_created": "2026-03-02T18:01:45.395000Z",
"date_modified": "2026-03-02T18:01:45.395000Z",
"file_hash": "8b8f56a005701c37f9cb5e67c15677083b781f2e73126d5a463ff48d66857963",
"private": false,
"record": {
"abstract": "We introduce a model of computation based on read only memory (ROM), which\nallows us to compare the space-efficiency of reversible, error-free classical\ncomputation with reversible, error-free quantum computation. We show that a\nROM-based quantum computer with one writable qubit is universal, whilst two\nwritable bits are required for a universal classical ROM-based computer. We\nalso comment on the time-efficiency advantages of quantum computation within\nthis model.",
"arxiv_id": "quant-ph/0109016",
"authors": [
"B. C. Travaglione",
"M. A. Nielsen",
"H. M. Wiseman",
"A. Ambainis"
],
"categories": [
"quant-ph"
],
"journal_ref": "Quantum Information and Computation, Vol. 2, No. 4 (2002)",
"title": "ROM-based computation: quantum versus classical",
"url": "https://arxiv.org/abs/quant-ph/0109016"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "80bba986-0ed5-4769-8bfc-5f756e128f78",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}