Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

Abstract

We show that there exists a universal quantum Turing machine (UQTM) that can simulate every other QTM until the other QTM has halted and then halt itself with probability one. This extends work by Bernstein and Vazirani who have shown that there is a UQTM that can simulate every other QTM for an arbitrary, but preassigned number of time steps. As a corollary to this result, we give a rigorous proof that quantum Kolmogorov complexity as defined by Berthiaume et al. is invariant, i.e. depends on the choice of the UQTM only up to an additive constant. Our proof is based on a new mathematical framework for QTMs, including a thorough analysis of their halting behaviour. We introduce the notion of mutually orthogonal halting spaces and show that the information encoded in an input qubit string can always be effectively decomposed into a classical and a quantum part.

18 pages, 1 figure. The operation R is now really a quantum operation (it was not before); corrected some typos, III.B more readable, Conjecture 3.15 is now a theorem

References in corpus (6)

• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
• Lossless quantum data compression and variable-length coding
• On Halting Process of Quantum Turing Machine
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• The Second Quantized Quantum Turing Machine and Kolmogorov Complexity

Cited by in corpus (13)

• Law without law: from observer states to physics via algorithmic information theory
• Quantum Kolmogorov Complexity and the Quantum Turing Machine
• Quantum Kolmogorov Complexity and Quantum Key Distribution
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Kolmogorov Complexity and Bounded Quantum Memory
• Quantum Iterative Deepening with an application to the Halting problem
• A Gentle Introduction to Quantum Computing Algorithms with Applications to Universal Prediction
• On Gács' quantum algorithmic entropy
• On the Quantum Kolmogorov Complexity of Classical Strings
• On the Role of Quantum Computing in Science and Cybersecurity
• An Extended Coding Theorem with Application to Quantum Complexities
• Second Quantized Kolmogorov Complexity