Remarks on universal quantum computer

DOI10.1016/S0375-9601(02)00015-4MaRDI QIDQ5954906zbMATH OpenOpenAlexFDO

Authors Yu. Shi

Publication date 5 February 2002

Published in Physics Letters. A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/quant-ph/9908074

zbMATH Keywords

entanglementunitary transformationTuring machine

Mathematics Subject Classification ID

Quantum computation (81P68)

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.

Recommendations

• Universality and programmability of quantum computers
• Can a Universal Quantum Computer Be Fully Quantum?
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• On the halting problem for a quantum computer
• scientific article; zbMATH DE number 1379489

Cites work

• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 2002072 (Why is no real title available?)
• Can a Universal Quantum Computer Be Fully Quantum?
• Programmable Quantum Gate Arrays
• Quantum Complexity Theory
• Quantum computational networks
• Quantum theory, the Church–Turing principle and the universal quantum computer

Cited in

(14)

• Note on a universal quantum Turing machine
• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY
• Programmable Quantum Gate Arrays
• Cellular quantum computer architecture
• IRREVERSIBILITY IN THE HALTING PROBLEM OF QUANTUM COMPUTER
• Zeno machines and hypercomputation
• Universality and programmability of quantum computers
• Quantum random access stored-program machines
• Resonant spin polarization in a two-dimensional hole gas
• A prototype of quantum von Neumann architecture
• Can a Universal Quantum Computer Be Fully Quantum?
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Unsolvability of the halting problem in quantum dynamics
• On Halting Process of Quantum Turing Machine

This page was built for publication: Remarks on universal quantum computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5954906)