dorsal/arxiv
View SchemaRemarks on Universal Quantum Computer
| Authors | Yu Shi |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/9908074 |
| URL | https://arxiv.org/abs/quant-ph/9908074 |
| DOI | 10.1016/S0375-9601(02)00015-4 |
| Journal | Phys. Lett. A 293 (2002) 277 |
Abstract
According to Deutsch, a universal quantum Turing machine (UQTM) is able to perform, in repeating a fixed unitary transformation on the total system, an arbitrary unitary transformation on an arbitrary data state, by including a program as another part of the input state. We note that if such a UQTM really exists, with the program state dependent on the data state, and if the prescribed halting scheme is indeed valid, then there would be no entanglement between the halt qubit and other qubits, as pointed out by Myers. If, however, the program is required to be independent of the data, the concerned entanglement appears, and is problematic no matter whether the halt qubit is monitored or not. We also note that for a deterministic programmable quantum gate array, as discussed by Nielson and Chuang, if the program is allowed to depend on the data state, then its existence has not been ruled out. On the other hand, if UQTM exists, it can be simulated by repeating the operation of a fixed gate array. However, more importantly, we observe that it is actually still open whether Deutsch's UQTM exists and whether a crucial concatenation scheme, of which the halting scheme is a special case, is valid.
{
"annotation_id": "8b080b3c-8fb5-42fe-a9b3-bfc012687a32",
"date_created": "2026-03-02T18:02:48.100000Z",
"date_modified": "2026-03-02T18:02:48.100000Z",
"file_hash": "d3d80eeaacc41071b19223a813044dae90d36895ca917a7fcee196bfa22b277f",
"private": false,
"record": {
"abstract": "According to Deutsch, a universal quantum Turing machine (UQTM) is able to\nperform, in repeating a fixed unitary transformation on the total system, an\narbitrary unitary transformation on an arbitrary data state, by including a\nprogram as another part of the input state. We note that if such a UQTM really\nexists, with the program state dependent on the data state, and if the\nprescribed halting scheme is indeed valid, then there would be no entanglement\nbetween the halt qubit and other qubits, as pointed out by Myers. If, however,\nthe program is required to be independent of the data, the concerned\nentanglement appears, and is problematic no matter whether the halt qubit is\nmonitored or not. We also note that for a deterministic programmable quantum\ngate array, as discussed by Nielson and Chuang, if the program is allowed to\ndepend on the data state, then its existence has not been ruled out. On the\nother hand, if UQTM exists, it can be simulated by repeating the operation of a\nfixed gate array. However, more importantly, we observe that it is actually\nstill open whether Deutsch\u0027s UQTM exists and whether a crucial concatenation\nscheme, of which the halting scheme is a special case, is valid.",
"arxiv_id": "quant-ph/9908074",
"authors": [
"Yu Shi"
],
"categories": [
"quant-ph"
],
"doi": "10.1016/S0375-9601(02)00015-4",
"journal_ref": "Phys. Lett. A 293 (2002) 277",
"title": "Remarks on Universal Quantum Computer",
"url": "https://arxiv.org/abs/quant-ph/9908074"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "99a49033-c203-4d37-b7f5-01babbabc26b",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}