Upload
adaleiz-gilgenbach
View
108
Download
2
Embed Size (px)
Citation preview
Quantum Computing
Hartmut KlauckUniversität FrankfurtWS 04/055.1.
Frage:
Können wir NP-vollständige Probleme in polynomieller Zeit lösen?? [Auf einem Quantenrechner]
Spezifischer: Reicht die “Parallelität” des Modells um exponentielle Beschleunigung zu erreichen?
Z.Bsp. SAT Problem: gegeben KNF Formel auf n Variablen, ist die Formel erfüllbar?
Ansatz: Teste alle 2n Belegungen der Variablen Wie schnell kann dies ein Quantenalgorithmus ?
Black Box Modell
Kann das SAT Problem im Black Box Modell schnell gelöst werden?
D.h. Gegeben Black Box, die bei gegebener Belegung der Variablen anzeigt, ob Formel erfüllt ist, keine weitere Information über Formel
n Boolesche Variablen, N=2n Belegungen Suchproblem: Bits x0,...,xN-1 gegeben,
finde xi=1 wenn vorhanden
Suchprobleme
Erstes Problem: Gegeben x0,...,xN-1, finde i mit xi=1 wenn vorhanden
Zweites Problem: Gegeben x0,...,xN-1 mit Garantie, dass genau ein xi=1, finde i
Drittes Problem: Gegeben x0,...,xN-1, Berechne ODER(x0,...,xN-1)
Viertes Problem: Gegeben x0,...,xN-1 mit Garantie, dass genau ein xi=1 oder kein xi=1, Entscheide welcher Fall
2),3) einfacher als 1), 4) einfacher als 2),3)
Klassische Algorithmen
Betrachte randomisierte Algorithmen mit Fehler 1/3 für Problem 4)
Wir zeigen: (N) Fragen an die Black Box notwendig
Klassische Algorithmen
Gegeben: randomisierter Fragealgorithmus Wenn es randomisierten Algo mit T Fragen
(worst case) und Erfolgswahrscheinlichkeit p gibt, dann gibt es einen deterministischen Algo mit T Fragen und Erfolg p für zufällige s
Randomisierter Algorithmus ist Schaltkreis mit zusätzlicher Eingabe r2{0,1}m
Ex Er [Erfolg bei Zusatzeingabe r]=p ) es gibt ein r, so dass Ex [Erfolg auf bei Zusatzeingabe r]¸ p
Fixiere r ) deterministischer Algorithmus
Klassische Algorithmen
Verteilung auf den Eingaben: mit Wahrscheinlichkeit 1/2 Eingabe 0N, Eingaben 000010000 mit Wahrscheinlichkeit 1/(2N) jeweils
Betrachte deterministischen Algorithmus mit Fehler 1/3 und <N/3 Fragen Darf 00000 nicht falsch klassifizieren Wenn <N/3 xi bekannt sind gibt es noch >2/3¢ N
Positionen, die 1 sein können, Algorithmus muss also >2N/3 Eingaben falsch verwerfen, Fehler also >1/3
Also muss jeder Algorithmus mindestens N/3 Fragen stellen
Quantenalgorithmen
Wie schnell kann ein Quantenalgorithmus das Suchproblem lösen?
Wir wissen schon: Grovers Algorithmus kann dies in O(N1/2)
Historisch kam untere Schranke zuerst Jeder Algorithmus für das Suchproblem
(Genauer für Problem 4) ) braucht (N1/2) Fragen
D.h. “brute Force” Algorithmen für SAT brauchen Zeit 2n/2
Die Untere Schranke
Betrache beliebigen Quanten Fragealgorithmus A Lasse A auf 0N laufen, mit T Fragen
Folge von Quantenfragen Zustände 0...N-1 ai,t |ii |ui,ti |vi,ti
i: Adresse, u Register für Ausgabe der Black Box , v für restlichen Speicher, t=1..T Zeit
Definiere “Fragegrösse” M(i) = t=1...T|ai,t|2
Intuitiv “Wahrscheinlichkeit, dass i gefragt wird” Erwartungswert Ei M(i)· T/N Fixiere i mit M(i)· T/N A hat wenig Information über xi, kann nicht gut
vorhersagen ob xi=1 oder =0
Die Untere Schranke
“Fragegrösse” M(i) = t=1...T|ai,t|2
Fixiere i mit M(i) · T/N Mit Cauchy Schwartz gilt t=1...T|ai,t| · t=1...T1¢ |ai,t|· T1/2 (t=1...T|ai,t|2)1/2· T/N1/2
y(i) sei String mit y(i)i=1 und 0 sonst Betrachte A in folgenden Situationen:
In Frage 1 bis t enthält Black Box 0N
Ab Frage t+1 enthält Black Box y(i) Endzustand sei |(t)i |(0)i Endzustand A auf y(i);
|(T)i Endzustand A auf 0N
Die Untere Schranke
Betrachte Abstand zwischen den Zuständen |(t)i und |(t-1)i
Klar: Bis Schritt t-1 selber Zustand im Algorithmus In Schritt t wird Abstand 21/2|ai,t| eingeführt Ab Schritt t+1 werden dieselben unitären
Transformationen ausgeführt, d.h. Abstand nicht verändert
Setze |E(t)i= |(t)i-|(t-1)i Dann kE(t) k· 21/2|ai,t|
Die Untere Schranke
|(0)i Endzustand A auf y(i); |(T)i Endzustand A auf 0N
k |(T)i - |(0)i k
= k |(T)i - |(T-1)i +|(T-1)i - |(0)i k
· k |(T)i - |(T-1)i k + k |(T-1)i - |(0)i k
· t=1...T k |(t)i - |(t-1)i k
= t=1...T k |E(t)i k
· t=1...T 21/2 |ai,t|· 21/2 T/N 1/2
Wenn T<N1/2/10, dann ist der Abstand kleine Konstante, d.h. Fehler zu gross, denn auf 0N und y(i) mit hoher Wahrscheinlichkeit gleiche Ausgabe
Grovers Algorithmus
[Grover 96]
Löst das Suchproblem mit N1/2 Fragen im worst case
Allgemeiner: Wenn t Positionen i mit xi=1 existieren, dann Zeit (N/t)1/2
Grovers Algorithmus
Betrache Fall mit genau einer Lösung xi=1 (Problem 2)
Betrache Vektoren |ii sowie |0i=j=0...N-1 1/N1/2 |ji
”Ziel” und “Start” Wie kann man den Abstand verringern? Betrachte Ebene von |ii und |0i; |ei sei
orthogonal zu |ii in der Ebene
Grovers Algorithmus
Betrachte Ebene von |ii und |i; |ei sei orthogonal zu |ii in der Ebene
Reflektiere um |ei und dann um |0i Ergebnis:
|ii
|ei
|i
Grovers Algorithmus
Betrachte Ebene von |ii und |i; |ei sei orthogonal zu |ii in der Ebene
Reflektiere um |ei und dann um |0i Ergebnis:
|ii
|ei
|i
Grovers Algorithmus
Betrachte Ebene von |ii und |i; |ei sei orthogonal zu |ii in der Ebene
Reflektiere um |ei und dann um |0i Ergebnis: Rotation um 2
|ii
|ei
|i
Grovers Algorithmus
Betrachte Ebene von |ii und |i; |ei sei orthogonal zu |ii in der Ebene
Reflektiere um |ei und dann um |i Ergebnis: Rotation um 2 Wenn Winkel zu |0i, dann erst -- zu |
ei und dann 2 + zu |0i|ii
|ei
|i
Grovers Algorithmus
Reflektiere um |ei und dann um |i Ergebnis: Rotation um 2 |ei=i j 1/(N-1)1/2 |ji
Wie viele Iterationen? Höchstens (/2)/(2) Iterationen 1/N1/2 =hi|0i = cos(/2- ) = sin() Dann 1/N1/2 = sin() ¼
und ca. /4 ¢ N1/2 Iterationen
Grovers Algorithmus
Reflektiere um |ei und dann um |i Ergebnis: Rotation um 2 |ei=i j 1/(N-1)1/2 |ji Aber wie? Reflektion um |ei:
bilde a|ii+b|ei ab auf -a |ii+ b|ei Durch Frage an Black Box! Wechsele Vorzeichen wenn xi=1
|ei|i
|ii
Grovers Algorithmus
Reflektiere um |ei und dann um |i
Reflektion um |0i:
Wende Operation 2|0ih 0|- I an Sei N=2n, Positionen 0,...,N-1 in
Binärdarstellung Implementierung durch H n P H n, wobei
P|0ni=|0ni und P|xi=-|xi sonst
|ei|i
|ii
Grovers Algorithmus
Operation 2|0ih 0|- I Implementierung durch H n P H n, wobei P|
0ni=|0ni und P|xi=-|xi sonst
Grovers Algorithmus
Operation 2|0ih 0|- I Implementierung durch H n P H n, wobei P|
0ni=|0ni und P|xi=-|xi sonst
Grovers Algorithmus
Operation 2|0ih 0|- I Andere Interpretation:
Vektor (a0,...,aN-1) wird abgebildet auf Vektor mit (2j aj/N)-ai an Position i
Inversion über den Mittelwert
Grovers Algorithmus
Black Box: Zusätzliches Qubit 1/21/2 (|0i-|1i) Anwendung der normalen Black Box: |
ii|ai wird auf |ii|a©xii abgebildet Trick mit zusätzlichem Qubit: Black Box
bildet |ii auf (-1)xi |ii ab
Grovers Algorithmus
Register mit n Qubits Starte mit Zustand |0i=j=0...N-1 1/N1/2 |ji
[durch Anwendung von H n auf |0ni] Iteriere ungefähr N1/2 mal:
Wende Black Box an Wende H n P H n an, wobei P|0ni=|0ni und
P|xi=-|xi sonst Messe i, teste ob xi=1
Grovers Algorithmus
HH
HH
HH
O
HH
HH
HH
HH
HH
HH
P
N1/2
Beispiel
x0=1, andere xi=0
Anfang: j=0...N-1 1/N1/2 |ji
Dann j=1...N-1 1/N1/2 |ji-1/N1/2|0i Dann Inversion über den Mittelwert
Vektor (a0,...,aN-1) wird abgebildet auf Vektor mit (2j aj/N)-ai an Position i
Ergebnis: Amplitude von |0i steigt ungefähr um 2/N1/2, andere Amplituden bleiben fast gleich
Ähnlich in anderen Schritten Fertig nach (/2)/(2/N1/2)=(/4) N1/2 Schritten
Genaue Anzahl der Iterationen Macht man zuviele Iterationen, wird der Zustand wieder
von der Lösung entfernt !
Anfangszustand: j=0...N-1 1/N1/2 |ji
1/N1/2 |i0i +ji0 1/N1/2 |ji
k0,l0=1/N1/2
Iteration setzt kj+1= (N-2)/N ¢ kj+2(N-1)/N¢ lj lj+1= (N-2)/N ¢ lj -2/N¢ kj
Man kann zeigen, dass kj=sin((2j+1)); lj=1/(N-1)1/2 cos((2j+1)) wobei so dass sin2()=1/N
km=1 wenn (2m+1)=/2, wenn m=(-2)/(4) Fehler kleiner als 1/N wenn b /4 N1/2c Iterationen
Mehr als eine Lösung
Es gebe t Werte von i mit xi=1 t sei bekannt Verwende selben Algorithmus, andere
Anzahl von Iterationen Ähnliche Analyse wie zuvor, Fehler t/N bei
b/4 ¢ (N/t)1/2c Iterationen
Unbekannte Anzahl von Lösungen Es gebe t Werte von i mit xi=1 t sei unbekannt Verwende immer kleinere Schätzungen von
t und lasse vorigen Algorithmus laufen s=N/2,N/4,N/8,...,t/2,... Laufzeiten O((N/s)1/2) jeweils Gesamtlaufzeit s=N/2,N/4,...,t/2 (N/s)1/2 =
O((N/t)1/2)Betrachte (N/t)-1/2 ¢ a=1,...,log N-log t+1 2a/2=O(1) geometrische Reihe
Exaktes Suchen
Wenn Anzahl der Lösungen bekannt ist, kann im Prinzip mit der richtigen Anzahl Iterationen Erfolgswahrscheinlichkeit 1 erzielt werden
Problem: Anzahl ist integer Lösung: Abwandlung der Iteration im letzten
Schritt, die um genau den richtigen Winkel dreht D.h. Suchproblem bei gegebener Anzahl t von
Lösungen in Zeit O((N/t)1/2 ) exakt lösbar Gilt nicht z. Beispiel für das Entscheiden des
ODERs von N Bits: hier Fehler unumgänglich
Amplituden Amplifikation
Problem: Gegeben Quantenalgorithmus, der mit Erfolgswahrscheinlichkeit a<1 funktioniert, wobei Erfolg verifizierbar ist[Ohne interne Messungen]
Klassische Wiederholungstechnik braucht (1/a) Iterationen um konstante Erfolgswahrscheinlichkeit zu erzielen
Grovers Technik erlaubt selbiges in O(1/a1/2) Wiederholungen
Selber Ansatz wie zuvor, ersetze Black Box durch Laufen des gegebenen Algorithmus’ plus Verifikation