Quantum Kolmogorov Complexity and the Quantum Turing Machine

Details Quantum Kolmogorov Complexity and the Quantum Turing Machine Quantum Kolmogorov Complexity and the Quantum Turing Machine

2007-12-28

arxiv.org/abs/0712.4377v1

Physics

Quantum Physics

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

Scientific paper

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 \rho as the minimum base length of any quantum input which makes a quantum Turing machine (QTM) halt and output \rho, 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.

Affiliated with

Also associated with

No associations

Rating

Quantum Kolmogorov Complexity and the Quantum Turing Machine does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Kolmogorov Complexity and the Quantum Turing Machine, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Kolmogorov Complexity and the Quantum Turing Machine will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-508619