On Halting Process of Quantum Turing Machine

DOI10.1007/S11080-005-0923-2MaRDI QIDQ3368408zbMATH OpenOpenAlexFDO

Authors Takayuki Miyadera, Masanori Ohya

Publication date 30 January 2006

Published in Open Systems & Information Dynamics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Quantum computation (81P68)

Abstract: We prove that there is no algorithm to tell whether an arbitrarily constructed Quantum Turing Machine has same time steps for different branches of computation. We, hence, can not avoid the notion of halting to be probabilistic in Quantum Turing Machine. Our result suggests that halting scheme of Quantum Turing Machine and quantum complexity theory based upon the existing halting scheme sholud be reexamined.

Recommendations

• scientific article; zbMATH DE number 2013798
• scientific article; zbMATH DE number 1379489
• On the halting problem for a quantum computer
• IRREVERSIBILITY IN THE HALTING PROBLEM OF QUANTUM COMPUTER
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

Cites work

• scientific article; zbMATH DE number 1530002 (Why is no real title available?)
• Can a Universal Quantum Computer Be Fully Quantum?
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Complexity Theory
• Remarks on universal quantum computer

Cited in

(8)

• Quantum circuit oracles for abstract machine computations
• scientific article; zbMATH DE number 2013798 (Why is no real title available?)
• On the halting problem for a quantum computer
• scientific article; zbMATH DE number 1542832 (Why is no real title available?)
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Quantum Kolmogorov complexity and information-disturbance theorem
• Quantum random access stored-program machines
• IRREVERSIBILITY IN THE HALTING PROBLEM OF QUANTUM COMPUTER

This page was built for publication: On Halting Process of Quantum Turing Machine

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