Quantum Kolmogorov Complexity and the Quantum Turing Machine

Abstract

The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity (QC), and rigorous mathematical proofs of its basic properties. The definition used here is similar to that by Berthiaume, van Dam, and Laplante. It defines the QC of some indeterminate-length qubit string ρas the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output ρ, up to some error tolerance. First, we prove that there is a QTM which is universal in the sense of input base length. Furthermore, we show several general properties of QTMs, including a result on mutually orthogonal ``halting spaces'', and a way to transform every almost-halting input into a deterministically-halting input by adding at most a constant number of qubits. Afterwards, we apply these results to QC. In particular, we show that QC is invariant, incompressible, agrees with classical Kolmogorov complexity for classical strings, and is closely related to von Neumann entropy for ergodic quantum information sources.

Ph.D. thesis, Technical University of Berlin, August 2007. 114 pages, 4 figures

References in corpus (18)

• Quantum Kolmogorov Complexity
• Universal Quantum Information Compression
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Quantum Algorithmic Entropy
• Algorithmic complexity and entanglement of quantum states
• Quantum Nondemolition Monitoring of Universal Quantum Computers
• Indeterminate-length quantum coding
• Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno's Theorem
• Lossless quantum data compression and variable-length coding
• Remarks on Universal Quantum Computer
• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• On Halting Process of Quantum Turing Machine
• Measurement-Based Quantum Turing Machines and their Universality
• The Halting Problem for Quantum Computers
• Quantum algorithmic information theory
• Models of Quantum Turing machines
• An extension of Chaitin's halting probability Ωto a measurement operator in an infinite dimensional quantum system
• The Second Quantized Quantum Turing Machine and Kolmogorov Complexity

Cited by in corpus (9)

• Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity
• Equilibration in low-dimensional quantum matrix models
• Prefix-free quantum Kolmogorov complexity
• Quantum Kolmogorov Complexity and Information-Disturbance Theorem
• Quantum algorithmic randomness
• Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
• Quantum Iterative Deepening with an application to the Halting problem
• Algorithmic Randomness and Kolmogorov Complexity for Qubits
• On Gács' quantum algorithmic entropy