Der Quantencomputer:

Inhaltsverzeichnis

1 Der Quantencomputer 51.1 Vergleich klassischer Computer und Quantencomputer . . . . . . . . . . . . . 51.2 Reversible Operationen und Gatter . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Quanteninformationsverarbeitung . . . . . . . . . . . . . . . . . . . . . . . . 91.4 Quantenfehlerkorrektur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2 Quantenalgorithmen 132.1 Der DeutschAlgorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3 Experimentelle Realisierung 17

4 Der Weg zum Quantencomputer 23

5 Quantenmechanik und Computer 27

6 Der ShorAlgorithmus 316.1 Der klassische ShorAlgorithmus . . . . . . . . . . . . . . . . . . . . . . . . 326.2 Die diskrete Fouriertransformation . . . . . . . . . . . . . . . . . . . . . . . . 346.3 Der Quantenalgorithmus von Shor . . . . . . . . . . . . . . . . . . . . . . . . 36

6.3.1 Theoretische Betrachtung des QuantenShorAlgorithmus . . . . . . . 366.3.2 Zahlenbeispiele fr den QuantenShorAlgorithmus . . . . . . . . . . 41

A Zahlentheoretische Grundlagen 49A.1 Kongruenzen und Restklassen . . . . . . . . . . . . . . . . . . . . . . . . . . 49A.2 Euklidischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50A.3 Chinesischer Restesatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51A.4 Eulersche -Funktion, Ordnung mod N , groer Primzahlsatz . . . . . . . . . . 51

A.4.1 Die Eulersche -Funktion . . . . . . . . . . . . . . . . . . . . . . . . 51

3

4 INHALTSVERZEICHNIS

A.4.2 Der groe Primzahlsatz . . . . . . . . . . . . . . . . . . . . . . . . . . 52A.5 Kettenbrche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

B Zahlenbeispiel fr DFTq 55

C Programm zur Berechnung der Periodizitt und der Wahrscheinlichkeitsver-teilung 59

Kapitel 1

Der Quantencomputer

1.1 Vergleich klassischer Computer und QuantencomputerEin universeller klassischer Rechner besteht aus einem Register, in dem beliebig (aber endlich)viele Bits gespeichert sind. Ein Bit an Information entspricht einer Entscheidung zwischen zweiMglichkeiten wie ja oder nein, 1 oder 0, wahr oder falsch. In einem Digitalrechner ist einBit an Information beispielsweise die Ladung eines Kondensators: Ein geladener Kondensatorbezeichnet eine 1, ein entladener Kondensator eine 0. Ein weiteres Merkmal des klassischenComputers ist das Programm, das aus einer frei whlbaren und teilweise auch wiederholtenAbfolge logischer Verknpfungen (auch Gatter genannt) besteht, die auf die Bits des Registerswirken. blicherweise whlt man als elementare Operationen die aus der mathematischen Lo-gik bekannten Verknpfungen AND, OR und NOT. Die NOT-Verknpfung ist eine einwertigeGrundfunktion, d.h. dass sie auf ein Eingangsbit wirkt. Das Eingangsbit wird invertiert: ist es 1,dann wird das Ausgangsbit 0 und umgekehrt. Das AND und das OR sind zweiwertige Grund-funktionen, also Verknpfungen, die auf zwei Eingangsbits wirken. Das AND bewirkt, dassdas Ausgangsbit nur dann 1 wird, wenn beide Eingangsbits 1 sind und in den sonstigen Fllenzu 0 wird. Bei der OR-Verknpfung ist das Ausgangsbit 1, wenn mindestens ein Eingangsbit1 ist. Aus diesen drei elementaren Operationen knnen alle logischen Verknpfungen erzeugtwerden. Ein klassischer Rechner kann jede arithmetische Aufgabe bewltigen, wenn er bereine geeignete Auswahl von Gattern verfgt.Der Quantencomputer ist bisher lediglich ein theoretisches Konstrukt mit der Aufgabe, denQuanteninformationsprozess formal zu analysieren. In der experimentellen Realisierung wer-den zwar stetig Fortschritte erzielt, aber bis ein lauffhiger Quantencomputer, der einen inKapitel 6 dargestellten Algorithmus durchfhren kann, existiert, bedarf es noch erheblicherForschungs- und Entwicklungsarbeit. Ein Quantencomputer funktioniert nun, indem er die ge-wohnten quantenmechanischen Niveauzustnde und Superpositionszustnde nutzt. Eine Auf-reihung von Wasserstoffatomen kann im Prinzip ebenso gut Bits speichern wie eine Reihe vonKondensatoren. Ein Wasserstoffatom im energetischen Grundzustand wrde z.B. einer 0 (imfolgenden |0) entsprechen und eines im ersten angeregten Zustand einer 1 (|1).1 Ein Spin-1

2-

System, z.B. der Spin eines Elektrons, kann ebenfalls zur Speicherung von Bits benutzt wer-den: Spin up reprsentiert den Zustand |1 und spin down den Zustand |0. Zustzlich knnen

1Die anderen Anregungszustnde sollen hierbei keine Rolle spielen.

6 1. Der Quantencomputer

Elektronen aber auch jeden Zustand annehmen, der einer berlagerung (auch Superposition)|0 + |1 mit ||2 + ||2 = 1 entspricht. Im Kontext der Quanteninformationsverarbeitungnennt man die Zustnde eines Zweiniveausystems Qubits. Da aber Speichern nicht ausreichendist, muss es mglich sein, Information in das System einzubringen, sie zu verarbeiten und wie-der auszulesen. Das bedeutet, aus den vorhandenen Bits durch logische Verknpfungen neue zugewinnen und wieder aus dem System herauszuholen, also lesen, rechnen und schreiben. Frdas Problem Information in ein System einzubringen, fand der amerikanische Physiker IsidorIsaac Rabi (1898-1988) als erster eine Lsung: Ein Wasserstoffatom befinde sich in seinemGrundzustand mit der Energie E0. Um eine Null einzuschreiben, tue man gar nichts. Um eineEins einzuschreiben, muss man das Atom auf einen Zustand hherer Energie E1 anregen. Dazubestrahlt man es mit Laserlicht aus Photonen, deren Energie genau gleich der Differenz von E1und E0 ist. Ein Laserpuls wird dann das Atom vom Grundzustand in den angeregten Zustandversetzen (siehe auch [1]). Das Auslesen der Bits aus dem Quantensystem funktioniert hnlichwie das Schreiben: Dazu wird das System ebenfalls mit einem Laserpuls bestrahlt. War es imangeregten Zustand, wird ein Photon abgestrahlt, war es im Grundzustand, wird kein Photon re-gistriert. Vom Schreiben und Lesen ist es dann noch ein Schritt zum Rechnen. Welche Anstze,Ideen und Voraussetzungen dafr ntig sind, soll im Folgenden dargelegt werden.

1.2 Reversible Operationen und Gatter

Wie in Abschnitt (1.1) schon erlutert, besteht ein Computer aus einem komplexen Netzwerkvon untereinander verbundenen Operationen, den Gattern. Die klassischen Operationen sinddas NOT, AND und OR, wobei die letzten zwei Elemente irreversibel sind 2. Da die Gesetzeder Quantenmechanik in der Zeit reversibel sind, mssen die Operationen der Quanteninforma-tionsverarbeitung ebenfalls reversibel sein3, d.h. Verknpfungen wie das AND und OR eignensich nicht fr den quantenmechanischen Informationsverarbeitungsprozess. Richard Feynman[2, 3] verfolgte wie schon Benett [4] Fredkin und Toffoli [5] den Ansatz, Computermaschi-nen zu betrachten, die den reversiblen Gesetzen der Quantenmechanik gehorchen. An dieserStelle soll zunchst dargelegt werden, dass sich reversible Operationen ebenfalls eignen, logi-sche Verknpfungen zu erzeugen. Wie auf diesen Grundlagen unter Benutzung der Gesetze derQuantenmechanik ein Computer konstruiert werden kann, ist in Kapitel 5 erlutert.Um eine universelle Maschine zu erstellen, knnen drei reversible Operationen benutzt wer-den. Das erste ist das NOT, das aus einer Leitung besteht. Es verliert keine Information und istdurch nochmalige Anwendung reversibel. In der folgenden Abbildung ist das NOT symbolischdargestellt mit der zugehrigen Tabelle fr die sich ergebenen Werte des Inputs a und Outputsa:

a a'

+

=

>

a a

0 11 0

Abbildung 1.1: NOT

2Das AND und das OR sind irreversibel, da durch Anwenden irgendeiner Operation der Ausgangszustand nichtreproduziert werden kann; z.B. im Fall der Verknpfung OR kann man nicht sicher sagen, aus welchen Wertender Eingangsbits der Wert 1 im Ausgangsbit resultiert.

3Dieser Zusammenhang wird in Kapitel 5 verdeutlicht.

1.2. Reversible Operationen und Gatter 7

Das zweite reversible Element ist das CONTROLLED NOT. Es besteht aus zwei Eingangslei-tungen a und b und zwei Ausgangsleitungen a und b. Die erste Leitung ist die Kontrollleitung,fr die a = a gilt. Diese Kontrollleitung ist notwendig, um Zweideutigkeiten im Output zubeheben. Das CONTROLLED NOT bewirkt, dass ein NOT auf b ausgefhrt wird, wenn a = 1.Ansonsten gilt b = b (siehe Abbildung 1.2). Da man fr den Output b = 0 nicht sagen kann,ob er aus (a, b) = (0, 0) oder (a, b) = (1, 1) entstanden ist, wird diese Zweideutigkeit imCONTROLLED NOT durch die Kontrollleitung a = a behoben. Damit ist auch das CON-TROLLED NOT durch einfache Wiederholung reversibel.

a'

b

a

b'

a b a b

0 0 0 00 1 0 11 0 1 11 1 1 0

Abbildung 1.2: CONTROLLED NOT

Die Kombination nur dieser beiden Elemente reicht noch nicht aus, um beliebige logischeFunktionen auszufhren. Man bentigt noch eine weitere Operation mit drei Leitungen, dasCONTROLLED CONTROLLED NOT (siehe Abbildung 1.3). Dieses besteht aus zwei Kon-trollleitungen, die unverndert bleiben (a = a, b = b), sowie einer dritten Leitung c, auf dieNOT angewandt wird, wenn a = b = 1 gilt, und die ansonsten unverndert bleibt. Ist die dritteEingangsleitung z.B. auf c = 0 gesetzt, dann erhlt man c = 1 nur dann, wenn a = b = 1gilt. Die drei Kombinationen fr (a, b), nmlich (0, 0), (0, 1) und (1,0) ergeben alle den Wert 0,so dass zwei Bits bentigt werden, um die Mehrdeutigkeit aufzuheben. Diese sind in den Kon-trollleitungen a und b realisiert, so dass das CONTROLLED CONTROLLED NOT reversibelist.

a'

b

c

a

b'

c'

a b c a b c

0 0 0 0 0 00 0 1 0 0 10 1 0 0 1 00 1 1 0 1 11 0 0 1 0 01 0 1 1 0 11 1 0 1 1 11 1 1 1 1 0

Abbildung 1.3: CONTROLLED CONTROLLED NOT

In der Informatik wurde gezeigt, dass man mit diesen drei Elementen und deren Kombinatio-nen jeden logischen Kreislauf und somit auch einen universellen Computer erzeugen kann.Die folgenden Beispiele sollen dies verdeutlichen. In den in diesem Zusammenhang erstelltenGattern reprsentiert jede Leitung ein Bit; die Gatter werden in ihren Operationen von linksnach rechts gelesen.

8 1. Der Quantencomputer

Man erhlt einen ADDER (Halbaddierer), indem man zuerst das CONTROLLED CONTROL-LED NOT und dann das CONTROLLED NOT in Folge benutzt (siehe Abbildung 1.4). DiesesGatter erzeugt von den Eingangsleitungen a, b und 0 den ursprnglichen Wert von a in derzugehrigen Ausgangsleitung a, die Summe von a und b in b und den bertrag des CON-TROLLED CONTROLLED NOT angewendet auf a und b in c.

a'

b

c = 0

a

Summe b' = a + b

bertrag = c'

a b c a b c

0 0 0 0 0 00 1 0 0 1 01 0 0 1 1 01 1 0 1 0 1

Abbildung 1.4: ADDER

Ein etwas komplizierterer Schaltkreis ist der FULLADDER (Volladdierer), welcher einenbertrag c von einer vorherigen Addition zu a und b addiert und eine zustzliche Eingangs-leitung d = 0 besitzt (siehe Abbildung 1.5).

b = b'

d = 0

a = a'

bertrag = d'c'

a

b

cSumme c' = a + b + c

s'

c

s' = a + b

a a

b

a b c d a s c d

0 0 0 0 0 0 0 00 0 1 0 0 0 1 00 1 0 0 0 1 1 00 1 1 0 0 1 0 11 0 0 0 1 1 1 01 0 1 0 1 1 0 11 1 0 0 1 0 0 11 1 1 0 1 0 1 1

a b c d a b c d

0 0 0 0 0 0 0 00 0 1 0 0 0 1 00 1 0 0 0 1 1 00 1 1 0 0 1 0 11 0 0 0 1 0 1 01 0 1 0 1 0 0 11 1 0 0 1 1 0 11 1 1 0 1 1 1 1

Abbildung 1.5: FULLADDER

Dieser Schaltkreis besteht aus vier Operationen, die sich aus den primitiven Elementen CON-TROLLED CONTROLLED NOT und CONTROLLED NOT zusammensetzen. Neben der to-talen Summe c = a + b + c und dem bertrag d erhlt man auf den zwei anderen Ausgangs-leitungen weitere Informationen: Den Startwert a und einen Zwischenwert s, der sich whrendder Routine ergeben hat. Neben den gewnschten Outputwerten erhlt man also auch Abfall,aus dem sich jedoch die Werte der Eingangsleitungen rekonstruieren lassen. Dies ist eine fr re-versible Systeme typische Vorgehensweise. Im Fall eines FULLADDERs geschieht dies durch

1.3. Quanteninformationsverarbeitung 9

eine zustzliche Anwendung eines CONTROLLED NOTs auf die ersten zwei Leitungen a unds. In dem Schaltbild des FULLADDERs ist dies durch die gestrichelten Linien dargestellt.Auf diese Art und Weise kann man also durch verschiedene Kombinationen einen beliebigenlogischen Kreislauf erzeugen, der n Bits reversibel in n Bits umformt. Wenn das zu berech-nende Problem selbst reversibel ist, hat man keinen zustzlichen Abfall. Allgemein bentigtman aber zustzliche Leitungen, die die fr die Reversibilitt notwendigen Informationen spei-chern.

1.3 QuanteninformationsverarbeitungIm idealen Fall besteht die Quanteninformationsverarbeitung aus einer Sequenz von unitrenOperationen auf Registerzustnden 4, die aber mglicherweise durch Mess- und Ausleseprozes-se unterbrochen und gesteuert werden knnen [6, 7, 8]. Ein Quantencomputer besteht letztlichaus einem endlich groen Quantenregister, also einer endlichen Anzahl N von Qubits. We-sentlich ist, dass das Quantenregister nicht nur in einem seiner 2N Basiszustnde vorliegenkann, wie z.B. |0|1|0 oder |1|0|1 fr N = 3, sondern auch in einer beliebigen Linear-kombination dieser Zustnde, d.h. in verschrnkten Zustnden wie |0|1|0+ |1|0|1 mit||2 + ||2 = 1. Da das Quantenregister in gewissem Sinne gleichzeitig in allen seiner mg-lichen Zustnde sein kann, knnen bestimmte Informationsverarbeitungen in hohem Maeparallel stattfinden. Dies ist das besondere Potential der Quanteninformationsverarbeitung, diein sogenannten Quantengattern stattfindet, deren Operationen reversibel sind, wie schon in Ka-pitel 1.2 erlutert. Diese Gatter haben die gleiche Anzahl von Inputs und Outputs, wobei jedeLeitung hier ein Qubit reprsentiert. Die zur Quanteninformationsverarbeitung bentigten Ope-rationen sind im einfachsten Fall sogenannte Ein-Qubit- und Zwei-Qubitoperationen, wie z.B.das CONTROLLED NOT (siehe auch Kapitel 1.2). Man kann zeigen, dass sich jede Rechen-operation in eine Folge von Operationen und zwar eines CONTROLLED NOTs zusammen mitallgemeinen unitren Transformationen eines einzelnen Qubits zerlegen lsst [9].Beispiele fr Ein-Qubitoperationen sind die Hadamartransformation und die Phasenverschie-bung. Die Hadamartransformation H ist von der Gestalt:

H =12

(1 11 1

). (1.1)

Betrachtet man die Zustnde

|0 =(

10

), |1 =

(01

),

so bewirkt die Hadamartransformation folgendes:

H|0 = 12

(1 11 1

)(10

)=

12

(11

)4In der Quantenmechanik ist die Operation, die einen Eingangszustand z.B. |a, |b, |c, |d reversibel in einen

Ausgangszustand |a, |b, |c, |d berfhrt, ein unitrer Operator, d.h. ein Operator U fr den UU = 1I gilt.

10 1. Der Quantencomputer

=12

[(10

)+

(01

)]=

12(|0+ |1)

und

H|1 = 12

(1 11 1

)(01

)=

12(|0 |1) .

Eine weitere wichtige Ein-Qubittransformation, die Phasenverschiebung, hat die Form:

P =

(1 00 i

). (1.2)

Betrachtet man wiederum die Zustnde |0, |1 dann bewirkt die Phasenverschiebung folgen-des:

P |0 =(

1 00 i

)(10

)= |0

und

P |1 =(

1 00 i

)(01

)= i|1 = eipi2 |1.

Als elementare Zwei-Qubitoperation ist das CONTROLLED NOT (siehe Abbildung 1.2)

CONTROLLED NOT =

1 0 0 00 1 0 00 0 0 10 0 1 0

(1.3)zu nennen.

Eine weitere, fr einen spter angesprochenen Quantenalgorithmus (siehe Kapitel 6) grundle-gende Zwei-Qubitoperation ist die Phasenvernderung, wenn der Zustand |1|1 vorliegt:

Sjk =

1 0 0 00 1 0 00 0 1 00 0 0 ei

. (1.4)Alle fr die quantenmechanische Informationsverarbeitung relevanten Transformationen lassensich aus der Hadamartransformation, der Phasenverschiebung und dem CONTROLLED NOTzusammensetzen [10].

1.4. Quantenfehlerkorrektur 11

1.4 QuantenfehlerkorrekturIn den bisherigen Ausfhrungen wurde davon ausgegangen, dass man Quantengatteropera-tionen vllig fehlerfrei ausfhren kann. Dies ist in der Realitt allerdings nicht der Fall. Dadie Informationstrger den Gesetzen der Quantenmechanik unterliegen, ist das Problem derQuanteninformationsverarbeitung eng mit dem Problem der Dekohrenz verbunden. Die uni-tre Zeitentwicklung ist nur in vollstndig isolierten Systemen gewhrleistet. Jedes reale Sy-stem ist jedoch, wenn auch nur schwach, an Freiheitsgrade seiner Umgebung gekoppelt, unddie unkontrollierte Wechselwirkung der Informationstrger mit der Umgebung verursacht eineDekohrenz im Zustandsraum der Qubits. Quantenmechanische Verschrnkung und Superpo-sitionszustnde werden dadurch empfindlich gestrt, was die Anzahl der ausfhrbaren Ope-rationen begrenzt und die Realisierbarkeit von Quantenrechnern sehr schwierig gestaltet. DieQuantenfehlerkorrektur wird daher zu einem wesentlichen Bestandteil eines realen Quanten-computers.Klassische Rechner sind recht tolerant gegenber ungewollten ueren Einflssen, da jedesBit z.B. mit Hilfe einer makroskopischen Anzahl von Elektronen gespeichert wird. Im Prinzipkann ein solches Bit mit Hilfe einer ziemlich starken und deshalb sehr unwahrscheinlichen Wechselwirkung mit der Umgebung spontan umspringen. Quantencomputer speichern dagegendie Information in quantenmechanischen Zweizustandssystemen (siehe Kapitel 1.1). In diesemFall reichen Ste oder schon eine viel schwchere Wechselwirkung mit der Umgebung aus,um ein Qubit umspringen zu lassen. Wenn man etwa zur Informationsspeicherung zwei Zu-stnde eines Atoms benutzt, so kann der angeregte Zustand ungewollt mit einer bestimmtenWahrscheinlichkeit durch die spontane Emission eines Photons zerfallen. Auerdem knnenin Quantencomputern nicht nur Bitaustausche als Fehler auftreten, sondern auch Phasenfehler.Auf den ersten Blick scheinen daher reale Quantencomputer selbst bei einer sehr optimistischenAbschtzung der Fehlerquellen um viele Zehnerpotenzen von den Anforderungen entfernt zusein, die man brauchen wrde, um etwa eine Zahl mittels des ShorAlgorithmus (siehe Kapitel6) zu faktorisieren. Es wurden jedoch Fehlerkorrekturmethoden gefunden, die Quantenrechnergegenber ungewollten ueren Einflssen sehr viel unanflliger machen, was zur HoffnungAnlass gibt, dass die prinzipielle Realisierung des Quantencomputers durchaus mglich ist.Insbesondere wurde gezeigt, dass man im Prinzip beliebig lange Rechnungen verlsslich aufeinem Quantencomputer ausfhren kann, solange die einzelnen Quantengatteroperationen miteiner gewissen Mindestgenauigkeit ausgefhrt werden. Dies ist insofern bemerkenswert, alsdass jede Fehlerkorrekturmethode die Anzahl der Operationen, die Zahl der bentigten Qubitsund somit auch die Fehleranflligkeit erheblich erhht. Die Lsung dieses Problems liegt in derwiederholten Anwendung der Fehlerkorrektur. Die momentanen Abschtzungen der erforder-lichen Mindestgenauigkeit zeigen, dass sie bei einem Fehler in 104 Operationen liegt [11].Im Folgenden soll ein kleiner Einblick in die Funktionsweise solcher Fehlerkorrekturmethodenvermittelt werden. Diese Methoden bauen auf den klassischen Konzepten der Fehlerkorrekturauf. Die zugrundeliegende Idee ist, in die Speicherung der Information in den Qubits eine ge-wisse Redundanz einzubauen. Zum Beispiel kann man ein Qubit an Information in drei realenQubits kodieren, indem man festlegt, dass die |0 durch |0|0|0 dargestellt wird und die |1durch |1|1|1. Nimmt man an, dass in einem der drei Qubits ein Bitflip 5 als Fehler auftritt, hatman trotzdem noch genug Information, um den Fehler zu finden und zu beheben. Jeder mg-

5Eine Bitposition wechselt von 0 auf 1 oder umgekehrt.

12 1. Der Quantencomputer

liche Bitflipfehler hat ein ihm eigenes Fehlersyndrom, was am Beispiel des Produktzustands|0|0|0 illustriert werden soll:

1. & 2. Qubit 2. & 3. Qubit Qubits Fehlergleich gleich |0|0|0 keinerverschieden gleich |1|0|0 Flip im ersten Qubitverschieden verschieden |0|1|0 Flip im zweiten Qubitgleich verschieden |0|0|1 Flip im dritten Qubit

Zum Beispiel liegt kein Fehler vor, wenn sowohl die ersten zwei als auch die letzten zweiQubits gleich sind. Wenn die ersten zwei Qubits in unterschiedlichen Zustnden sind, die letz-ten zwei aber in demselben Zustand, so ist ein Flipfehler im ersten Qubit aufgetreten, usw.Da diese Information in den drei Qubits gespeichert ist, kann man durch einen geeignetenSatz von Quantengattern den Fehler detektieren und rckgngig machen. Wichtig ist, nur die(Un)gleichheit von Qubits zu messen, nicht die Qubits selbst, da dann Information zerstrtwrde. Im Folgenden sollen allgemeine Qubits |x und |y (|x kann z.B. |0 oder |1 sein) be-trachtet werden, um die Operation, die das Gewnschte leistet, zu erlutern (siehe Abbildung1.6): Sind die Qubits |x und |y gleich, wechselt das Hilfsqubit, welches zunchst auf |0 ge-setzt ist, kein- oder zweimal den Zustand und bleibt so am Ende im Zustand |0. Sind |x und|y verschieden, so liegt das Hilfsqubit am Ende im Zustand |1 vor.

|x

|y

|z

|x

|y

|0

x y 0 x y z0 0 0 0 0 00 1 0 0 1 11 0 0 1 0 11 1 0 1 1 0

Abbildung 1.6: Messung von Qubits auf Fehler

Mit einer hnlichen Methode knnen auch Phasenfehler behandelt werden. Dazu nutzt man dieTatsache aus, dass ein Phasenfehler durch Anwendung der Hadamartransformation zu einemBitflipfehler wird (siehe dazu [12, 13, 14]).

Kapitel 2

Quantenalgorithmen

Die Erweiterung des Informationsbegriffes erlaubt es, neue Algorithmen, sogenannte Quan-tenalgorithmen, zu entwickeln. Die Mglichkeit, durch quantenmechanische berlagerung ver-schiedene Registerzustnde quasi gleichzeitig zu verarbeiten, wird Quantenparallelismus ge-nannt und verspricht, gewisse mathematische Probleme auf einem Quantencomputer effizien-ter zu lsen, als dies mit einem klassischen Computer mglich ist. Die Anforderungen an diePrzision, mit der die Gatteroperationen realisiert werden mssen, um beliebige Quantenalgo-rithmen implementieren zu knnen, sind allerdings sehr hoch. Die Theorie des fehlertolerantenQuantenrechnens liefert einen Wert in der Grenordnung von 104 als relative Ungenauigkeitpro Rechenschritt bzw. Gatteroperation [11]. Mit anderen Worten, von 10000 Operationen darfhchstens eine Operation fehlerhaft sein, damit der Quantencomputer noch funktioniert.Die neuen Kapazitten des Quantencomputers sollen in diesem Kapitel an Hand eines ein-fachen Beispiels, dem DeutschAlgorithmus verdeutlicht werden. Dieses Beispiel zeigt, dassQuantencomputer Probleme lsen knnen, vor denen klassische Computer kapitulieren. Au-erdem kann man an diesem Beispiel schon ein wesentliches Charakteristikum komplizierterQuantenalgorithmen, den Quantenparallelismus, ablesen. Ein zweites Beispiel ist der ShorAlgorithmus (siehe Kapitel 6), der der Faktorisierung von groen Zahlen dient. Dieser kann alseiner der wichtigsten bisher ausgearbeiteten Algorithmen angesehen werden.

2.1 Der DeutschAlgorithmus

Der DeutschAlgorithmus dient der effizienten Berechnung einer binren Funktionf : {0, 1} {0, 1}. Dazu stelle man sich vor, man habe eine Blackbox, die diese binreFunktion berechnet, die also ein Bit x in ein einzelnes Bit y := f(x) verwandelt. Nimmt manan, dass eine Berechnung 24 Stunden dauert, dann mssen die Vorgnge in der Box dement-sprechend recht kompliziert sein. Weil jeder der beiden Funktionswerte f(0) und f(1) einender mglichen Werte 0 oder 1 annehmen kann, gibt es insgesamt vier Mglichkeiten fr dieBerechnung der Funktion und man mchte wissen, was die Box berechnet. Nun bentigt mandas Resultat aber in 24 Stunden. Es sei angenommen, dass es reichen wrde zu wissen, obf(x) konstant ist, also f(0) = f(1), oder nicht konstant ist, also f(0) 6= f(1). Ein klassischerComputer msste f(0) und f(1) berechnen und dann die Ergebnisse vergleichen. Dies wrdefr beide Funktionswerte f(0) und f(1) insgesamt 48 Stunden dauern. Der Quantencomputer

14 2. Quantenalgorithmen

hingegen bentigt nur eine Messung, was nun dargestellt werden soll:Im Folgenden bezeichnet die binre Addition (mod 2)1, d.h.

0 10 0 11 1 0

.

Angenommen die Blackbox berechnet f(x) und der Computer ist so programmiert, dass erauf den Produktbasiszustnden |x|y mit x, y {0, 1} die Operation

U(|x|y) = |x|y f(x) mit x, y {0, 1} (2.1)ausfhrt (siehe Abbildung 2.1).

>|y f(x))>|x

>|y>|x

U

Abbildung 2.1: Operation U(|x|y) = |x|y f(x)

Diese Operation bedeutet in Worten, dass die Maschine das zweite Qubit verndert, wenn f aufdas erste Qubit 1 ergibt und dass die Maschine gar nichts macht, wenn f auf das erste Qubit0 ergibt. Um die Reversibilitt sicherzustellen, muss die Blackbox zwei Eingnge haben, diedurch die Qubits |x und |y realisiert sind.Die Quantenmechanik erlaubt es, als Eingangszustand einen berlagerungszustand der bei-den Qubits |x = |0+|1

2und |y = |0|1

2zu whlen, was der Schlssel zur Lsung von

Deutschs Problem ist. Diesen Eingangszustand prpariert man, indem man ausgehend vom Zu-stand |0|0 zunchst ein NOT (siehe Kapitel 1.2) auf den zweiten Eingang anwendet, was denZustand |0|1 liefert (siehe Abbildung 2.2). Im Anschluss daran wird die Hadamartransfor-mation (siehe Kapitel 1.3) auf beiden Leitungen ausgefhrt und man erhlt den gewnschtenAnfangszustand

|in := |x|y =( |0+ |1

2

)( |0 |12

). (2.2)

Nach Anwendung von U auf |in, ergibt sich|out := U |in

= U

( |0+ |12

)( |0 |12

)=

1

2U (|0|0 |0|1+ |1|0 |1|1)

=1

2(|0|0 + f(0) |0|1 + f(0)+|1|0 + f(1) |1|1 + f(1)).

1Eine Einfhrung in die zahlentheoretischen Grundlagen der Kongruenzen und Restklassen befindet sich imAnhang A.1

2.1. Der DeutschAlgorithmus 15

Nun sei fr z {0, 1}, 1 + z = z, wobei 1 = 0 und 0 = 1. Mit folgender Tabelle f(0) f(1)0 f(0) f(1)

1 f(0) f(1)

erhlt man

|out = 12(|0|f(0) |0|f0)+ |1|f(1) |1|f(1))

=12

[|0(|f(0) |f(0)

2

)+ |1

(|f(1) |f(1)

2

)]. (2.3)

Wie erwartet kommen in diesem Zustand Zustnde fr die Funktionswerte sowohl fr x = 0als auch fr x = 1 vor. Diese Eigenschaft wird als Quantenparallelismus bezeichnet.Durch eine Messung kann man allerdings nicht beide Funktionswerte explizit bestimmen: So-bald man das erste Qubit misst und dies z.B. den Wert 1 ergibt, enthlt das zweite Qubit nurnoch Information ber den Funktionswert f(1). Die Frage nach der Konstanz der Funktionkann dennoch in einem Schritt beantwortet werden; dazu betrachte man folgende Fallunter-scheidung:

(1) f konstant f(0) = f(1)

|out =( |0+ |1

2

)( |f(0) |f(0)2

). (2.4)

(2) f nicht konstant f(0) 6= f(1) f(1) = f(0), f(1) = f(0)

|out =( |0 |1

2

)( |f(0) |f(0)2

). (2.5)

Also gilt:

|out =( |0 |1

2

)( |f(0) |f(0)2

). (2.6)

Daran erkennt man, dass der Zustand des ersten Qubits davon abhngt, ob die Funktion kon-stant ist (+) oder nicht (). Folglich muss man nur noch messen, in welchem dieser beidenZustnde sich das erste Qubit befindet, um die Frage nach der Konstanz der Funktion beant-worten zu knnen, d.h. die Blackbox wird nur einmal durchlaufen.Konkret kann man durch Anwenden der Hadamartransformation (siehe Kapitel 1.3) die beidenin |out enthaltenen orthogonalen Zustnde unterscheiden:

|0 |0+ |12

(2.7)

|1 |0 |12

. (2.8)

16 2. Quantenalgorithmen

Man erhlt also den Zustand |0 fr eine konstante Funktion und |1 fr nicht konstantes f .Alle Operationen, die fr die Durchfhrung des DeutschAlgorithmus notwendig sind, sind inder folgenden Abbildung nochmals zusammenfassend dargestellt:

>|0

>|0U

NOT H

HH Messung

Abbildung 2.2: Schematische Darstelllung des DeutschAlgorithmus

Verallgemeinert lsst sich folgendes festhalten: Mit Hilfe des Quantenparallelismus ist es zwarnicht mglich alle Funktionswerte gleichzeitig auszuwerten, gewisse globale Eigenschaften derFunktion sind aber doch effektiver bestimmbar als mit klassischen Algorithmen. Dies ist einMerkmal fr Quantenalgorithmen. So beruht der wesentliche Schritt im spter (Kapitel 6 ) be-handelten QuantenShorAlgorithmus darauf, die Periode einer Funktion zu finden. Dafr wirdwiederum der Quantenparallelismus verwendet, indem man eine diskrete Fouriertransformierteberechnet, von der die Periode mehr oder weniger direkt abgelesen werden kann. Die diskre-te Fouriertransformierte wird als berlagerung aller mglichen Verschiebungen der Funktionmit verschiedenen Phasen quantenparallel berechnet. Der DeutschAlgorithmus berechnet freinen besonders einfachen Fall ebenfalls die Periode einer Funktion.

Kapitel 3

Experimentelle Realisierung

Es stellt sich die Frage, warum man heute noch keine Quantencomputer hat, die die schnel-len Rechnungen, wie beispielsweise die Faktorisierung groer Zahlen mittels des ShorAlgorithmus (siehe Kapitel 6), durchfhren knnen.Fr die Implementierung eines Quantencomputers ist es notwendig, ein physikalisches Systemzu prparieren, das es erlaubt, Quantenzustnde verlsslich zu speichern sowie mit Quanten-operationen gezielt und przise zu manipulieren. In der Praxis gibt es bisher nur wenige Kan-didaten, die diese Voraussetzungen erfllen. Zur Realisierung eines Quantencomputers msseneine Reihe von Bedingungen gewhrleistet sein, die nun weiter beleuchtet werden sollen:

Identifikation einzelner Qubits, Adressierbarkeit und Auslesen der Bits, Implementierung von Quantengattern, schwache Dekohrenz, effiziente Implementierung von Fehlerkorrekturen, Skalierbarkeit von wenigen auf viele Qubits.

Das Hauptproblem der experimentellen Realisierung ist die Forderung nach guter Manipulier-barkeit der Information einerseits und mglichst guter Abschirmung strender Einflsse ande-rerseits. Zum einen mssen die Qubits fr die Informationsverarbeitung selektiv transformiertoder ausgelesen werden (Ein-Qubitoperationen) und idealerweise auch zwei beliebige Qubitsmiteinander verknpft werden knnen (Zwei-Qubitoperationen); zum anderen soll der Koh-renzverlust minimiert werden, so dass die Qubitzustnde mglichst lange ihre quantenmechani-sche Verschrnkung beibehalten. Jede unkontrollierte Wechselwirkung erzeugt eine Verschrn-kung des Quantencomputers mit der Umgebung, welche die Zustnde so beeinflusst, dass dieVoraussetzungen zur Ausfhrung von Quantenrechnungen nicht mehr erfllt sind. Diese unge-wollten Effekte fasst man unter den Begriff der Dekohrenz zusammen. Kurz gesagt erfordertdie Manipulierbarkeit der Information einen gewissen Einfluss der Umgebung, die Speicherungder Information jedoch ein mglichst von der Umwelt isoliertes System. Bentigt wird infolge-dessen ein gezielt an- und ausschaltbarer Einfluss der Umgebung. Auerdem sollte es mglich

18 3. Experimentelle Realisierung

sein, das System ohne allzu groen Aufwand zu vergrern; das System sollte skalierbar sein,d.h. die Hinzunahme eines weiteren Qubits sollte die Adressierbarkeit und Dekohrenz nichtvervielfachen, sondern nur anteilig erhhen.Eine Vorreiterrolle beim Bau von Quantencomputern spielt die Quantenoptik. Als Trger derQuanteninformation kommen in der Quantenoptik einzelne Atome und Photonen in Frage.Ziel ist die Speicherung einzelner Atome in Fallen und die Prparation eines Atoms im Be-wegungsgrundzustand [15, 16, 17, 18, 19]. Mittels Laserpulsen knnen die internen Zustndeder Atome (die Qubits) gezielt manipuliert werden. Somit lassen sich Ein-Qubitoperationendurch Wechselwirkung von Laserlicht mit Atomen realisieren. Die Implementierung von Zwei-Qubitoperationen lsst sich entweder durch Ankopplung an Hilfsfreiheitsgrade, wie z.B. kol-lektive Schwingungsmoden von gespeicherten Atomen, Ionen oder Photonen in einem Reso-nator, erreichen, oder auch durch gezielte Zweiteilchenwechselwirkungen zwischen zwei Ato-men. Zur gezielten Verschrnkung der internen Zustnde zweier Atome kann eine Reihe vonkontrollierbaren Zweiteilchenwechselwirkungen verwendet werden, deren Strke vom Zustandder Qubits abhngt. Um Ionen zu verschrnken, eignet sich die Coulomb-Wechselwirkung, de-ren Strke proportional zum inversen Abstand der Ionen ist. Zur Verschrnkung von neutra-len Atomen werden isotrope Stoprozesse bei tiefen Temperaturen (so genannte kalte Ste)verwendet. Das Wechselwirkungspotential hat allerdings nur eine sehr begrenzte Reichwei-te. Eine weitere Mglichkeit ist die Wechselwirkung zwischen permanenten Dipolmomentenvon Rydberg-Zustnden in wasserstoffartigen Atomen in statischen elektrischen Feldern. Dortwird die Wellenfunktion des Valenzelektrons so verzerrt, dass es zu einer Verschiebung desLadungsschwerpunktes der Elektronenhlle im Vergleich zum Ladungsschwerpunkt des Kernskommt. Es entsteht ein Dipolmoment, dessen Strke mit dem Quadrat der Hauptquantenzahldes Zustandes anwchst. Die Wechselwirkungsstrke zwischen den Dipolmomenten zweierbenachbarter Atome ist proportional zur vierten Potenz der Hauptquantenzahl und umgekehrtproportional zur dritten Potenz des Abstandes der Atome. Selbst fr eine Hauptquantenzahl vonweniger als 15 liefert dies wesentlich grere Wirkungsquerschnitte als kalte Ste zwischenneutralen Atomen.Ein Beispiel ist der in [20] vorgestellte Quantencomputer, der auf der Wechselwirkung von La-sern mit gekhlten Ionenketten basiert. Dies ist vermutlich der erste Vorschlag zur Verwirkli-chung eines Quantenrechners oder zumindest eines kleineren Quanteninformationssystems. Ander experimentellen Realisierung wird zur Zeit weltweit in mehreren Labors, darunter am NISTBoulder, an der Universitt Innsbruck, dem Max-Planck-Institut fr Quantenoptik in Garchingund in Los Alamos gearbeitet. Dieses Modell nutzt als Qubits ultrakalte Ionen, die zwischenzwei inneren Zustnden wechseln knnen und die eine Kette bilden, die in einer linearen Io-nenfalle, der Paul-Falle, gespeichert wird. Diese Falle besteht aus vier parallelen Metallstben.Ein zeitabhngiges Radiofrequenzpotential wird an jeweils zwei gegenberliegenden Stbenangelegt. Damit knnen sich die Ionen nur noch auf einer Linie parallel zu den Stben anord-nen. Zwei zustzliche zirkulare Elektroden dienen als Abschlsse an den beiden Enden (sieheAbbildungen 3.1, 3.2).

19

Abbildung 3.1: PaulFalle (entnommen aus [22]).

Abbildung 3.2: Ionen in der PaulFalle (entnommen aus [22]).

Um die strenden spontanen Zerflle des energetisch hheren Qubitniveaus zu minimieren,benutzt man einen metastabilen Zustand mit der verglichen mit typischen Lebensdauern imNanosekundenbereich groen Lebensdauer von etwa einer Sekunde. Die Gleichgewichtslageder Ionen im Querschnitt der Falle ergibt sich aus dem Fallenpotential. Schwingungen der Io-nenkette entsprechen kleinen Auslenkungen der Ionen entlang der Fallenachse aufgrund derCoulombabstoung. Durch Laserkhlen kann der Schwingungszustand der Ionen ausgefrorenwerden, und die Ionenkette wird im Schwingungsgrundzustand prpariert. Der Gesamtzustandder Ionenkette ist somit durch einen Zustandsvektor zu beschreiben, der ein Produktzustandder internen Ionenzustnde, des Quantenregisterzustands und der quantisierten Schwerpunkts-bewegung im Grundzustand ist. Die phononischen Freiheitsgrade dienen nun als Datenbus zurVerschrnkung der internen Ionenzustnde. Insbesondere kann ein einzelnes Ion derart mit ei-nem rotverstimmten Laserpuls bestrahlt werden, dass es vom Zustand |1 in den Zustand |0bergeht und dabei die Ionenkette durch die Abgabe eines Phonons in Schwingung versetzt.Falls das Ion im Zustand |0 ist, wird der Zustand nicht verndert. Im Fall einer Ionenkette kannin einem beliebigen zweiten Ion der interne Zustand gem |0 |1 umgeschaltet werden.Insgesamt erhlt man so einen Prozess, bei dem der interne Zustand des zweiten Ions verndertwird, sofern das erste Ion sich im Zustand |1 befindet. Wird abschlieend der Anfangszu-stand des ersten Ions wieder hergestellt, lsst sich damit die schon bekannte CONTROLLEDNOT-Operation (siehe Abbildung 1.2) realisieren [21, 23]. Jede Rechenoperation kann als eineFolge von solchen Operationen zusammen mit einfachen Zustandsnderungen der einzelnenIonen dargestellt werden. Am Beginn einer Rechnung setzt man dabei durch optisches Pumpenden Zustand aller Ionen auf einen gewnschten Anfangswert, z.B. auf |0|0 . . . |0. Um denMessprozess ausfhren, d.h. um die Bitzustnde der Ionen am Ende einer Rechnung auslesenzu knnen, verwendet man die Methode der Quantensprnge. Dabei wird die Ionenkette mitLaserlicht einer geeigneten Frequenz bestrahlt, so dass ein Ion im Zustand |1 Fluoreszenzlichtausstrahlt, whrend es im Zustand |0 dunkel bleibt. Experimentell wurden bisher quantenlogi-sche Verschrnkungsoperationen mit einem und bis zu vier Ionen nachgewiesen [18, 19].An Erweiterungen wird intensiv gearbeitet, und man hofft, in nherer Zukunft bis auf etwa zehn

20 3. Experimentelle Realisierung

Qubits zu kommen [24]. Die Ionenfallen bieten sicherlich sehr gut abgeschirmte Qubits. DieManipulierbarkeit von Qubitpaaren erscheint eher als Schwachpunkt, insbesondere bezglichgrerer Systeme. Ein weiteres Problem ist das Laserkhlen in den Grundzustand des Fallen-potentials, das eine der Voraussetzungen, zugleich aber eine Schwierigkeit der experimentellenRealisierung ist.Bei einem anderen Realisierungsvorschlag nimmt man an, dass Ionen in periodisch angeord-neten Mikrofallen gefangen werden [25], wie sie beispielsweise mit lithographischen Metho-den erzeugt werden knnen. Auch hier sind die Trger der Qubits langlebige elektronischeZustnde der Ionen. Die Ionen sind ebenfalls mit Lasern einzeln adressierbar, so dass Ein-Qubitoperationen realisiert werden knnen. Zur Verwirklichung von Zwei-Qubitoperationenmssen die Ionen in kontrollierter Weise miteinander und mit dem ueren Coulombfeld wech-selwirken. Das Grundprinzip der Realisierung der Zwei-Qubitoperationen in diesem Modell istdie Anwendung eines ueren Laserfeldes auf ein Ion, so dass seine Wellenfunktion in Abhn-gigkeit von seinem internen Zustand rumlich verschoben wird (Abbildung 3.3). Indem zweibenachbarte Ionen in |1 mit dem Laser verschoben werden, ergibt sich eine Energieverschie-bung im ueren Feld, und somit tritt ber die Zeit integriert eine Phasennderung auf. DasErgebnis ist ein Phasengatter (siehe Gleichung 1.4) mit einer Phase, die sich aus der zeitlichenIntegration der nderung der Coulomb-Wechselwirkungsenergie der beiden benachbarten Io-nen ermitteln lsst. Einen Quantencomputer, der auf diesen Ideen basiert, zeigt Abbildung (3.4).Dabei nimmt man an, dass ein Ion als Kopf und ein zweites Ion nahe aneinander gebracht wer-den knnen; es ist nicht notwendig, die beiden Ionen einzeln zu adressieren.

Energie|0|0 1

d|0|1 1d+x2(t)

|1|0 1dx1(t)

|1|1 1d+x2(t)x1(t)

Abbildung 3.3: Schema einer Zwei-Qubitoperation mit in unabhngigen Mikrofallen gespeicherten Io-nen. Um eine Operation auszufhren, werden die Ionen rumlich verschoben, falls sieim Zustand |1 sind (entnommen aus [26, 25, 27]).

21

Abbildung 3.4: Ein skalierbarer Quantencomputer. Die Qubits (Ionen) sind in unabhngigen Fallen inder Ebene gefangen. Ein weiteres Ion, als Kopf bezeichnet, wird ber der Ebene bewegtund kann mit einem beliebigen anderen Ion eine Zwei-Qubitoperation ausfhren. Da-mit lassen sich Verschrnkungsoperationen zwischen zwei beliebigen Ionen ausfhren(entnommen aus [25]).

Der Abstand zwischen den Ionen in der Ebene kann hingegen gro sein, da keine direkte Wech-selwirkung zwischen ihnen erforderlich ist. Eine solche zweidimensionale Anordnung hat of-fensichtlich die Eigenschaft, zu einer groen Zahl von Quantenbits skalierbar zu sein. Ein wei-terer Vorteil ist, dass die Forderung nach niedrigsten Temperaturen in diesem Modell nichtbesteht.Ein Vorschlag, der besonderes Interesse ausgelst hat, betrifft die Entwicklung eines Quanten-computers mittels Kernspinresonanz [28, 29, 30]. Einige der ersten Realisierungen von Quan-tenalgorithmen wie des Deutsch-Algorithmus [31, 32] und einer sehr einfachen Grover-Suche[33] basieren auf Kernspinresonanzexperimenten, wie sie aus Anwendungen in der physika-lischen Chemie und auch in der Medizin sehr gut bekannt sind. Dabei sind die Qubits durchden Spin der Kerne einzelner Atome in den betrachteten Moleklen, etwa Chloroform, gege-ben. Ein-Qubitoperationen werden durch gezielte Pulse magnetischer Felder bei abgestimmtenFrequenzen erreicht. Bei Zwei-Qubitoperationen nutzt man hingegen die sehr schwache Wech-selwirkung der Kernspins miteinander. Der wesentliche Unterschied zu den Vorschlgen ausder Quantenoptik besteht darin, dass anstelle von Einzelsystemen ein Ensemble von Molek-len verwendet und das System auerdem bei endlicher Temperatur betrachtet wird. Obwohldieser Ansatz einige schne Demonstrationen ermglicht hat, wird sein Nutzen durch zweiNachteile eingeschrnkt: Die Wechselwirkung zwischen den Kernspins ist nicht gut manipu-lierbar. Auerdem lassen sich die Systeme kaum wesentlich vergrern, da die verwertbarenSignale bei greren Systemen schnell sehr klein werden und so nicht mehr skalierbar sind.Hinzu kommt noch der Nachweis, dass die mit NMR-Methoden bislang erzeugten Quantenzu-stnde bei endlicher Temperatur separabel sind, d.h. keine Verschrnkung aufweisen [34].Eine Reihe von Vorschlgen beruht auf Systemen der Festkrperphysik in Anlehnung an diehochentwickelte Halbleitertechnologie. Hier besteht ein wissenschaftliches Umfeld mit Erfah-rungen in der Erzeugung von immer kleineren geordneten Strukturen (Mikrochips, Nanotech-nologie), auf die man aufbauen kann. Daraus kann man schon vermuten, dass diese VorschlgeStrken in der Manipulierbarkeit und der Skalierbarkeit haben werden. Ihre Schwche liegt in

22 3. Experimentelle Realisierung

der Abschirmung der Umgebung. Zwei Modelle beruhen auf dem Spin. Bei dem einen Modellbesteht das Qubit aus den Niveaus eines Kernspins gezielt eingebrachter Fremdatome, etwaPhosphor 31P in einen Siliziumhalbleiter [35]. Ein konstantes Magnetfeld B0 von ungefhr 2Tesla trennt die beiden Niveaus. Ein-Qubitoperationen werden ber ein zeitlich oszillierendessehr schwaches Magnetfeld Bosz von 103 Tesla in Resonanz realisiert. Die Resonanzfrequenzkann dabei ber die Hyperfeinwechselwirkung mit der Elektronenwolke, die das Donatora-tom Phosphor umgibt, beeinflusst werden. Zieht man mittels einer positiven Gatespannung V1die Elektronen weg, vermindert sich diese Wechselwirkung und die Resonanzfrequenz sinktebenfalls. Zwei-Qubitoperationen knnen kontrolliert aus- oder eingeschaltet werden, indemdie Elektronenwolken benachbarter Donatoratome durch eine negative Gatespannung V2 aus-einander gehalten werden oder durch eine positive Gatespannung V2 verschmolzen werden.Kernspins haben den Vorteil, dass sie sehr gut von der Umgebung isoliert sind.Bei dem zweiten Vorschlag bernimmt der Spin eines berzhligen Elektrons auf einem Quan-tenpunkt die Rolle des Qubits [36]. Die Ein-Qubitoperationen werden wiederum ber Magnet-felder realisiert. Die Zwei-Qubitoperationen werden ber verschiedene Gatespannungen, diedie Elektronenverteilungen in den Quantenpunkten verformen, erzeugt. Als Beispiele fr dieRealisierung von Quantenoperationen sei hier auf Vorschlge mit Cooper-Paaren in Josephson-Kontakten [37] und mit Spinzustnden von Elektronen in Quantenpunkten [36] als Trger vonQubits verwiesen. Auerdem gibt es einen Vorschlag, einen NMR-Quantencomputer mit Me-thoden der Festkrperphysik zu realisieren [35].Eine andere Mglichkeit nutzt von vornherein ein Quantenphnomen, das makroskopisch auf-tritt: die Supraleitung [38]. Fr diesen Vorschlag gibt es die Realisierung eines einzelnen Qubits[39]. Dies ist zwar noch wenig, aber man hofft, dass die Entwicklung in diese Richtung nochErfolge erzielen wird.Die Erwartung fr die Zukunft ist, dass whrend der nchsten 5 Jahre kleine Quantencomputermit etwa 10 Qubits im Labor zur Verfgung stehen werden. Dies wird sicher die experimen-telle Grundlage fr eine Reihe von fundamentalen Experimenten zur Teilchenverschrnkung,zum Messprozess und fr Dekohrenzstudien in der Quantenmechanik sein. Ferner werdenauch Proof-of-Principle-Experimente in der Quanteninformationsverarbeitung erfolgen kn-nen. Wann die tatschliche Anwendung als Quantencomputer im Sinne von Shor und Grovermglich sein wird, wann also effizientere Implementierungen skalierbarer Konzepte, die sichauf eine grere Anzahl von Qubits anwenden lassen, erfolgen knnen, bleibt abzuwarten.

Kapitel 4

Der Weg zum Quantencomputer

Das Phnomen Quantencomputer vereinigt die Ideen der klassischen Informationstheorie, derInformatik und der Quantenphysik. Die Informationstheorie ist eine 1948 von dem amerikani-schen Mathematiker Claude Elwood Shannon begrndete mathematische Theorie, die sich mitder strukturellen und quantitativen Erfassung und mit den (statistischen) Gesetzmigkeiten derbermittlung und Verarbeitung von Nachrichten sowie den in ihnen enthaltenen Informationenbeschftigt. Die Informationstheorie war die erste Theorie, die es erlaubte, den Informations-begriff mathematisch zu fassen und so eine quantitative Untersuchung von Informationsber-tragung und -verarbeitung zu ermglichen.Die Grundlagen der Informatik wurden ungefhr zur gleichen Zeit formuliert wie ShannonsInformationstheorie. Als Vter der Informatik sind Charles Babbage (1791-1871) und AlanTuring (1912-1954) zu nennen. Charles Babbage ist wegen seiner Beitrge zum grundlegendenDesign des Computers durch seine analytische Maschine auch als Vater des automatischenRechnens bekannt. Seine Differenzmaschine war speziell fr das Erstellen von astronomi-schen und mathematischen Tabellen (z.B. Logarithmentafeln) sowie Versicherungstabellen be-stimmt.Die in der Mitte der 1930er Jahre von Alan Turing entwickelte universelle Maschine wirdnach ihm Turing-Maschine genannt. Die Turing-Maschine ist ein idealisiertes mathemati-sches Modell eines Computers, das benutzt werden kann, um die Grenzen der Anwendungeines Computers zu fassen. Es erhebt keinen Anspruch darauf, ein praktisches Design fr je-de aktuelle Maschine zu sein, sondern dient eher dazu, die essentiellen Merkmale eines jedenComputers darzulegen. Turing wollte mit seiner Maschine zeigen, wie ein Rechenvorgang ineine Folge kleinster und einfachster Schritte zerlegt werden kann.Der dritte Aspekt, der im Quantencomputer Anwendung findet, ist das Einbeziehen der quan-tenmechanischen Sichtweise. Die ersten Ideen dazu befassen sich mit der Umwandlung derArbeitsschritte einer Turing-Maschine in einen quivalenten reversiblen Prozess und dem Auf-stellen eines Hamiltonoperators fr das dazugehrige Quantensystem. Diese Ideen basierenauf einer Arbeit von Bennett [4], die zeigte, dass ein universeller klassischer Computer, wie dieTuring-Maschine, unter Beibehaltung seiner einfachen Prinzipien reversibel gemacht werdenkann (siehe auch [40]).In den frhen 1980er Jahren zeigte Benioff vom Argonne National Laboratory (Illinois), dassein Computer, der ausschlielich nach den Gesetzen der Quantenmechanik arbeitet, theoretischfunktionieren kann [41, 42]. Er stellte ein Modell einer reversiblen Turing-Maschine vor, die

24 4. Der Weg zum Quantencomputer

lesen und schreiben konnte, sowie Operationen vollstndig ausfhrte und dafr quantenmecha-nische Wechselwirkungen benutzte. Obwohl sich die daraus resultierende Maschine bezglichdes Rechenaufwands noch wie ein klassischer Computer verhielt, ist dies doch als der erste Ver-such anzusehen, die Quantenmechanik in das mathematische Modell eines Computers einzu-bringen. In diesem Zusammenhang machte Benioff verschiedene Vorschlge fr Turing-artigeHamiltonoperatoren. Allerdings waren seine Ideen keine vollstndige Untersuchung der Quan-tenrechner, da sie lediglich klassische Rechner reproduzierten.Darber hinausgehende berlegungen stellte der Physik-Nobelpreistrger Richard Feynman[2, 3] an. Er beschftigte sich mit der kontroversen Frage, wie gut klassische Computer Quan-tensysteme simulieren knnen. Er schloss aus seinen Betrachtungen, dass klassische ComputerQuantensysteme nicht effizient simulieren knnen, Quantensysteme sich hingegen im Prinzipimmer fr die Simulation irgendeines anderen Systems eignen. Dies war der erste Hinweisdarauf, dass die rechnerische Effektivitt einer Quantenvorrichtung, speziell eines Quantensi-mulators, die Kapazitt einer klassischen Maschine bertreffen knnte. Seinen Ansatz kannman allerdings nicht als ausgereiftes Computersystem bezeichnen, da er zwar voraussetzte,dass jede Wechselwirkung zwischen angrenzenden Zweizustandssystemen geordnet werdenkann, jedoch nicht beschrieb, wie dies geschehen soll.Im Jahr 1985 gelang David Deutsch vom Mathematischen Institut der Universitt Oxford (Eng-land) bezglich des Quantencomputers ein entscheidener Schritt vorwrts: Deutsch beschriebdie erste Quanten-Turing-Maschine [43]. Dies war eine Maschine, die lesen, schreiben undOperationen durchfhren konnte, die alle durch quantenmechanische Wechselwirkungen zu-stande kamen, und deren Register jetzt zustzlich in nicht klassischen Zustnden existierenkonnte. Whrend eine herkmmliche klassische Turing-Maschine nur 0, 1 oder Leerzeichenan jeder Stelle des Registers lesen konnte, konnte die Quanten-Turing-Maschine gleichzeitigauch eine Superposition von 0 und 1 entschlsseln. Daher hat die Quanten-Turing-Maschinedas Potential, mehrere Inputs eines Problems simultan im gleichen Register zu entschlsselnund eine Berechnung mit allen Inputs in der gleichen Zeit durchzufhren, die bentigt wird,um eine Berechnung klassisch auszufhren. Dieser Effekt wird Quantenparallelismus genannt.Die Gesetze der Quantenmechanik erlauben es allerdings nicht, mehr als einen dieser Werteexplizit zu extrahieren. Das Problem liegt darin, dass das Erhalten eines Wertes eine Messungnotwendig macht, durch die die restlichen Ergebnisse unwiderruflich verloren gehen. Somitist das endgltige Resultat nicht besser als das mit einer klassischen Turing-Maschine erzielte.Trotzdem erhlt man in effizienter Weise verschiedene globale Eigenschaften der Outputs (sie-he dazu Kapitel 2.1).Essentiell ist das System von Deutsch eine Reihe von Zweizustandssystemen und sieht eheraus wie eine Registermaschine als wie eine Turing-Maschine; beides sind jedoch universelleklassische Rechenmaschinen. Deutsch bewies, dass fr die Simulation eines jeden physikali-schen Systems eine unitre Entwicklung aufgestellt werden kann, wenn eine Entwicklung desZweizustandssystems durch eine bestimmte kleine Anzahl von einfachen Operationen mglichist. Die gleichen Ideen legte er auch der Betrachtung zugrunde, wie man eine Turing-hnlicheVerhaltensweise erzielen kann.Diese einfachen Operationen von Deutsch werden Quantengatter genannt, da sie eine analogeRolle zu den binren logischen Gattern des klassischen Computers einnehmen. Verschiede-ne Wissenschaftler untersuchten im Anschluss daran die kleinste Klasse von Gattern, die frden Quantencomputer notwendig ist. Es zeigte sich, dass Deutschs Simulator im strikten Sin-ne nicht universell ist. Trotzdem ist seine Idee insofern effektiv, als dass man auf diese Weise

25

eine groe Klasse von Quantensystemen simulieren kann [44]. Auch in anderer Hinsicht istdie Arbeit von Deutsch hervorzuheben: Sie fhrte Konzepte fr Quantennetzwerke [45] undlogische Gatter ein, welche fr den Quantencomputer sehr wichtig sind und es berhaupt erstermglichen, sich weitere Gedanken ber die Quantenrechner zu machen.Auf der Grundlage des Modells der Quanten-Turing-Maschine war man nun in der Lage, dieFhigkeiten des Quantencomputers zu untersuchen. Diese Untersuchungen beziehen sich inerster Linie auf die Berechenbarkeit, d.h. auf die Art der mit dieser Maschine zu lsenden Pro-bleme, den damit verbundenen Aufwand, d.h. dem Verhltnis von Arbeitsspeicher und Zeit-aufwand zur Gre des Problems, sowie auf die Allgemeingltigkeit, d.h. die Frage, ob eineMaschine alle anderen effizient simulieren kann. Im Folgenden werden diese einzelnen Aspek-te genauer dargelegt.Fr die Betrachtung der Allgemeingltigkeit sei zunchst die Church-Turing-These vorange-stellt: Jede (im intuitiven Sinn) berechenbare Funktion ist auch Turing-berechenbar. Feynmanstellte 1982 jedoch fest, dass eine klassische Turing-Maschine die Quantenmechanik nicht ef-fizient simulieren kann.Die Diskrepanz zwischen den Aussagen von Church-Turing und Feynman fhrte zu einer Um-formulierung der Church-Turing These durch David Deutsch [43]: Jedes endlich realisierbarephysikalische System kann im endlichen Sinn perfekt durch eine universelle Computerma-schine simuliert werden. Diese Aussage kann nur dann mit Feynmans Beobachtung ber dieEffektivitt von Quantensystemsimulationen in Einklang gebracht werden, wenn man das Mo-dell einer Computermaschine auf die Quantenmechanik sttzt.Den Aspekt der Berechenbarkeit muss man unter folgendem Blickwinkel betrachten: Die Com-putertheorie befasst sich damit, welche Probleme in endlicher Zeit auf einem Computer gelstwerden knnen. Wenn es im Hinblick auf das betrachtete Computermodell keinen Algorithmusgibt, der garantiert, in endlicher Zeit eine Antwort fr das gegebene Problem zu finden, gilt dasProblem fr dieses Computermodell als unberechenbar. In Bezug auf den Quantencomputerbewies wiederum Deutsch [43], dass der Quantencomputer verschiedene Outputs berechnenkann, deren Berechnung durch deterministische Turing-Maschinen nicht mglich ist, da klas-sische deterministische Turing-Maschinen darauf beschrnkt sind Funktionen, d.h. mathemati-sche Prozeduren, zu berechnen, die ein einzelnes reproduzierbares Ergebnis besitzen. Es gibtaber durchaus Probleme, die nicht durch die Anwendung einer Funktion lsbar sind, wie z.B.das Erzeugen von echten Zufallsvariablen. Daher kann eine Turing-Maschine das Erzeugen vonZufallsvariablen nur vortuschen.Whrend sich die Berechenbarkeit damit befasst, welche Probleme mit einem Computer lsbarbzw. unlsbar sind, geht es bei der Betrachtung des Aufwands darum, wie effizient der Com-puter die Probleme lsen kann. Die Effizienz ist eine wichtige Frage in der Informatik. DieTatsache, dass ein Computer ein Problem theoretisch lsen kann, garantiert nicht dessen Ls-barkeit mit der heutigen Technologie in der Praxis. Die Lsung von sehr komplexen Problemenkann durch zu hohen Bedarf an Laufzeit oder Speicherplatz auf klassischen Computern nichtpraktikabel sein. Informatiker haben ein Klassifikationsschema fr die Beschreibung des Auf-wandes von verschiedenen realisierbaren Algorithmen auf unterschiedlichen Computertypenentwickelt. Das grte gemeinsame Ma der Effizienz zeichnet sich durch das Verhltnis derKomplexitt des Problems zur Gre der Zeit oder des Speicherplatzes, die zur Lsung einesProblems bentigt werden, aus. Vereinfacht gesagt ist die Gre des Speicherplatzes die Anzahlder bentigten Bits, um in dem Computer das Problem anzugeben. Die Klassifizierung wurdeentwickelt, um die Schwierigkeit eines Problems quantitativ zu bestimmen. Diese Einteilung

26 4. Der Weg zum Quantencomputer

basiert auf der mathematischen Form einer Funktion, die die Vergrerung des rechnerischenAufwands in Abhngigkeit von der Gre des Problems beschreibt. Der grte quantitativeUnterschied liegt zwischen einem polynomial wachsenden Aufwand (diese Probleme werdenals lsbar erachtet) und einem exponentiell wachsenden Aufwand (diese Probleme werden alsnicht lsbar erachtet).Zur Verdeutlichung betrachte man die Multiplikation zweier groer Zahlen p q = N unddas Faktorisieren der Zahl N . Es ist relativ leicht, zwei groe Zahlen p und q miteinander zumultiplizieren, wogegen die Umkehroperation, das Finden der Faktoren von N , sich weitausschwieriger gestaltet:

10433 16453 = ? leicht (polynomial)? ? = 171654149 schwer (exponentiell)

Wenn in binrer Notation die zu multiplizierenden Zahlen eine Gre von L Bits haben, dannkann die Multiplikation in einer Zeit proportional zu L2, also polynomial in L, durchgefhrtwerden. Fr die Faktorisierung sind die besten bekannten klassischen Methoden fr Zahlen mitungefhr 100-150 Dezimalstellen das mehrfache polynomiale quadratische Sieb [46], sowiedas Zahlfeldsieb [47, 48] fr Zahlen mit mehr als 110 Dezimalstellen. Die Laufzeit dieser Al-gorithmen wchst strker als polynomial mit L, der Anzahl von Bits, die bentigt werden, umdie zu faktorisierende Zahl N anzugeben (L log2N ): Der beste Faktorisierungsalgorithmusvon Zahlen erfordert eine Zeit der Ordnung exp(L 13 log(L) 23 ) (dazu mehr in Kapitel 6).Mitte der 1980er Jahre lie das Interesse am Quantencomputer zunchst nach. Das lag dar-an, dass sich kein mathematisches Problem fand, das mit einem Quantenrechner besser oderschneller zu lsen wre, als mit einem klassischen Computer.In den frhen 1990er Jahren wurde die Suche nach solchen Problemen von verschiedenen Wis-senschaftlern wie Deutsch und Jozsa [49, 50], Berthiaume und Brassard [51, 52], Bernstein undVazirani [53] erneut aufgenommen. In dieser Hinsicht gelang Simon mit dem Simonalgorith-mus [54] und Peter W. Shor von den AT & T-Bell-Laboratorien in Murray Hill (New Jersey)mit dem Shoralgorithmus [49, 55, 56, 57, 58, 14, 59, 60, 61] der entscheidende Durchbruch.Shor diskutierte u.a. die Faktorisierung groer Zahlen unter Benutzung von Quantenfourier-transformationen. Die Methode der Anwendung von Quantenfouriertransformationen ging vonCoppersmith [62] und Deutsch aus (dazu auch [63]). Weitere wichtige Quantenalgorithmenwurden von Grover [64, 65, 66, 14, 67], Durr und Hoyer [68] und Kitaev [69] vorgestellt. 1991beschrieb Jozsa zustzlich noch eine Klasse von Funktionen, die nicht mit Hilfe des Quanten-parallelismus berechnet werden knnen [70].Theoretisch sind in den letzten Jahren durch die Entwicklung von Quantenalgorithmen undder Quantenfehlerkorrektur groe Fortschritte erzielt worden. Dagegen stehen die experimen-telle Realisierung und der Einbezug der theoretischen Konzepte in die Praxis erst am Anfang,wenn auch mit Quantengattern und der Teleportation schon erfolgreiche Laborergebnisse er-zielt wurden. Der entscheidende Schritt zum skalierbaren Quantencomputer mit einem gre-ren Rechenumfang ist nach heutigem Stand noch nicht absehbar.

Kapitel 5

Quantenmechanik und Computer

Wie kann nun unter Benutzung der Gesetze der Quantenmechanik ein Computer gebildet wer-den? Man stellt einen Hamiltonoperator fr ein System wechselwirkender Teilchen auf, dassich wie ein Gesamtsystem verhlt, welches einem universellen Computer dient. Der Hamil-tonoperator soll alle internen Rechenoperationen im Detail beschreiben, nicht aber die Wech-selwirkungen mit den ueren Einflssen beinhalten, wie das Einlesen des Inputs und Lesendes Outputs.Man betrachtet als Prototyp ein Zweizustandssystem, also z.B. das Spin-1

2-System eines

Elektrons. Jedes Bit wird durch einen der beiden Zustnde |0 oder |1 dargestellt. 1Der Anschaulichkeit halber soll das Beispiel des FULLADDERs (siehe Kapitel 1.2), indem die Eingangsleitungen durch |a, |b, |c, |d und die Ausgangsleitungen durch |a, |b,|c, |d gegeben sind, nochmals aufgegriffen werden. In der Quantenmechanik ist die Opera-tion, die |a, |b, |c, |d reversibel in |a, |b, |c, |d berfhrt, ein unitrer Operator, d.h. einOperator U fr den U U = 1I gilt. Fr den FULLADDER bedeutet dies, dass der OperatorM , der aus einzelnen Operationen besteht, den Anfangszustand |in in den Ausgangszustand|out = M |in berfhrt. Die Matrix M besteht aus den Elementen NOT, CONTROLLEDNOT und CONTROLLED CONTROLLED NOT. Fr die einfachste Operation, das NOT, istder zugehrige Operator auf den Zustand |a in der Ein-Teilchen-Basis von der Gestalt

Aa =

(0 11 0

).

Diesen Operator kann man mit Hilfe des Aufsteige- und Absteigeoperators darstellen. 2 Umzu verdeutlichen, dass dieser Operator im vorliegenden Fall auf die einzelne Leitung |a wirkt,

1z.B. |0 = | , |1 = | ,oder bei jedem anderen Zweizustandssystem: |0 = |Grundzustand, |1 = |angeregter Zustand

2Die Aufsteige- und Absteigeoperatoren sind von der allgemeinen Gestalt: S+ := ~| |, S := ~| |.Auf die Zustnde | , | angewendet erhlt man: S+| = 0, S| = ~| , S+| = ~| und S| = 0.Die physikalische Interpretation von S+ (Aufsteigeoperator) besagt folglich, dass S+ die Spinkomponente umeine Einheit ~ erhht. Wenn die Spinkomponente nicht mehr erhht werden kann, erhlt man den Nullzustand.Fr den Absteigeoperator S gilt das entsprechende. In der Matrixdarstellung sind S+ und S von der Form:

S+ = ~(

0 10 0

), S = ~

(0 01 0

).

Fr das Aufstellen des Operators M wird im Folgenden der Faktor ~ vernachlssigt.

27

28 5. Quantenmechanik und Computer

werden S+ und S (siehe Funote 2) in a+ und a umbenannt. In dieser Darstellung ergibtsich die Matrix Aa fr das NOT zu

Aa = a+ + a =(

0 10 0

)+

(0 01 0

)=

(0 11 0

).

Da der Operator Aa unitr ist, d.h. AaAa = 1I gilt, liegt mit NOT ein reversibles Element vor.In der gleichen Weise erhlt man die Matrix Aa,b in der Zwei-Teilchen-Basis fr das CON-TROLLED NOT:

Aa,b = aa+(b+ + b) + a+a =

1 0 0 00 1 0 00 0 0 10 0 1 0

.Im ersten Term aa+(b++b) wird durch aa+ berprft ob |a = |1 gilt. Wenn dies der Fallist, fhrt b+ + b das NOT auf |b aus. Der zweite Term a+a liest aus, ob |a = |0 gilt undwendet dann auf |b die Identitt an. Die Matrix Aa,b kann auch ber die Vorschrift

Aa,b = 1I + aa+(b+ + b 1I)erhalten werden. Dabei bewirkt die Einheitsmatrix keine Vernderung der Werte der Eingangs-leitungen. Fr den Fall, dass |a = |1 gilt, wird dies korrigiert, indem ein NOT ausgefhrtwird, anstatt |b unverndert zu lassen. Dieser Operator ist ebenfalls unitr, so dass dasCONTROLLED NOT auch ein reversibles Element ist.

Der Operator Aab,c fr das CONTROLLED CONTROLLED NOT ist von der Gestalt

Aab,c = aa+bb+(c+ + c) + aa+bb+= 1I + aa+bb+(c+ + c 1I)

=

1 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 1 0 00 0 0 0 0 0 0 10 0 0 0 0 0 1 0

.

Auch hier gilt die Unitaritt von Aab,c und die daraus folgende Reversibilitt des CONTROL-LED CONTROLLED NOTs.Das Gatter des FULLADDERs besteht aus fnf Operationen und somit erhlt man die MatrixM aus dem Produkt der einzelnen Operatoren der notwendigen Operationen 3:

M = Aa,bAb,cAbc,dAa,bAab,d.

Da diese Matrix aus einem Produkt einzelner unitrer Matrizen besteht, gilt die Unitarittsbe-dingung. M ist somit eine reversible Operation, und M fhrt |out in |in ber. Zu beachten

3Mit Aa,b Aa,b 1Ic : C8 C8

29

ist hier, dass man die Anwendung der einzelnen Operationen in der Matrixschreibweise vonrechts nach links ausliest, im Gegensatz zu den schematischen Darstellungen wie in Abbildung(1.5).Verallgemeinert stellt sich folgendes Problem: Sei A1, A2, A3, . . . , Ak eine Folge von Operato-ren, die auf n Leitungen wirken. Die notwendige 2n 2n-Matrix M , fr die |out = M |ingilt, ist das Produkt M = Ak A3A2A1. Wie implementiert man M experimentell?In der Quantenmechanik ist der Zustand zum Zeitpunkt t in einem System mit Hamiltonopera-tor H gegeben durch e i~Htin, mit dem Anfangszustand in. Die Schwierigkeit besteht darin,fr eine gegebene Zeit t den Hamiltonoperator H zu finden, der M = e i~Ht erzeugt, wenn Mein solches Produkt von nichtvertauschbaren Matrizen ist. Die Entwicklung von e i~Ht lautet

ei~Ht =

nl=0

( i~Ht

)l 1l!= 1 iHt

~ H

2t2

2~2+ i

H3t3

6~3+H4t4

24~4 . . . .

Es wird deutlich, dass H beliebig oft wirkt und so der Gesamtzustand als Superposition dieserMglichkeiten gegeben ist. Dies fhrt zu dem Ansatz, die Matrix M der einzelnen OperatorenA zu finden. Man addiert zu dem Rechenregister, das aus n Zweizustandssystemen besteht,eine vllig neue Folge von k + 1 Zweizustandssystemen, das Zhlregister. Seien S+i und Sider Aufsteige- und Absteigeoperator fr die Stelle i im Zhlregister mit 0 i k. Wenn dieStelle i besetzt ist, lautet der zugehrige Zustand |1, wenn die Stelle unbesetzt ist, |0. DerHamiltonoperator H ergibt sich zu

H =k1i=0

S+i+1SiAi+1 + hermitesch konjugiert

=k1i=0

S+i+1SiAi+1 +(S+i+1SiAi+1

)= S+1S0A1 + S+2S1A2 + S+3S2A3 + . . .+ S+kSk1Ak

+ S+0S1A1 + S+1S2A

2 + S+2S3A

3 + . . .+ S+k1SkA

k.

Unter Bercksichtigung dieser Entwicklung betrachtet man den Fall, dass sich ein Zweizu-standssystem im Zustand |1, die restlichen Zweizustandssysteme im Zustand |0 befinden.Dann bleibt auch nach der Anwendung des Hamiltonoperators H nur ein Zustand besetzt. DieAnzahl der besetzten Zustnde ist eine erhaltene Gre, da der Besetzungszahloperator N mitdem Hamiltonoperator kommutiert. Da sich whrend einer herkmmlichen Operation nie zweioder mehr Zweizustandssysteme im Zustand |1 befinden, nimmt man im Folgenden an, dass inder Operation des Computers immer nur eine Zhlregisterstelle besetzt ist. Der Anfangszustanddes Systems aus Rechen- und Zhlregister sei von der Gestalt, dass sich das Rechenregister in|in befindet und die Zhlregisterstelle i = 0 besetzt ist, alle anderen Stellen aber unbesetztsind, also |1|0 . . . |0. Wenn sich nach einiger Zeit die Stelle k des Zhlregisters im Zustand|1 befindet und damit alle anderen im Zustand |0, liegt die Vermutung nahe, dass auf dasRechenregister der Gre n die Matrix M = Ak A2A1 angewandt wurde. Dies besttigtsich folgendermaen: Angenommen man startet mit einem beliebigen Anfangszustand |indes Rechenregisters, und die Zhlregisterstelle i = 0 ist besetzt. Dann ist der einzige Term desHamiltonoperators, der auf dieses System zunchst wirken kann, der erste Term S+1S0A1.Der Operator S0 verwandelt die Zhlregisterstelle i = 0 von einem besetzten Zustand in

30 5. Quantenmechanik und Computer

einen unbesetzten. Der Operator S+1 hingegen verwandelt die Zhlregisterstelle i = 1 von ei-nem unbesetzten Zustand in einen besetzten. Somit verschiebt die Operation S+1S0A1 denZustand |1 von der Position i = 0 auf die Position i = 1 des Zhlregisters mit zustzlicherAnwendung der Matrix A1: Hierbei wirkt der Operator A1 nur auf das Rechenregister, so dassder Anfangszustand |in mit A1 multipliziert wird. Wendet man den Hamiltonoperator wie-derum auf das so erhaltene System an, wirkt nur der zweite Term S+2S1A2, der den besetztenZustand von i = 1 nach i = 2 verschiebt und die zustzliche Multiplikation von A2 auf dasRechenregister ausfhrt. Somit wurde nun insgesamt die Operation A2A1 auf den Anfangszu-stand |in dieses Registers angewandt. Auf diese Art verschiebt sich nach Durchlaufen derersten Zeile des Hamiltonoperators einerseits der besetzte Zustand |1 von der Stelle i = 0 zui = k im Zhlregister, und andererseits werden auf das Rechenregister der Gre n nachein-ander die Operationen Ak . . . A2A1 angewandt, die insgesamt die Operation M ergeben, wobeies gleichgltig ist wie dieser Zustand erreicht wird:Der Hamiltonoperator muss hermitesch sein und somit die transponiert komplex konjugiertenaller Operationen enthalten. Mit diesen Operationen kann man die bisher ausgebten rckgn-gig machen. Angenommen man befindet sich im Programm an der Stelle i = 2 des Zhlregi-sters, an der auf das Rechenregister die Operation A2A1 ausgefhrt wurde. Durch den TermS+1S2A

2 wird der besetzte Zustand von i = 2 nach i = 1 verschoben, und auf das Rechen-

register wird die Operation A2A2A1 ausgebt. Da A2A2 = 1I gilt, wirkt also nur noch A1 auf

|in. Somit kann man sich durch Anwendung der einzelnen Terme des Hamiltonoperators so-wohl vorwrts als auch rckwrts durch das Programm bewegen. Befindet man sich z.B. an derStelle i = j, haben die Matrizen A1 bis Aj auf das Rechenregister gewirkt. Dabei macht eskeinen Unterschied, ob man auf direktem Wege bis zur Stelle i = j gelangt ist, oder ob manbis dorthin sowohl vorwrts als auch rckwrts operiert hat.Auf diese Weise wurde von Feynman argumentiert, dass die Gesetze der Quantenmechanik zurRealisierung eines Computers benutzt werden knnen.

Kapitel 6

Der ShorAlgorithmus

Bereits vor Euklid (um 300 v. Chr.) war die Existenz einer Zerlegung jeder Zahl N Nin ein Produkt von Primzahlen bekannt, aber die erste klare Formulierung mit Beweisscheint von C. F. Gau (1777-1855) in den Disquistiones Arithmeticae (Art. 16) gegebenworden zu sein. Jedoch mangelt es bis in die heutige Zeit an einem effizienten Verfahren,diese Zerlegung zu finden. Erst um 1970, als die Anwendung von Paradigmen der theo-retischen Informatik auf die Zahlentheorie vollzogen wurden, erfolgte der entscheidendeDurchbruch, da diese Verknpfung erstmalig zu einer hheren Effizienz bei den Faktorisie-rungsalgorithmen fhrte. Der effizienteste klassische Algorithmus, der heute bekannt ist, istder von Lenstra und Lenstra [47, 48], der eine zum Input exponentielle Laufzeit bentigt( exp(c(log(N)) 13 (log(log(N)) 23 )) fr c = konstant). Der sehr hohe zeitliche Aufwand frdie Faktorisierung von Zahlen und eine nicht erkennbare Aussicht auf effizientere Algorithmenfhrten schlielich zur Anwendung bei Verschlsselungssystemen (z.B. der RSA-Algorithmus[71]).1994 fand Peter Shor einen Algorithmus [55, 56, 57, 58, 14, 59, 60, 61], der es mit Hilfe desQuantencomputers mglich macht, eine Zahl N in polynomialer Zeit zu faktorisieren. DieseMethode hatte so groe Auswirkungen auf die wissenschaftlichen Bereiche der Mathematik,Physik und Informatik, dass ein breites Interesse an dem Quantencomputer entstand.Den meisten Faktorisierungsalgorithmen, einschlielich dem von Shor, liegt eineStandardreduktion des Faktorisierungsproblems auf das Problem, die Periode einer Funktionzu finden, zugrunde. Shor benutzt dazu den Quantenparallelismus, um eine Superpositionaller Werte einer Funktion in einem Schritt zu erhalten, was bedeutet, dass er die diskreteFouriertransformation einer Funktion berechnet, die wie klassische Fouriertransformationenalle Amplituden der Funktion in Vielfache der Reziproken der Periode umwandelt. Bei Wie-derholung liefert die Messung des Zustands mit gewnschter Wahrscheinlichkeit die Periode,was es ermglicht, eine Zahl N zu faktorisieren. Das Finden der Periode ist allerdings nichtganz so einfach, da die diskrete Fouriertransformation in den meisten Fllen nur approximativeWerte liefert. Die Techniken fr das Erhalten der Periode sind jedoch klassisch.Im Folgenden soll der ShorAlgorithmus erlutert werden; um das Wesen des Algorithmus zubeleuchten, wird mit dem Algorithmus, der sich rein auf zahlentheoretische Grundlagen sttzt,begonnen. Im Anschluss daran wird zunchst die Diskrete Fouriertransformation erlutertum den QuantenShorAlgorithmus zuerst theoretisch betrachten zu knnen und dann mitZahlenbeispielen zu schlieen.

32 6. Der ShorAlgorithmus

6.1 Der klassische ShorAlgorithmus

Mit Hilfe des ShorAlgorithmus kann man eine beliebige ZahlN in ihre Primfaktoren zerlegen.Zu einem gegebenenN whle man eine dazu beliebige teilerfremde Zahl y, also ggT(y,N) = 1(ggT(y,N) steht fr den grten gemeinsamen Teiler von y und N ). Nun muss die Periodeoder auch Ordnung r der Funktion FN(a) = ya (mod N) gefunden werden. Dies bedeutet,dass man sich die Reste von ya bezglich der Division durch N anschauen muss. Betrgt dasErgebnis yr 1 (mod N) (siehe auch Anhang A.1), so hat man die Periode r gefunden. Diesist der Hauptbestandteil des Algorithmus, da dieser zu einer nichttrivialen Lsung x = yr/2der quadratischen Gleichung x2 1 (mod N) mit den gesuchten Faktoren von N fhrt 1 (zurErluterung siehe Exkurs 1).

Exkurs 1: Zusammenhang zwischen der quadratischen Gleichung x2 1 (mod N) undder Primfaktorzerlegung von NBetrachtet wird die quadratische Gleichung x2 1 (mod N). Diese besitzt stets die trivia-len Lsungen x = 1, die die einzigen Lsungen sind, sofern N eine ungerade Primzahlist. Dies wird wie folgt deutlich: Sei (Z /pZ ,+, ) ein Krper fr alle Primzahlen p, alsoder Restklassenkrper (mod p). In diesem Krper ist das multiplikativ inverse Elementeindeutig bestimmt und 1 das neutrale Element der Multiplikation. Das bedeutet, dass mitder quadratischen Gleichung nach jenen x gesucht wird, die zu sich selbst invers sind.

x2 1 (mod p)(x2 1) 0 (mod p)

(x 1)(x+ 1) 0 (mod p)(6.1)

In den Restklassenkrpern (mod p) sind [1]p und [p1]p = [1]p die einzigen selbstinver-sen Elemente (dabei bedeutet [a]p Restklasse (mod p)). Damit sind die trivialen Lsungenx = 1 oder x = 1 die einzigen Lsungen der Gleichung (6.1). Dies veranschaulicht auchdas folgende Zahlenbeispiel: R5 = {[0], [1], [2], [3], [4]} (siehe auch Anhang A.1)

+ [0] [1] [2] [3] [4][0] [0] [1] [2] [3] [4][1] [1] [2] [3] [4] [0][2] [2] [3] [4] [0] [1][3] [3] [4] [0] [1] [2][4] [4] [0] [1] [2] [3]

[0] [1] [2] [3] [4][0] [0] [0] [0] [0] [0][1] [0] [1] [2] [3] [4][2] [0] [2] [4] [1] [3][3] [0] [3] [1] [4] [2][4] [0] [4] [3] [2] [1]

Wenn N aber zusammengesetzt ist, d.h. in Faktoren p, q N zerlegbar ist, existieren nochzustzlich sogenannte nichttriviale Lsungen x a (mod N). Sei N = n1 n2 mitggT(n1, n2) = 1, dann gibt es folgende vier Stze von Lsungen:

a){

x1 +1 (mod n1)x1 +1 (mod n2) b)

{x2 1 (mod n1)x2 1 (mod n2)

c){

x3 +1 (mod n1)x3 1 (mod n2) d)

{x4 1 (mod n1)x4 +1 (mod n2) .

(6.2)

1Im Folgenden werden der Vollstndigkeit halber in den Exkursen Zusatzinformationen angeboten. Diese Zu-satzinformationen sind fr das Durcharbeiten des Inhalts nicht zwingend notwendig, sondern dienen dem interes-sierten Leser zur Vertiefung.

6.1. Der klassische ShorAlgorithmus 33

In allen Fllen gilt x2i 1 (mod n1) und (mod n2) und damit erfllt jedes xi auchdie Gleichung x2 1 (mod N). Laut dem Chinesischen Restesatz (Anhang A.3)hat jeder Satz eine eindeutige Lsung (mod N). Fr die Flle a) und b) erhlt manx1 1 und x2 1 (mod N), die trivialen Lsungen der Gleichung x2 1 (mod N).Fr die Flle c) und d) ergibt sich x3 a und x4 a (mod N), ein Paar nichttrivialerLsungen. Also gilt (a+1)(a1) 0 (mod N) mit a1 ungleich Null. Damit ist N einTeiler von (a+ 1)(a 1), aber kein Teiler von a 1 (mit a 1 N + 1). Somit ist derggT(N, a 1) ein nichttrivialer Faktor von N (fr a 6= 1), der ber den EuklidischenAlgorithmus (Anhang A.2) gefunden wird. Dieser letzte Schritt fr die Bestimmung derFaktoren von N ist in polynomialer Zeit durchfhrbar.Das Erhalten von Lsungen mit Hilfe der vier Stze von Gleichungen soll nun anhand ei-nes Zahlenbeispiels vorgefhrt werden: Es sei x2 1 (mod 35). Dann ergeben sich inAnlehnung an Gleichung (6.2) folgende Stze:

a){

x1 +1 (mod 5)x1 +1 (mod 7) b)

{x2 1 (mod 5)x2 1 (mod 7)

c){

x3 +1 (mod 5)x3 1 (mod 7) d)

{x4 1 (mod 5)x4 +1 (mod 7) .

Fr die Flle a) und b) ergeben sich wie erwartet die Lsungen x1 1 undx2 1 (mod 35). Hingegen erhlt man fr c) x3 6 (mod 35) bzw. frd) x4 29 6 (mod 35). Damit gilt (6 + 1)(6 1) 35 0 (mod 35), bzw.(6+1)(61) 35 0 (mod 35), aber 35 ist weder Teiler von 6 noch von6. Damithat man ein Paar nichttrivialer Lsungen der quadratischen Gleichung x2 1 (mod 35)gefunden.

Fr den ShorAlgorithmus berechnet man also zu dem gewhlten y mit ggT(N, y) = 1zunchst die Ordnung r. Wenn r eine gerade Zahl ist, setze man x = yr/2, eine nicht-triviale Lsung der quadratischen Gleichung x2 1 (mod N). Zum Schluss bleiben derggT(x 1, N) = p und der ggT(x + 1, N) = q, die die jeweiligen Faktoren p und q vonN = p q ergeben, zu berechnen.Der beschriebene Algorithmus muss nicht zum Erfolg fhren. Dies ist der Fall, wenn das ge-whlte y eine ungerade Ordnung r besitzt, da dann nicht notwendig yr/2 N gilt. Auerdemliefert das Verfahren keine verwendbare Lsung, wenn r gerade ist, aber yr/2 eine triviale L-sung von x2 1 (mod N) ist.Nun soll der ShorAlgorithmus an einem konkreten Zahlenbeispiel vorgefhrt werden. Manbetrachte die zu faktorisierende Zahl N = 21. Whle y so, dass der ggT(N, y) = 1 ist, d.h.y {2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20}. Hier sei y = 5 und die zugehrige Ordnung von5 (mod 21) erhlt man aus

51 5 (mod 21)52 4 (mod 21)53 1 (mod 21)54 16 (mod 21)55 4 (mod 21)56 1 (mod 21)

34 6. Der ShorAlgorithmus

Damit ergibt sich r = 6. Da r gerade ist, gilt x = 56/2 = 53 1 (mod 21). Dies istjedoch eine triviale Lsung der quadratischen Gleichung x2 1 (mod 21). Somit scheitert derAlgorithmus.Whle nun y = 2. Die zugehrende Ordnung ist r = 6 und man erhlt x = 8. Die Faktoren vonN = 21 ergeben sich aus

ggT(7, 21) : 21 = 3 7 + 0, also p=7ggT(9, 21) : 21 = 2 9 + 3,

9 = 3 3 + 0, also q=3.Die Zahl N = 21 lsst sich daher in 21 = 3 7 faktorisieren.

6.2 Die diskrete Fouriertransformation

Um den Quantenalgorithmus von Shor zur Faktorisierung einer Zahl N zu erlutern, sei hierzunchst ein kleiner berblick ber die diskreten Fouriertransformationen im Zusammenhangmit unitren Transformationen gegeben. Ein Zahlenbeispiel, das diesen Zusammenhang illu-striert befindet sich im Anhang BDie diskrete Fouriertransformation (mod q), im Folgenden durch DFTq abgekrzt, ist eineunitre Transformation in q Dimensionen. Sie hat bezglich einer gewhlten Basis |0, |1, . . . ,|q 1 die Form

DFTq|a = 1q

q1c=0

ei2piacq |c. (6.3)

Insbesondere bedeutet dies, dass der Zustand |0 in eine gleichfrmige Superposition allerc (mod q) transformiert wird oder allgemeiner ausgedrckt, dass die DFTq eine diskrete Fou-riertransformation der Inputamplituden durchfhrt.Fr den Algorithmus muss man die DFTq fr q N2 anwenden, wobei N die zu fakto-risierende Zahl ist und q die Form q = 2L mit L N hat. In diesem Fall kann der effizienteQuantenalgorithmus in Anlehnung an die Fast-Fouriertransformation konstruiert und in Termenvon unitren Operationen ausgedrckt werden, was nun gezeigt werden soll. Im Folgenden seiq = 2L und a eine Zahl, die in binrer Darstellung von der Form |aL1|aL2 . . . |a0 ist.Um die DFT2L zu konstruieren, bentigt man nur zwei grundlegende unitre Operationen. Dieeine ist die schon bekannte Hadamartransformation (Gleichung (1.1)), die auf das j-te Qubitangewandt wird und gegeben ist durch:

Hj =12

|0 |1(11

11

) |0|1 . (6.4)

Die andere Operation fhrt eine Zwei-Bittransformation der Qubits in den Positionen j und k,mit j < k durch, wenn sich diese im Zustand 1 befinden, unabhngig von den Zustnden deranderen Qubits (vgl. Gleichung (1.4)):

6.2. Die diskrete Fouriertransformation 35

Sjk =

|0|0 |0|1 |1|0 |1|11000

0100

0010

000

eijk

|0|0|0|1|1|0|1|1

(6.5)

mit jk = pi2kj . Die Matrix Hj wird wie in Gleichung (6.4) angedeutet in der |aj Basis und dieMatrix Sjk wie in Gleichung (6.5) angedeutet in der |aj|ak Basis, mit ai = 0, 1, dargestellt.Um eine DFT2L auf |a durchzufhren, muss man die folgende Operation L-mal wiederholen.Man numeriert jeden Durchgang mit einem Index j, der von j = L1 auf j = 0 runterluft. Frden ersten Durchgang setzt man j = L1 und wendet Hj auf das Bit aL1 an. Dann verringertman j um 1, also j = L 2, und wendet im zweiten Durchgang Sj,L1Hj auf das Bit aL2an. Fr jeden weiteren Durchgang verringert man j um 1 und wendet Sj,j+1Sj,j+2 . . . Sj,L1Hjan. Dies wird solange wiederholt, bis j = 0 ist und schliet mit der Operation H0 ab. So ergibtsich die DFT2L in der Darstellung der unitren Transformationen allgemein zu:

(H0S0,1S0,2 . . . S0,L2S0,L1) . . . (HL3SL3,L2SL3,L1)(HL2SL2,L1)(HL1).

(6.6)

Das bedeutet nun fr einen Input der Gre L, dass L Operationen Hj und L(L1)2 Operatio-nen Sj,k durchgefhrt werden mssen, also insgesamt L(L+1)2 elementare Operationen fr diegesamte DFT2L . Somit wchst die Durchfhrungszeit wie eine quadratische Funktion mit derInputgre L; folglich ist dies im Vergleich zu Algorithmen mit exponentiell anwachsendemAufwand ein effizienter Algorithmus.Wenn man die Folge (6.6) von Transformationen auf einen Zustand |a anwendet, so erhltman

DFTq|a = 1q

q1b=0

ei2piacq |b, (6.7)

wobei |b die umgekehrte Bitfolge von |c hat, also |b = |c. Also wird eine zustzlicheOperation bentigt, die entweder die Bits von |b in umgekehrter Reihenfolge anordnet, um|c zu erhalten, oder das Register von |b in umgekehrter Reihenfolge liest. Dies ndert jedochnichts an der Effizienz des Algorithmus, da beide Mglichkeiten einfach umzusetzen sind.Nun soll gezeigt werden, dass die Operationen Hj und Sj,k eine DFT2L bilden.Dazu betrachte man den bergang der Amplituden |a = |aL1 . . . |a0 zu|b = |bL1 . . . |b0 = |c0 . . . |cL1 = |c. Der Faktor 12 der Hadamartransformationwird durch die L-malige Anwendung dieser Transformation zu einem Faktor 1

q, da q = 2L.

Somit muss nun nur noch das Zustandekommen der Phase 2piacq

in der Summe (6.7) geklrtwerden. Die Matrizen Sj,k lassen die Qubits selbst unverndert und verndern lediglichderen Phase. Somit ergibt sich nur die Mglichkeit, das j-te Bit von aj auf bj zu berfhren,indem man die Hadamartransformation Hj anwendet. Durch den rechten unteren Eintrag inGleichung (6.4) wird pi zu der Phase addiert, wenn beide Bits aj und bj den Wert 1 haben; fraj bj 6= 1 bleibt alles unverndert. Die Matrix Sj,k addiert zustzlich noch pi2kj zu der Phase,

36 6. Der ShorAlgorithmus

wenn aj und bk beide 1 sind und ndert sonst nichts. Damit ergibt sich die Phasenverschiebungvon |a nach |b aus der Summe

0j

6.3. Der Quantenalgorithmus von Shor 37

1q

q1a=0

|a|ya (mod N). (6.10)

ergibt. Fhrt man eine Messung in dieser Basis durch, ist z mit z = yl (mod N) ein mglichesErgebnis. Mit der Periode r gilt dann yl = yl+jr (mod N),j N. Damit werden im erstenRegister a Werte mit a = l, l + r, l + 2r, . . . , l +Ar q 1 bestimmt, d.h., dass die Messungden Zustand

1q

q1a=0

|a 7 1A+ 1

Aj=0

|l + jr = |l (6.11)

liefert. Ziel ist es, von diesem Zustand ausgehend, die Periode r zu erhalten, und zwar miteiner Wahrscheinlichkeit in der Nhe von 1, wobei die Zahl der Messungen um diese Signifi-kanz zu erreichen, nicht exponentiell mit der Gre von N wchst. Das bedeutet, dass man denWert von r mit einer endlichen, d.h. von Null verschiedenen Wahrscheinlichkeit bestimmenmchte, wenn die obige Messung hchstens poly(log(N))-mal wiederholt wird. Hierzu ist zubemerken, dass wiederholte Messungen wegen der Besonderheiten des quantenmechanischenMessprozesses bei festem y verschiedene Werte fr l ergeben und damit auch |l variiert.Fr das Finden der Ordnung r sei zunchst der vereinfachte Fall q

r N, wobei r eine Zwei-

erpotenz ist, betrachtet, um die prinzipielle Vorgehensweise und die Anwendung der DFTq indiesem Zusammenhang zu verdeutlichen.Allgemein gilt q

r l

r 1 < A q

r l

r, und damit erhlt man fr A die Bedingungen:

l = r : A =q

r 1 (6.12)

l < r : A =q

r 1. (6.13)

Damit ergibt sich der Zustand nach der Messung zu

|l =r

q

qr1

j=0

|l + jr =q1a=0

qr1

j=0

r

qa,l+jr|a =

q1a=0

f(a)|a (6.14)

mit

f(a) :=

qr1

j=0

r

qa,l+jr. (6.15)

Auf diesen Zustand wendet man nun eine DFTq an. So erhlt man

DFTq|l = DFTqq1a=0

f(a)|a

=

q1a=0

f(a) DFTq|a

38 6. Der ShorAlgorithmus

Gl.(6.3)=

q1a=0

f(a) 1q

q1c=0

ei2piacq |c

Gl.(6.15)=

qr1

j=0

r

q 1

q

q1c=0

ei2pi(l+jr)c

q |c

=

q1c=0

qr1

j=0

r

qei2pi(l+jr)c

q |c

=

q1c=0

f(c)|c.

(6.16)

wobei

f(c) =

qr1

j=0

r

qei2pi(l+jr)c

q

=

r

qei2pilcq

qr1

j=0

ei2pi(jrc)

q

qrc, qr mit N

=1r e i2pilcq c, q

r

(6.17)ist, und somit

DFTq|l = 1r

r1=0

ei2pilr |q

r.

(6.18)

Eine Messung auf diesen Zustand liefert ein c, fr das qr= c c

q=

rgilt. Wenn

ggT(, r) = 1 gilt, kann r bestimmt werden, da c und q bekannt sind.Da zufllig gewhlt wird, ist die Wahrscheinlichkeit, dass ggT(, r) = 1 gilt, fr groer grer als 1

log(r)(siehe Anhang A.4.2). Wiederholt man diese Berechnung O(log(r)) N2, gibt es hchstens einen Bruch dr mit r < N , der Gleichung (6.27) gengt.Also erhlt man den Bruch dr in kleinsten Termen, indem man

cq auf den nchsten Bruch

rundet, dessen Nenner kleiner als N ist. Dieser Bruch kann in polynomialer Zeit gefunden

6.3. Der Quantenalgorithmus von Shor 41

werden, indem man die Kettenbruchdarstellung von cq berechnet, womit man die bestenApproximationen von cq mit Hilfe von Brchen findet (Anhang A.5). Wenn man den Bruchdr in kleinsten Termen berechnet hat und ggT(d, r) = 1 ist, hat man die gesuchte Perioder gefunden.Es gibt (r) mgliche Werte dafr, dass d relativ prim zu r ist 2. Jeder dieser Brche drliegt nahe bei einem Bruch cq , der

cq dr 12q erfllt. Da r die Ordnung von y ist, gibtes r mgliche Werte fr yl. Also gibt es r (r) mgliche Zustnde |c, ya (mod N), diees ermglichen, r zu erhalten. Da jeder dieser Zustnde mit einer Wahrscheinlichkeit vonmindestens 1

3r2vorkommt, erhlt man r mit einer Wahrscheinlichkeit von mindestens (r)3r .

Die Beachtung des Groen Primzahlsatzes und seiner Approximation, (r)r >e

log log(r) mite konstant (siehe Anhang A.4.2), erfordert eine nurO(log log(r))-malige Wiederholungder oben beschriebenen Vorgehensweise, um mit einer beliebig groen Wahrscheinlichkeitzum Erfolg zu gelangen.

6.3.2 Zahlenbeispiele fr den QuantenShorAlgorithmusIn Anlehnung an das Zahlenbeispiel aus Kapitel (6.1) soll nun fr N = 21 auch derQuantenShorAlgorithmus schrittweise vorgefhrt werden. Im ersten Beispiel wird derQuantenShorAlgorithmus fr den Fall, dass die Periode r eine Zweierpotenz ist durchge-fhrt und im Anschluss daran in Form eines zweiten Beispiels (siehe Exkurs 3) fr den Fall,dass r keine Zweierpotenz ist.

Beispiel 1: Zahlenbeispiel fr den QuantenShorAlgorithmus, wenn die Periode r eineZweierpotenz ist

1.Schritt: Benutzung des QuantenparallelismusMan whle eine beliebige Zahl y. Wenn y keine teilerfremde Zahl zu N ist, ergibt sich einFaktor von N . Ansonsten gilt ggT(y,N) = 1 und man verfhrt nach dem Algorithmus.Sei L so, dass N2 2L = q < 2N2 gilt. Zu Anfang wird auf das erste Register, das ausL-Qubits im Zustand |0 besteht, die DFTq angewandt, so dass man das Register

1q

q1a=0

|a (6.28)

erhlt. Man benutzt den Quantenparallelismus, um f(a) = ya (mod N) fr alle Zahlen von 0bis q 1 zu berechnen. Die Funktion f(a) ist in dem Quantenzustand

1q

q1a=0

|a|f(a) (6.29)

verschlsselt. Im Folgenden wird angenommen, dass y = 8 zufllig gewhlt wur-de. Da N2 = 441 und 2N2 = 882 gilt, findet man L = 9 (da 29 = 512), also

2(r) ist dabei die Eulersche -Funktion (siehe Anhang A.4.1).

42 6. Der ShorAlgorithmus

N2 = 441 29 < 882 = 2N2.Hat man beispielsweise insgesamt 14 Qubits, werden damit 9 fr a unddlog2(N)e = 5 fr f(a) benutzt, um die Superposition aus Gleichung (6.29) zu berech-nen.

2.Schritt: Konstruktion eines Zustands, dessen Amplitude die gleichePeriode wie f(a) hat

Die diskrete Fouriertransformation wirkt auf die Funktion der Amplitude in Verbindung mitdem Inputzustand. Im Hinblick darauf, dass die diskrete Fouriertransformation genutzt wird,um die Periode r von f(a) zu erhalten, wird ein Zustand konstruiert, dessen Amplitudenfunk-tion dieselbe Periode wie f(a) hat.Um einen solchen Zustand zu generieren, misst man die letzten dlog2(N)e Qubits des Zustan-des von (6.29), die f(a) verschlsseln. Das Ergebnis ist ein zuflliger Wert z = yl (mod N).Der Wert l ist an sich nicht von Interesse, sondern nur der Effekt, den die Messung auf die Su-perposition hat. Die Messung projiziert den Zustandsraum auf den Unterraum, der kompatibelmit dem gemessenen Wert ist, so dass der Zustand nach der Messung

q1a=0

g(a)|a|ya (mod N) mit g(a) = k a,l+jr (k : Normierungsfaktor) (6.30)

ist. Damit verbleibt im ersten Register eine berlagerung aller a, die ya = yl (mod N)erfllen, brig, d.h. es gilt a l (mod r).Wenn man zwei aufeinanderfolgende a in der Summe messen knnte, wre die Periode rgefunden. Aber die Gesetze der Quantenmechanik erlauben nur eine Messung; danach ist derZustand zerstrt und muss neu prpariert werden.Angenommen es wird yl (mod N) 8 gemessen; dann verbleiben im ersten Register alle a,fr die 8a (mod 21) 8 gilt.

3.Schritt: Die Benutzung der diskreten FouriertransformationAuf das in Gleichung (6.30) erhaltene erste Register

q1a=0

g(a)|a

wird nun eine DFTq angewendet. Dies ergibt

DFTq

q1a=0

g(a)|a =q1c=0

f(c)|c.

Wenn die Periode r eine Zweierpotenz ist, erhlt man das exakte Ergebnis

DFTq

q1a=0

g(a)|a = 1r

r1=0

ei2pilr |q

r. (6.31)

6.3. Der Quantenalgorithmus von Shor 43

4.Schritt: Das Erhalten der PeriodeDer Zustand in dem zuletzt erhaltenen Register (6.31) wird gemessen; das Ergebnis wird cgenannt. Die Periodenbestimmung ist einfach, wenn die Periode eine Zweierpotenz ist, da danndie diskrete Fouriertransformation exakt ein Vielfaches von q

rergibt. In diesem Fall gilt c = q

r

fr alle . Meistens sind und r teilerfremd, so dass der maximal gekrzte Bruch cq(=

r) ein

Bruch ist, dessen Nenner q die Periode r ist.Angenommen die Messung des Zustands ergibt c = 768. Da q = 512 gilt (siehe 1.Schritt) ist

c

q=

768

512=

3

2=

r,

also die Periode r = 2 und somit eine Zweierpotenz.

5.Schritt: Das Finden der Faktoren von NWie schon in Kapitel (6.1)