Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/067.11.

Unterscheidbarkeit von Zuständen Gegeben: Menge von Zuständen

S={ |1 i ,…, |ki } (bekannt) Input: Ein Zustand aus S Ausgabe: Index i des Zustandes Identifikationsproblem

Zustände in S paarweise orthogonal:Problem perfekt lösbar: konstruiere Observable mit Unterräumen Si=span(|ii), Projektoren |iihi|

Unterscheidbarkeit nichtorthogonaler Zustände

Sei S={ |i , |i } mit h | i 0 Gibt es eine Messung, die das

Identifikationsproblem löst? |i = |i + |i mit = h|i Messung ist Projektion, d.h. linear, d.h.

”-Anteil” von |i benimmt sich wie |i Mit Wahrscheinlichkeit |h|i|2 wird auf

Eingabe |i die Ausgabe erzeugt(wenn auf |i immer ausgegeben wird)

Also wird das Problem nicht ohne Fehler gelöst

Was ist „nichtklassisch“ an der Quantentheorie ? Phänomene der klassischen Physik können im

Prinzip vollständig berechnet werden Beispiel: Wurf eines Würfels, Beschreibung als

Wahrscheinlichkeitsverteilung ist „unvollständig“ Quantenmechanik liefert nur probabilistische

Beschreibungen

Gott würfelt nicht

Was ist „nichtklassisch“ an der Quantentheorie ? [Einstein Podolsky Rosen 35] behaupteten, die

Quantenmechanik sei unvollständig In dem Sinn, dass eine tieferliegende klassische

Theorie probabilistische Vorhersagen eliminieren kann, indem sie bisher unbekannte physikalische Parameter ins Spiel bringt

Der Zustand, 1/21/2 (|00i+|11i), wenn auf zwei räumlich getrennten Qubits gemessen weist „spukhafte Fernwirkungen“ auf (verhält sich wie zwei perfekt korrelierte Würfel, die zu weit entfernt sind, um zu „kommunizieren“)

Quantentheorie vs. Lokal Realistische Theorien Physikalische Theorie ist

lokal, wenn räumlich getrennte Systeme sich nicht direkt beeinflussen

realistisch, wenn direkt vor einer Messung eine zu messende Eigenschaft im Prinzip mit Sicherheit vorhersehbar ist,d.h. „objektiv“ vorhanden ist

Bellsche Ungleichung

Zwei Partikel werden von Charlie an Alice und Bob weitergereicht (in irgendeinem Zustand)

Alice und Bob sind räumlich getrennt Partikel für Alice hat Eigenschaften EQ und ER

mit Werten Q und R Partikel für Alice hat Eigenschaften ES und ET

mit Werten S und T Werte der Eigenschaften sind „objektiv“, d.h.

werden durch Messung nur festgestellt Q,R,S,T 2 {-1,1}

Bellsche Ungleichung

Betrachte QS+RS+RT-QT = Q( S-T ) + R( S+T ) S-T=0 oder S+T=0, also QS+RS+RT-QT = § 2 Erwartung E[QS+RS+RT-QT] · 2 Zufallsexperiment hier: Charlies Präparierung der

Partikel, kein Zufall bei fester Präparierung Es gibt also Wahrscheinlichkeiten P(q,r,s,t), dass

das System die Eigenschaften Q=q, R=r, S=s, T=t direkt vor der Messung hat

Erwartung E[QS+RS+RT-QT] · 2 Linearität des Erwartungswertes:

E[QS]+E[RS]+E[RT]-E[QT] · 2

Bellsche Ungleichung

Voraussetzungen: Es gibt die Wahrscheinlichkeiten P(q,r,s,t) [Realismus], und die Messungen verlaufen kausal unabhängig [Lokalität]

Messung von EPR Paaren

Zustand der zwei Partikel von Alice und Bob: 1/21/2 (|01i-|10i)

Es gibt eine Menge von vier Observablen, so dass E[QS]+E[RS]+E[RT]-E[QT] ¸ 2¢ 21/2

von QM vorhergesagt

Experimenteller Test entscheidet zu Gunsten von QM [Aspect 82]

Versteckte Parameter

Ein klassisches Modell mit versteckten Parametern funktioniert so:

(implizit) Alice und Bob erhalten je ein präparieres Teilchen

(tatsächlich) Alice und Bob haben eine gemeinsame klassische Information (diese legt für alle möglichen Experimente auf je einem Teilchen den Wert aller Messergebnisse fest, also z.B. Experiment E auf Teilchen A ergibt Ergebnis 1 usw.). Bemerkung: in einer realistischen Theorie

existiert eine solche Liste Rest des Protokolls verläuft räumlich getrennt,

gleichzeitig, d.h. kausal unabhängig

Versteckte Parameter

Aufgabe: Alice und Bob dürfen sich absprechen, danach ist

keine Kommunikation zwischen beiden erlaubt Alice und Bob erhalten dann je ein Zufallsbit x bzw. y Sie produzieren je eine Ausgabe: a,b Das Protokoll hat Erfolg, wenn xÆy = a©b

x,y geben eine zu messende Eigenschaft vor Wie gut kann ein Protokoll sein? Optimale Strategie: Beide geben immer 0 aus Erfolgswahrscheinlichkeit: 3/4

Wenn eine Theorie mit versteckten Parametern QM erklärt, sollten beide dasselbe vorhersagen, d.h. jedes Quantenexperiment sollte Erfolg · ¾ haben

Ein Quantenprotokoll

Alice und Bob haben den Zustand 1/21/2 (|01i-|10i)

x=0, Alice misst (in der Standardbasis), Ausgabe des Ergebnisses

x=1, Alice rotiert mit

,misst, Ausgabe des Ergebnisses y=0, Bob misst, Ausgabe Komplement d. Ergebnisses y=1, Bob rotiert mit

,misst, Ausgabe Komplement d. Ergebnisses

Rotationsgatter

Qubit |0i wird zu cos(/8) |0i - i sin(/8) |1i

Wahrscheinlichkeit von Messergebnis0 ist dann cos2(/8)

Analyse

Fall 1: x=0, y=0; Messung Standardbasis, Ausgabe immer a,b mit a=b, also a©b=0,also immer korrekt

Fall 2: x=0, y=1; A) Alice misst a=0 (mit Ws. ½)Zustand ist |01iBob hat |1i, daher b=0 mit Ws. cos2(/8), Fehler also 1-cos2(/8)= sin2(/8)

B) Alice misst a=1, analog Fall 3: x=1, y=0; analog, Fehler sin2(/8)

Analyse

Fall 4: x=y=1, gewünschte Ausgabe 1Alice und Bob rotieren vor der Messung

Alice rotiert -/8, Bob rotiert +/8 Leicht nachzurechnen, dass Messungen

nun unabhängig, Fehler also ½

Fehler gesamt:¼ (0 + 2¢sin2(/8) + 1/2) ¼ 0.2

Also ist der Fehler geringer als in jeder klassischen Theorie

Zurück zum anderen Konzept R: Ergebnis Messung Standard Basis (§ 1) Q: Ergebnis Messung nach Rotation (§ 1)

S: Ergebnis Messung Standard Basis (§ 1) T: Ergebnis Messung nach Rotation (§ 1)

E[RS]=1, E[QS]=E[RT]=cos2(/8)E[QT]=1/2

Also E[RS]+E[QS]+E[RT]-E[QT]=1 + 2 cos2(/8) - 1/2 ¼ 2.2 > 2

Ziele im Quantum Computing (Bauen eines Quantenrechners) Entwurf schneller Algorithmen Quantenkommunikation resp.

Kommunikation mit Hilfe von EPR-Paaren Quantenkryptographie Fehlertolerante Schaltkreise

Was wir wissen

Quanteneffekte sind grundsätzlich verschieden von klassischer Physik

In Spielzeugproblemen (Deutsch Josza) schlagen Quantenrechner klassische Rechner

Geht das auch für wichtige Probleme? Kann man interessante Probleme effizient lösen? Kann man NP-vollständige Probleme effizient

lösen (auf QC)? Kann man nicht berechenbare Funktionen

berechnen??

Berechnung durch Schaltkreise Klassische Schaltkreise: Eingaben x1,…,xn2{0,1}n

Gatter g1,…,gm Gatter: nimmt Eingaben oder vorherige Gatter,

berechnet Funktion {0,1}2{0,1} Ausgabe an gm Grösse: m (entspricht Rechenzeit) Basen (erlaubte Gatterfunktionen):

AND, OR, NOT NAND Alle 2-stelligen Booleschen Funktionen

Notwendige Grösse ändert sich mit Wahl der Basis nur um konstanten Faktor

Probabilistische Schaltkreise Zusätzliche Eingaben e1,…,er

Für jede echte Eingabe x1,…,xn gilt: wenn e1,…,er uniform zufällige Bits sind,dann wird das richtige Ergebnis mit Wahrscheinlichkeit 2/3 berechnet

Schaltkreisfamilien

Schaltkreis Cn funktioniert für Eingaben mit n Bits

Familie (Cn)n2 N

Kann unter dieser Definition nicht (durch Turingmaschinen) berechenbare Funktionen berechnen

Uniformitätskondition: Cn kann bei unärer Eingabe von n in polynomieller Zeit durch eine Turingmaschine berechnet werden

Komplexitätsklassen

P : Klasse der Sprachen, die von uniformen Schaltkreisfamilien polynomieller Grösse berechenbar sind

BPP : dto. mit probabilistischen Schaltkreisen

Definitionen sind äquivalent zu Definitionen mit Turingmaschinen

Fakten über Schaltkreise

Es ist bekannt, dass die meisten Funktionen {0,1}n{0,1} Schaltkreise der Grösse mindestens (2n/n) benötigen

Schranke ist dicht, d.h. jede Funktion f:{0,1}n{0,1} kann durch einen (nichtuniformen !) Schaltkreis der Grösse

(2n/n) berechnet werden Für keine konkrete Funktion ist eine

superlineare untere Schranke bekannt

Exponentielle untere Schranke für die meisten Funktionen Anzahl der Funktionen {0,1}n {0,1}:

exp2(exp2(n)) Zeigen, dass es viel weniger Schaltkreise

gibt, die kleiner als exp2(n)/n sind Da jeder Schaltkreis nur eine Funktion

berechnet, gibt es für die meisten Funktionen nur grosse Schaltkreise

Zählen aller Schaltkreise

m Gatter Für jedes Gatter können zwei Vorgänger

und eine Funktion gewählt werden Also höchstens (16 (m+n)2)m Schaltkreise Damit (16 (m+n)2)m ¸ exp2(exp2(n))/100 (8m)2m ¸ exp2(exp2(n))/100 2m log m +O(m) ¸ 2n-O(1) m=(2n/n)

Ähnliches gilt für probabilistische Schaltkreise

Quantenschaltkreise

n Qubits initialisiert mit der Eingabe s Arbeitsqubits Unitäre Operationen auf zwei Qubits

U1,…,Um; zusammen mit Wahl der zwei Qubits

Operation Ui wird als Tensorprodukt mit der Identität auf den n+s-2 restlichen Qubits angewendet

Zu messendes Ausgabequbit sei fix

Quantenschaltkreise

Uniforme Familien wie gehabt [hier gibt es noch momentan ein Problem mit der Beschreibung „beliebiger“ unitärer Transformationen, siehe einige Folien weiter]

Klasse BQP: durch uniforme Familien von Quantenschaltkreisen polynomieller Grösse berechenbare Funktionen, bei Fehlerwahrscheinlichkeit < 1/3

EQP: kein Fehler erlaubt Selbe Klassen durch (Quanten) Turingmaschinen

definierbar (siehe Gruskas Buch)