Ann¨ aherung an die Realit¨ at bieten k¨ onnten. Rechenprozesse, so die Annahme, seien n¨ amlich nichts anderes als physikalische Prozesse. Dabei bildet die Quantentheorie die Grundlage aller physikalischer Vorg¨ ange. 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¨ uh fest, dass es nicht m¨ oglich ist, Maschinen zu konstruieren, deren Funktionsumfang beliebig m¨ achtig ist, egal wieviele Ressourcen zur Verf¨ ugung stehen. Church und Turing leiteten daraus ab, dass diese Einschr¨ ankung weder vom technischen Fortschritt noch durch den menschlichen Ideenreichtum aufgehoben werden k¨ onnen, sondern universeller Natur sind. Dies kommt in der sog. ” Church-Turing Hypothese“ zum Ausdruck:

Every ” function which would naturally be regarded as computable“ can be computed by the universal Turing machine.

Hier wird der Sachverhalt in einer konventionellen, nicht-physischen Sichtweise beschrieben. Sie bedient sich der intuitiven Formulierung ” naturally

be regarded as computable“, so dass sie im Vergleich zu physischen Prinzipien wie z.B. den Gesetzen der Thermodynamik eher undeutlich ist. D. Deutsch schlug deshalb vor, Turings Hypothese in einen physikalischen Kontext zu setzen, so dass sie den gleichen erkenntnistheoretischen Status erh¨ alt wie andere physikalische Prinzipien. Er geht davon aus, das der Ausdruck functions which would naturally be regarded as computable“ interpretiert

”

werden kann als diejenigen Funktionen, die prinzipiell durch ein reales physikalisches System berechnet werden k¨ onnen. Um Mißinterpretationen des Begriffs ” naturally“ auszuschließen bedient er sich folgender Notation des Begriffs perfekte Simulation: Eine Rechenmaschine M ist f¨ ahig ein physikalisches System S perfekt zu simulieren, wenn ein Programm π(S) f¨ ur M existiert, welches M rechnerisch ¨ aquivalent zu S erscheinen l¨ aßt. Anders ausgedr¨ uckt verwandelt π(S) M in eine ” black box“, die funktionell nicht 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 ”

des physikalische Objekt einbeziehen, auf dem Messungen vollzogen werden k¨ onnen. Dagegen muss die ” universal computing machine“ nur ein idealisiertes (aber theoretisch m¨ ogliches) endliches spezifizierbares Modell sein. Die Fokussierung auf die universelle Turing-Maschine, wie sie im Original zu

2

finden ist, muss notwendigerweise ersetzt werden durch die allgemeinere Bedingung, dass die Maschine mit endlichen Mitteln ( by finite means“) 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¨ angt, und (iii) die Regel, welche die Bewegung beschreibt, im mathematischen Sinn endlich angegeben werden kann (z.B. als eine nat¨ urliche Zahl). Sowohl Turingmaschinen wie auch Quantencomputer gen¨ ugen diesen Axiomen. Dennoch ist die Aussage des Church-Turing-Prinzips so stark, dass Turing Maschinen im klassischen Sinn ihr nicht gen¨ ugen, da sie kein physikalisches System simulieren k¨ onnen. Es gibt n¨ amlich nur abz¨ ahlbar viele M¨ oglichkeiten, einen endlichen Eingabezustand f¨ ur eine Turingmaschine zu erzeugen. Dagegen gibt es in der (klassischen) Dynamik ¨ uberabz¨ ahlbar viele

m¨ ogliche (Eingabe-)zust¨ ande. Der universelle Quantencomputer ist allerdings schon dazu in der Lage.

2 Quanten-Turing-Maschinen

2.1 Definition der QTM

Im Gegensatz zum stochastischen Computer k¨ onnen 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, P c = |α c | ² , die c zugeordnet ist. Die euklidische L¨ ange

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¨ ange 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 festgelegtem blank-Symbol #, Q eine endliche Menge von Zust¨ anden mit festgelegtem Anfangszustand q 0 und Endzustand q f = q 0 , und δ die deterministische ¨ Uberf¨ uhrungsfunktion

δ : Q × Σ → Σ × Q × {L, R}

ist ¹ . Die TM besitzt ein in beide Richtungen unendliches Band aus Zellen,

¹ Manchmal wir die Menge {L, R} noch um ein N , das soviel wie ” keine Bewegung“

bedeutet, erweitert. Wir betracheten diese Variante der TM jedoch nicht.

3

die mit Z indiziert sind. Außerdem gibt es einen Schreib/Lesekopf der sich entlang des Bandes bewegen kann. Eine Konfiguration c ist eine ” Momentaufnahme“ 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¨ ucken, das c in einem Schritt auf c folgt. Per

Konvention legt man fest, dass die Startkonfiguration folgende Bedingungen erf¨ ullen muss: Der Schreib-/Lesekopf ist in Zelle 0 (Startzelle), und die TM ist im Zustand q 0 . Eine Startkonfiguration hat die Eingabe x ∈ (Σ−#) ^∗ , wo-

bei x in die Zellen 0, 1, 2, ..., geschrieben wird und alle anderen Zellen leer gelassen werden. Eine TM h¨ alt bei einer Eingabe x, wenn sie in endlicher Zeit in den Zustand q f eintritt. Die daf¨ ur ben¨ otigten Schritte werden als Laufzeit f¨ ur die Eingabe x bezeichnet. Falls eine TM h¨ alt, 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¨ ur alle Eingaben h¨ alt, berechnet demnach eine Funktion (Σ − #) ^∗ → Σ ^∗ .

Als n¨ achstes folgt die Definition der QTM nach Deutsch in leicht abgewandelter Form. Um die ¨ Uberf¨ uhrungsamplituden effizient berechnen zu k¨ onnen, beschr¨ ankt man sie auf rationale Zahlen. Es wurde nachgewiesen, dass diese Einschr¨ ankung die Rechenst¨ arke der QTM nicht einschr¨ ankt. Es wurde sogar gezeigt, dass die Amplitudenwerte {0, ± 3 5 , ± 4 5 , 1} ausreichen um eine universelle QTM zu konstruieren.

Definition 2.2. Sei ˜ C eine Menge von α i ∈ C f¨ ur die es einen deterministischen Algorithmus gibt, der den realen und imagin¨ aren Teil von α i bis auf einen Abstand von ±2 ⁻ⁿ 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¨ anden mit einem festgelegtem Anfangszustand q 0 und einem festgelegtem Endzustand q f = 0 , und δ die Quanten- ¨ Uberf¨ uhrungsfunktion

C ^Σ×Q×{L,R} δ : Q × Σ → ˜

ist. Die TM besitzt ein in beide Richtungen unendliches Band aus Zellen, die mit Z indiziert sind. Wir definieren Konfigurationen, Startkonfigurationen und Endkonfigurationen genauso wie bei deterministischen TMs. Sei S der Vektorraum (mit innerem Produkt) der endlichen komplexen Linearkombinationen aller Konfigurationen von M mit der euklidischen Norm. Wir nennen jedes Element φ ∈ S eine Superposition von M. Die QTM M definiert einen linearen Operator U M : 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

4

i α i c i befinden, wobei jedes α i einem ¨ in der Superposition ψ = Ubergang

δ(p, σ, τ, q, d) zugeordnet wird und c i die neue Konfiguration ist, die aus δ resultiert. Wenn man diese Abbildung auf ganz S ausweitet erh¨ alt man den linearen Zeitevolutionsoperator U m .

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¨ ahlbar-dimensionale) quadratische Matrix repr¨ asentiert werden, deren Reihen und Spalten man Konfigurationen der QTM zugeordnet und in der jedes Matrixelement a ij der Amplitude entspricht, welche die Konfiguration c i nach c j ¨ uberf¨ uhrt.

Die n¨ achste Definition ist f¨ ur die Einhaltung der quantenphysikalischen Gesetze von großer Wichtigkeit.

Definition 2.3. Eine QTM wird als wohlgeformt bezeichnet, wenn ihr Zei-tevolutionsoperator U m die euklidische L¨ ange bewahrt.

Eine wohlgeformte QTM M muss also ein U m besitzen, der f¨ ur jede denkbare Superposition von M sicherstellt, dass die Summe der Wahrscheinlichkeiten

i |α i | ² aller Konfigurationen c i immer 1 ist.

Als n¨ achstes definieren wir Regeln zur Beobachtung von QTMs. Messungen werden dabei auf die berechenbare Basis von S beschr¨ ankt. Dies ist n¨ otig, 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 ψ = i α i c i beobachtet oder gemessen wird, so erh¨ alt man das Ergebnis c i mit c i mit der Wahrscheinlichkeit |α i | ² . Die neue Superposition von M ist dann ψ = c i .

Es ist auch m¨ oglich, partielle Messungen durchzuf¨ uhren, beispielsweise nur ¨ uber 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: ψ = i α0 i c0 i + i α1 i c1 i . c0 i und c1 i sind jene Konfigu-

rationen, die eine 0 bzw. 1 in der ersten Zelle stehen haben. Wenn man nun eine Messung ¨ uber der ersten Zelle ausf¨ uhrt, ist die Wahrscheinlichkeit eine 0 zu messen P r[0] = eine neue Superposition ψ =

also, der mit dem gemessenen Ergebnis im Einklang steht, bleibt erhalten, wobei seine Amplitude wieder die euklidische L¨ ange haben muss.

Im weiteren Verlauf beschr¨ anken wir uns beim Messen angehaltene QTMs und bezeichnen das Ergebnis als Ausgabe. Dies f¨ uhrt nicht zu einem Verlust von Berechnungsst¨ arke, wie in [3] nachgewiesen wird. Allgemein k¨ onnen wir

5