Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

DOI10.1109/TIT.2007.913263zbMATH Open1314.68135arXivquant-ph/0605030MaRDI QIDQ3604703FDOQ3604703

Authors:

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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.

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

Recommendations

• Universality of quantum Turing machines with deterministic control
• Quantum Complexity Theory
• Remarks on universal quantum computer
• Quantum Kolmogorov complexity
• On Halting Process of Quantum Turing Machine

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cited In (12)

• An extended coding theorem with application to quantum complexities
• Universality of quantum Turing machines with deterministic control
• ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS
• Remarks on universal quantum computer
• Partial observation of quantum Turing machines and a weaker well-formedness condition
• Quantum dynamical entropies and Gács algorithmic entropy
• Note on a universal quantum Turing machine
• On Halting Process of Quantum Turing Machine
• Quantum Kolmogorov complexity and the quantum Turing machine
• Quantum information distance
• Quantum Kolmogorov complexity and information-disturbance theorem
• THE SECOND QUANTIZED QUANTUM TURING MACHINE AND KOLMOGOROV COMPLEXITY

This page was built for publication: Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity

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