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.
Zusammenfassung
Im Jahr 1936 veröffentlichten Church und Turing ihre berühmte Church-Turing-Hypothese. Sie gilt als einer der Grundpfeiler der Bere- chenbarkeits- und Komplexitätstheorie, die in den vergangenen Jahr- zehnten eine beachtliche Entwicklung vollzogen haben. Bis vor kurzem beschränkte man sich in der Forschung in erster Linie auf die klas- sischen, abstrahierten Prinzipien der Informationstheorie und schenk- te der physikalischen Natur von Information weniger Beachtung. Erst in den letzten Jahren kam der Gedanke auf, auch quantenmechani- sche 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 (physi- kalischen) 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 ei- nem 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.
1 Das Church-Turing Prinzip im physikalischen Kontext
Zum ersten Mal in seiner fast hundertjährigen Geschichte scheint das Fun- dament der Berechenbarkeitstheorie ins Wanken zu geraten. War diese Wis- senschaft seit jeher eine Domäne der Informatiker, ist vor kurzem von Physi- kern ein neuer Denkansatz gekommen, der den Wissenschaftlern eine andere Sichtweise eröffnet. Man behauptete, dass klassische Computer keine sichere Basis für die Berechenbarkeitstheorie darstellen, weil sie höchstens eine wage Annäherung an die Realität bieten könnten. Rechenprozesse, so die Annah- me, seien nämlich nichts anderes als physikalische Prozesse. Dabei bildet die Quantentheorie die Grundlage aller physikalischer Vorgänge. Deshalb ist es sinnvoll, den Quantencomputer als Grundlage der Berechenbarkeitstheorie anzusehen.
Zuerst wollen wir uns aber dem klassischen Ansatz von Church (1936) und Tuing (1936) widmen. Man stellte schon früh fest, dass es nicht möglich ist, Maschinen zu konstruieren, deren Funktionsumfang beliebig mächtig ist, egal wieviele Ressourcen zur Verfügung stehen. Church und Turing leiteten daraus ab, dass diese Einschränkung weder vom technischen Fortschritt noch durch den menschlichen Ideenreichtum aufgehoben werden können, sondern universeller Natur sind. Dies kommt in der sog. zum Ausdruck:
Every ”Church-TuringHypothese“ ”functionwhichwouldnaturallyberegardedascomputable“canbe computed by the universal Turing machine.
Hier wird der Sachverhalt in einer konventionellen, nicht-physischen Sicht- weise beschrieben. Sie bedient sich der intuitiven Formulierung ”naturally be regarded as computable“, so dass sie im Vergleich zu physischen Prin- zipien wie z.B. den Gesetzen der Thermodynamik eher undeutlich ist. D. Deutsch schlug deshalb vor, Turings Hypothese in einen physikalischen Kon- text zu setzen, so dass sie den gleichen erkenntnistheoretischen Status erhält wie andere physikalische Prinzipien. Er geht davon aus, das der Ausdruck ”functionswhichwouldnaturallyberegardedascomputable“interpretiert werden kann als diejenigen Funktionen, die prinzipiell durch ein reales phy- sikalisches System berechnet werden können. Um Mißinterpretationen des Begriffs ”naturally“auszuschließenbedientersichfolgenderNotationdes Begriffs perfekte Simulation: Eine Rechenmaschine M ist fähig ein physi- kalisches System S perfekt zu simulieren, wenn ein Programm π(S) für M existiert, welches M rechnerisch äquivalent zu S erscheinen läßt. Anders ausgedrückt verwandelt π(S) M in eine von S unterscheidbar ist.
Deutsch formuliert auf dieser Grundlage sein Church-Turing Prinzip:
Every finitely realizable physical system can be perfectly simulated by a universal computing machine operating by finite means.
Diese Formulierung ist sowohl besser definiert als auch Turings Original. Der Ausdruck ”physikalischer“als ”finitelyrealizablephysicalsystem“mußje- des physikalische Objekt einbeziehen, auf dem Messungen vollzogen werden können. Dagegen muss die ”universalcomputingmachine“nureinideali- siertes (aber theoretisch mögliches) endliches spezifizierbares Modell sein.
Die Fokussierung auf die universelle Turing-Maschine, wie sie im Original zu finden ist, muss notwendigerweise ersetzt werden durch die allgemeinere Bedingung, dass die Maschine mit endlichen Mitteln ( ”byfinitemeans“)arbei- tet. Dieser Ausdruck kann axiomatisch definiert werden. Betrachtet man den Rechenprozeß einer Rechenmaschine M als eine Reihe von Schritten, deren Dauer eine untere Grenze (> 0) hat, dann arbeitet M mit endlichen Mitteln, wenn (i) in jedem Schritt nur ein endliches Subsystem von M in Bewegung ist, und (ii) die Bewegung nur von dem Zustand des endlichen Subsystems abhängt, und (iii) die Regel, welche die Bewegung beschreibt, im mathema- tischen Sinn endlich angegeben werden kann (z.B. als eine natürliche Zahl). Sowohl Turingmaschinen wie auch Quantencomputer genügen diesen Axio- men. Dennoch ist die Aussage des Church-Turing-Prinzips so stark, dass Turing Maschinen im klassischen Sinn ihr nicht genügen, da sie kein phy- sikalisches System simulieren können. Es gibt nämlich nur abzählbar viele Möglichkeiten, einen endlichen Eingabezustand für eine Turingmaschine zu erzeugen. Dagegen gibt es in der (klassischen) Dynamik überabzählbar viele mögliche (Eingabe-)zustände. Der universelle Quantencomputer ist aller- dings schon dazu in der Lage.
2 Quanten-Turing-Maschinen
2.1 Definition der QTM
Im Gegensatz zum stochastischen Computer können beim Quantencomputer die Amplituden einer linearen Superposition und die Matrixelemente des Zeitevolutionsoperator komplexe Zahlen sein und nicht nur reelle positive Zahlen. Die Wahrscheinlichkeit, in einer Superposition durch Messung eine bestimmte Konfiguration c zu erhalten, berechnet sich aus dem Quadrat des Amplitudenbetrags, Pc = |αc|[2], die c zugeordnet ist. Die euklidische Länge der linearen Superposition ist dabei immer 1. Das heißt, dass eine QTM immer so definiert sein muß, dass ihre Zeitevolution immer die euklidische Länge in allen Superpositionen beibehalten muß.
Nun folgt zuerst (zur Wiederholung) die Definition der klassischen deterministischen Turingmaschine:
Definition 2.1. Eine deterministische Turingmaschine TM ist durch ein Tripel (Σ, Q, δ) definiert, wobei Σ ein endliches Alphabet mit einem festge- legtem blank-Symbol #, Q eine endliche Menge von Zuständen mit festgeleg- tem Anfangszustand q0 und Endzustand qf [Abbildung in dieser Leseprobe nicht enthalten] q0, und δ die deterministische Überführungsfunktion
Abbildung in dieser Leseprobe nicht enthalten
ist[1]. Die TM besitzt ein in beide Richtungen unendliches Band aus Zellen, die mit Z indiziert sind. Außerdem gibt es einen Schreib/Lesekopf der sich entlang des Bandes bewegen kann. Eine Konfiguration c ist eine ”Moment- aufnahme“ einer TM. Sie setzt sich zusammen aus dem Inhalt des Bandes, des aktuellen Zustands q ∈ Q und dem Aufenthaltsorts des Schreib/Lesekopfes. Zu jeder Zeit darf nur eine endliche Anzahl von Zellen ein Nichtblank- Symbol haben. Eine Nachfolgekonfiguration c′ wird durch die Anwendung von δ auf das aktuelle Bandsymbol und dem aktuellen Zustand erreicht. Man schreibt c →M c′ um auszudrücken, das c′ in einem Schritt auf c folgt. Per Konvention legt man fest, dass die Startkonfiguration folgende Bedingungen erfüllen muss: Der Schreib-/Lesekopf ist in Zelle 0 (Startzelle), und die TM ist im Zustand q0. Eine Startkonfiguration hat die Eingabe x ∈ (Σ−#)∗, wo- bei x in die Zellen 0, 1, 2, ..., geschrieben wird und alle anderen Zellen leer ge- lassen werden. Eine TM hält bei einer Eingabe x, wenn sie in endlicher Zeit in den Zustand qf eintritt. Die dafür benötigten Schritte werden als Laufzeit für die Eingabe x bezeichnet. Falls eine TM hält, dann ist die Ausgabe der String s ∈ Σ∗, der auf dem Band vom am weitesten links liegendem Nicht- blank bis zum am weitesten rechts liegenden Nichtblank reicht. Eine TM, die für alle Eingaben hält, berechnet demnach eine Funktion (Σ − #)∗ → Σ∗.
Als nächstes folgt die Definition der QTM nach Deutsch in leicht abgewandelter Form. Um die Überführungsamplituden effizient berechnen zu können, beschränkt man sie auf rationale Zahlen. Es wurde nachgewiesen, dass diese Einschränkung die Rechenstärke der QTM nicht einschränkt. Es wurde sogar gezeigt, dass die Amplitudenwerte [Abbildung in dieser Leseprobe nicht enthalten] ausreichenumeine universelle QTM zu konstruieren.
Definition 2.2. Sei [Abbildung in dieser Leseprobe nicht enthalten] eine Menge von αi ∈ [Abbildung in dieser Leseprobe nicht enthalten] für die es einen deterministischen Algorithmus gibt, der den realen und imaginären Teil von αi bis auf einen Abstand von [Abbildung in dieser Leseprobe nicht enthalten] in einer Zeit die polynomial zu n ist, berechnet. Eine QTM M ist ein Tripel (Σ,Q,δ), wobei Σ ein endliches Alphabet mit einem Blank-Symbol #, Q eine endliche Menge von Zuständen mit einem festgelegtem Anfangszustand q0 und einem festgelegtem Endzustand [Abbildung in dieser Leseprobe nicht enthalten], und δ die Quanten-Überführungsfunktion
Abbildung in dieser Leseprobe nicht enthalten
ist. Die TM besitzt ein in beide Richtungen unendliches Band aus Zellen, die mit [Abbildung in dieser Leseprobe nicht enthalten] indiziert sind. Wir definieren Konfigurationen, Startkonfiguratio- nen und Endkonfigurationen genauso wie bei deterministischen TMs. Sei S der Vektorraum (mit innerem Produkt) der endlichen komplexen Linear- kombinationen aller Konfigurationen von M mit der euklidischen Norm. Wir nennen jedes Element φ ∈ S eine Superposition von M. Die QTM M defi- niert einen linearen Operator [Abbildung in dieser Leseprobe nicht enthalten] : S → S, Zeitevolutionsoperator genannt, wie folgt: Wenn M am Anfang die Konfiguration c mit augenblicklichem Zu- stand p und gelesenem Symbol σ ist, dann wird sich M nach einem Schritt in der Superposition [Abbildung in dieser Leseprobe nicht enthalten] befinden, wobei jedes αi einem Übergang δ(p, σ, τ, q, d) zugeordnet wird und ci die neue Konfiguration ist, die aus δ resultiert. Wenn man diese Abbildung auf ganz S ausweitet erhält man den linearen Zeitevolutionsoperator Um.
S wird in dieser Definition durch eine Orthonormalbasis erzeugt, die sich aus den Konfigurationen der QTM zusammen setzt. Man kann deshalb jede Superposition ψ ∈ S durch einen Vektor aus komplexen Zahlen beschreiben werden, die mit entsprechenden Konfigurationen indiziert sind. Der Zeit- evolutionsoperator kann durch eine (abzählbar-dimensionale) quadratische Matrix repräsentiert werden, deren Reihen und Spalten man Konfiguratio- nen der QTM zugeordnet und in der jedes Matrixelement aij der Amplitude entspricht, welche die Konfiguration ci nach cj überführt.
Die nächste Definition ist für die Einhaltung der quantenphysikalischen Gesetze von großer Wichtigkeit.
Definition 2.3. Eine QTM wird als wohlgeformt bezeichnet, wenn ihr Zeitevolutionsoperator Um die euklidische Länge bewahrt.
Eine wohlgeformte QTM M muss also ein Um besitzen, der für jede denkbare Superposition von M sicherstellt, dass die Summe der Wahrscheinlichkeiten [Abbildung in dieser Leseprobe nicht enthalten] aller Konfigurationen [Abbildung in dieser Leseprobe nicht enthalten] immer 1 ist.
Als nächstes definieren wir Regeln zur Beobachtung von QTMs. Messungen werden dabei auf die berechenbare Basis von S beschränkt. Dies ist nötig, weil die Basis in der die Messung vollzogen werden soll, effektiv zu berechnen sein muß.
Definition 2.4. Wenn die QTM M in der Superposition [Abbildung in dieser Leseprobe nicht enthalten] be- obachtet oder gemessen wird, so erhält man das Ergebnis ci mit ci mit der Wahrscheinlichkeit [Abbildung in dieser Leseprobe nicht enthalten]. Die neue Superposition von M ist dann [Abbildung in dieser Leseprobe nicht enthalten].
Es ist auch möglich, partielle Messungen durchzuführen, beispielsweise nur über der ersten Zelle des Bandes. Wir nehmen an, dass in dieser ersten Zelle entweder eine 1 oder eine 0 steht. Weiterhin gehen wir von folgender Superposition aus: [Abbildung in dieser Leseprobe nicht enthalten]. [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten] sind jene Konfigu- rationen, die eine 0 bzw. 1 in der ersten Zelle stehen haben. Wenn man nun eine Messung über der ersten Zelle ausführt, ist die Wahrscheinlichkeit eine [Abbildung in dieser Leseprobe nicht enthalten] zu messen [Abbildung in dieser Leseprobe nicht enthalten] = [Abbildung in dieser Leseprobe nicht enthalten]. Falls nun eine [Abbildung in dieser Leseprobe nicht enthalten] gemessen wurde ergibt sich eine neue Superposition [Abbildung in dieser Leseprobe nicht enthalten] . Der Teil der Superposition also, der mit dem gemessenen Ergebnis im Einklang steht, bleibt erhalten, wobei seine Amplitude wieder die euklidische Länge haben muss.
Im weiteren Verlauf beschränken wir uns beim Messen angehaltene QTMs und bezeichnen das Ergebnis als Ausgabe. Dies führt nicht zu einem Verlust von Berechnungsstärke, wie in [3] nachgewiesen wird. Allgemein können wir
[...]
[1] Manchmal wir die Menge {L, R} noch um ein N , das soviel wie ”keineBewegung“ bedeutet, erweitert. Wir betracheten diese Variante der TM jedoch nicht.
-
-
-
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X.