Im Jahr 1936 veröffentlichten Church und Turing ihre berühmte Church-Turing-Hypothese. Sie gilt als einer der Grundpfeiler der Berechenbarkeits- und Komplexitätstheorie, die in den vergangenen Jahrzehnten
eine beachtliche Entwicklung vollzogen haben. Bis vor kurzem beschränkte man sich in der Forschung in erster Linie auf die klassischen, abstrahierten Prinzipien der Informationstheorie und schenkte der physikalischen Natur von Information weniger Beachtung. Erst in den letzten Jahren kam der Gedanke auf, auch quantenmechanische Phänomene bei der Konstruktion von Computern auszunutzen. Einer der Vorreiter auf diesem Gebiet ist David Deutsch [1], der bei seinem Versuch, die Church-Turing-Hypothese zu beweisen, als erster
(Quanten-)Physik als Grundlage benutzte. Dabei stellte er fest, dass
die klassische Komplexitätstheorie nicht ohne weiteres mit der (physikalischen)
Realität vereinbar ist. Sie bedurfte einer Erweiterung. Die daraus entstandene Quantenkomplexitätstheorie setzt sich zum Ziel, eine weitgreifendere Definition von "Komplexität" und "Wissen" in einem physikalischem System zu geben. Dabei muß nicht zuletzt auch die Church-Turing-Hypothese erweitert und präzisiert werden. Auf dieser Grundlage ist es letztendlich möglich, eine universelle Quanten-Turing-Maschine zu konstruieren. Im ersten Teil dieser Arbeit werde ich die Ideen von David Deutsch skizzieren und mich dann im zweiten Teil der Quantenturingmaschine (QTM) widmen, die im letzten Kapitel zu einer universellen Quantenturingmaschine ausgebaut werden soll.
Inhaltsverzeichnis
1 Das Church-Turing Prinzip im physikalischen Kontext
2 Quanten-Turing-Maschinen
2.1 Definition der QTM
2.2 Konventionen für die Ein- und Ausgabe bei QTMs
3 Programmieren einer QTM
3.1 Reversible TMs
3.2 Programmierprimitiven
3.3 Konstruktion einer universellen QTM
Zielsetzung & Themen
Die Arbeit verfolgt das Ziel, das klassische Church-Turing-Prinzip durch einen quantenphysikalischen Ansatz zu erweitern und auf dieser Grundlage die Konstruktion einer universellen Quanten-Turing-Maschine (QTM) formal zu beschreiben und methodisch zu fundieren.
- Theoretische Erweiterung des Church-Turing-Prinzips in einen physikalischen Kontext.
- Formale Definition und Modellierung von Quanten-Turing-Maschinen und deren Zeitevolution.
- Entwicklung von Programmierprimitiven (Verzweigung, Umkehrung, Iteration) für reversible Turingmaschinen.
- Konstruktion und Simulation einer universellen Quanten-Turing-Maschine.
Auszug aus dem Buch
3.3 Konstruktion einer universellen QTM
Zum Schluß benutzen wir die bisherigen Erkenntnisse, um eine universelle QTM zu konstruieren. Eine universelle QTM zeichnet sich dadurch aus, dass sie auch die Berechnungen jeder beliebigen anderen QTM durchführen kann. Dies bedeutet, dass sie alle anderen QTMs simulieren kann. Notwendigerweise wird die universelle QTM mehrere Schritte für jeden Schritt der simulierten Maschine benötigen. Ein einzelner Schritt entspricht bekanntlich einer Abbildung der orthonormalen Basis auf eine neue orthonormale Basis. Da ein einzelner Schritt der universellen QTM nur einen Teil der Basisvektoren auf das gewünschte Ziel abbilden kann, werden nicht immer alle Vektoren orthogonal aufeinander stehen und so eine solche partielle Transformation nicht unitär sein. Bei der Lösung des Problems hilft uns folgendes Lemma:
Lemma 3.10 (Unidirektionslemma). Jede QTM M kann von einer unidirektionalen QTM M’ mit einer Verlangsamung um den Faktor 5 simuliert werden. Falls M eine sich wohlverhaltende normale QTM ist, gilt dies auch für M’.
Zusammenfassung der Kapitel
1 Das Church-Turing Prinzip im physikalischen Kontext: Die Einleitung diskutiert die Notwendigkeit, das klassische Church-Turing-Prinzip um physikalische Prinzipien zu erweitern, um Quantenphänomene bei der Berechnung einzubeziehen.
2 Quanten-Turing-Maschinen: In diesem Kapitel werden formale Definitionen für die Quanten-Turing-Maschine, ihre wohlgeformte Zeitevolution sowie Konventionen für die Ein- und Ausgabe etabliert.
3 Programmieren einer QTM: Der Hauptteil konzentriert sich auf die algorithmische Programmierung, die Einführung von Primitiven wie Verzweigung und Schleifen für reversible Maschinen sowie die finale Konstruktion der universellen Quanten-Turing-Maschine.
Schlüsselwörter
Quanten-Turing-Maschine, QTM, Church-Turing-Prinzip, Quantenkomplexitätstheorie, Reversibilität, Zeitevolutionsoperator, universelle Turing-Maschine, Simulation, unitäre Transformation, wohlgeformte QTM, unidirektionale QTM, Berechenbarkeitstheorie, Superposition, Programmierung, Algorithmus
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit untersucht die Erweiterung der klassischen Berechenbarkeitstheorie durch quantenmechanische Prinzipien und leitet daraus die Konstruktion einer universellen Quanten-Turing-Maschine ab.
Was sind die zentralen Themenfelder?
Die zentralen Felder umfassen die physikalische Interpretation der Church-Turing-Hypothese, die formale Definition von Quanten-Turing-Maschinen und deren effiziente Programmierbarkeit.
Was ist das primäre Ziel der Untersuchung?
Das primäre Ziel ist es, zu zeigen, dass man mittels quantenphysikalischer Prinzipien eine universelle Maschine konstruieren kann, die in der Lage ist, jede andere Quanten-Turing-Maschine zu simulieren.
Welche wissenschaftlichen Methoden werden verwendet?
Es wird ein formal-axiomatischer Ansatz gewählt, der auf der Definition von Zustandsübergängen, unitären Transformationen und der Simulation durch unidirektionale Maschinen basiert.
Was wird im Hauptteil behandelt?
Der Hauptteil behandelt die theoretischen Grundlagen der Quanten-Programmierung, inklusive der Entwicklung von Primitiven wie Schleifen und Verzweigungen, sowie den Nachweis der universellen Simulierbarkeit.
Welche Schlüsselwörter charakterisieren die Arbeit?
Schlüsselbegriffe wie Quanten-Turing-Maschine, unitäre Transformation, Reversibilität und das Church-Turing-Prinzip sind zentral für das Verständnis der Arbeit.
Was genau leistet das in Kapitel 3 beschriebene "Verzweigungslemma"?
Das Verzweigungslemma ermöglicht die Konstruktion einer bedingten Verzweigung, bei der eine Maschine abhängig vom Inhalt eines zweiten Bandes eine von zwei weiteren Maschinen ausführt.
Wie wird das Problem der Nicht-Unitarität bei der universellen Simulation gelöst?
Durch das Unidirektionslemma wird gezeigt, dass jede QTM durch eine unidirektionale QTM simuliert werden kann, wodurch die Schwierigkeiten bei der Abbildung der Basisvektoren umgangen werden.
- Arbeit zitieren
- Matthias Schmeißer (Autor:in), 2003, Die universelle Quantenturingmaschine, München, GRIN Verlag, https://www.grin.com/document/113190
