Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-1687
Main Title: Quantum Kolmogorov Complexity and the Quantum Turing Machine
Translated Title: Quanten-Kolmogorov-Komplexität und die Quanten-Turing-Maschine
Author(s): Müller, Markus
Advisor(s): Seiler, Ruedi
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Ziel dieser Arbeit ist es, den Begriff der Quanten-Kolmogorov-Komplexität formal zu definieren und seine wichtigsten Eigenschaften rigoros zu beweisen. Die klassische Kolmogorov-Komplexität ist ein bekanntes und nützliches Maß für die Zufälligkeit endlicher Wörter. In den letzten Jahren wurden unterschiedliche Quantenverallgemeinerungen der Kolmogorov-Komplexität vorgeschlagen. Die natürlichste Art der Verallgemeinerung stammt von Berthiaume u.a., die die Komplexität eines Quantenwortes definieren als die Länge der kürzesten Quanteneingabe für einen universellen Quantencomputer, die als Ausgabe das entsprechende Wort produziert. Abgesehen von kleinen Änderungen soll dieser Komplexitätsbegriff in der hier vorliegenden Arbeit untersucht werden. Zunächst untersuchen wir verschiedene Aspekte des zugrunde liegenden Modells der Quantenturingmaschine (QTM), und zwar mit größerer formaler Genauigkeit als in bisherigen Arbeiten. Anschließend wenden wir diese Resultate auf die Quanten-Kolmogorov-Komplexität an. Unser erstes Ergebnis, basierend auf der Arbeit von Bernstein und Vazirani, ist ein Beweis für die Existenz einer universellen QTM, die jede andere QTM für eine beliebige Anzahl von Zeitschritten simulieren kann, und dann selbst mit Wahrscheinlichkeit eins hält. Weiterhin zeigen wir, dass jede Eingabe, die eine QTM beinahe halten lässt, modifiziert werden kann, um eine Eingabe zu erhalten, die die universelle QTM vollständig halten lässt, wobei sich die Eingabelänge höchstens um eine konstante Anzahl von Qubits vergrößert. Daraus folgt, dass die Quanten-Kolmogorov-Komplexität die Invarianzeigenschaft besitzt, d.h. sie ist bis auf eine additive Konstante unabhängig von der Wahl der universellen QTM. Außerdem stimmt die Quantenkomplexität klassischer Wörter mit deren klassischer Komplexität überein, wieder bis auf eine additive Konstante. Die entsprechenden Beweise beruhen auf verschiedenen analytischen Abschätzungen. Weiterhin beweisen wir mehrere Sätze, die zeigen, dass nur wenige Quantenwörter kleine Quantenkomplexität besitzen können. Schließlich zeigen wir, dass bei ergodischen Quantendatenquellen Komplexitätsrate und Entropierate mit Wahrscheinlichkeit eins übereinstimmen. Den Abschluss der Arbeit bildet ein Ausblick auf eine mögliche Anwendung der Quanten-Kolmogorov-Komplexität in der statistischen Mechanik.
The purpose of this thesis is to give a formal definition of quantum Kolmogorov complexity and rigorous mathematical proofs of its basic properties. Classical Kolmogorov complexity is a well-known and useful measure of randomness for binary strings. In recent years, several different quantum generalizations of Kolmogorov complexity have been proposed. The most natural generalization is due to Berthiaume et al., defining the complexity of a quantum bit (qubit) string as the length of the shortest quantum input for a universal quantum computer that outputs the desired string. Except for slight modifications, it is this definition of quantum Kolmogorov complexity that we study in this thesis. We start by analyzing certain aspects of the underlying quantum Turing machine (QTM) model in a more detailed formal rigour than was done previously. Afterwards, we apply these results to quantum Kolmogorov complexity. Our first result, based on work by Bernstein and Vazirani, is a proof of the existence of a universal QTM which simulates every other QTM for an arbitrary number of time steps and than halts with probability one. In addition, we show that every input that makes a QTM almost halt can be modified to make the universal QTM halt entirely, by adding at most a constant number of qubits. It follows that quantum Kolmogorov complexity has the invariance property, i.e. it depends on the choice of the universal QTM only up to an additive constant. Moreover, the quantum complexity of classical strings agrees with classical complexity, again up to an additive constant. The proofs are based on several analytic estimates. Furthermore, we prove several incompressibility theorems for quantum Kolmogorov complexity. Finally, we show that for ergodic quantum information sources, complexity rate and entropy rate coincide with probability one. The thesis is finished with an outlook on a possible application of quantum Kolmogorov complexity in statistical mechanics.
URI: urn:nbn:de:kobv:83-opus-16551
http://depositonce.tu-berlin.de/handle/11303/1984
http://dx.doi.org/10.14279/depositonce-1687
Exam Date: 31-Aug-2007
Issue Date: 27-Sep-2007
Date Available: 27-Sep-2007
DDC Class: 510 Mathematik
Subject(s): Quanteninformation
Quantenkomplexität
Quantenturingmaschine
Turingmaschine
Universeller Quantencomputer
Quantum complexity
Quantum information
Quantum Turing machine
Turing machine
Universal quantum computer
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_45.pdf772.83 kBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.