On Halting Process of Quantum Turing Machine

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.

2 pages

References in corpus (4)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Nondemolition Monitoring of Universal Quantum Computers
• Remarks on Universal Quantum Computer

Cited by in corpus (14)

• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Quantum Random Access Stored-Program Machines
• Quantum Kolmogorov Complexity and Quantum Key Distribution
• Quantum Turing Machines Computations and Measurements
• Halting in quantum Turing computation
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Iterative Deepening with an application to the Halting problem
• Quantum Register Machine: Efficient Implementation of Quantum Recursive Programs
• Quantum Kolmogorov Complexity and Bounded Quantum Memory
• A local model of quantum Turing machines
• Towards A Theory Of Quantum Computability
• On Quantum Turing Machine Halting Deterministically