Remarks on Universal Quantum Computer
arXiv:quant-ph/9908074 · doi:10.1016/S0375-9601(02)00015-4
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.
revtex, 14 pages, version appearing in Phys. Lett. A
References in corpus (4)
Cited by in corpus (18)
- Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
- On Halting Process of Quantum Turing Machine
- A comparative study of universal quantum computing models: towards a physical unification
- A prototype of quantum von Neumann architecture
- Quantum Kolmogorov Complexity and the Quantum Turing Machine
- Choi states, symmetry-based quantum gate teleportation, and stored-program quantum computing
- Quantum Random Access Stored-Program Machines
- A survey of universal quantum von Neumann architecture
- Halting in quantum Turing computation
- Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
- Unsolvability of the Halting Problem in Quantum Dynamics
- Quantum search processes in the cyclic group state spaces
- Irreversibility in the Halting Problem of Quantum Computer
- The basic principles to construct a generalized state-locking pulse field and simulate efficiently the reversible and unitary halting protocol of a universal quantum computer
- Quantum collapse as undecidable proposition in an Everettian multiverse
- A local model of quantum Turing machines
- On Quantum Turing Machine Halting Deterministically
- Zeno machines and hypercomputation