Date post: | 05-Apr-2015 |
Category: |
Documents |
Upload: | wilma-giesel |
View: | 109 times |
Download: | 2 times |
Quantum Computing
Hartmut KlauckUniversität FrankfurtWS 05/0615.12.
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 Eingaben x
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
Amplituden Amplifikation
Problem: Gegeben Quantenalgorithmus A, 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
Amplituden Amplifikation
Problem: Gegeben Quantenalgorithmus A, der mit Erfolgswahrscheinlichkeit |a|<1 funktioniert, wobei Erfolg verifizierbar ist[Ohne interne Messungen]
Seien Ausgaben x2 {0, 1}n gut oder schlecht. A berechne ein gutes x mit Wahrscheinlichkeit |a|
Guter Unterraum aufgespannt von guten |xi, schlechter von schlechten |xi
|i=A|0i=|gi+|si Dabei sei |gi die Projektion auf guten Raum usw.
Dabei sei ||g||2=a Operator S wechsele Vorzeichen von guten |xi, bilde
schlechte |xi auf sich selbst ab Operator P wie bei Grover (wechsele Vorzeichen von |
0i) Q= - A PA-1 S [A anstatt Hadamard]
Amplituden Amplifikation
Q= - A PA-1 S Behauptung:
Q|gi= (1-2a) |gi-2a|si
Q|si= (2-2a) |gi+(1-2a)|si
Z.B. betrachte p=hg| Qgi = hg| APA-1gi
Setze A-1|gi= a |0i+ |i, wobei |i ? |0i, beachte
h A-1 g |0i=a
Dann APA-1|gi= |gi -2a A|0i
Und somit p =h g | gi-2ah g|A|0i=a-2a2
Also wird der 2-dimensionale Raum von |gi und |si nicht verlassen
Amplituden Amplifikation
Q= - A PA-1 S Q ist auch
Reflektion um |si durch I-2/(1-a) |sihs|
gefolgt von Reflektion um |i durch I-2|ih|
Starte mit A|0i=|i Wende Q ungefähr 1/a1/2 mal an:
a=hg|i=cos(/2-)||g||=cos(/2-)a1/2
Also a1/2=sin() ¼ Winkelfortschritt 2(es sei der Winkel zwischen
|i und |si) Anzahl der Iterationen /(4a1/2)
Amplituden Amplifikation
Q= - A PA-1 S Anzahl der Iterationen /(4a1/2) Beispiel: Grover
A=H n erzeugt uniforme Superposition, bei t Lösungen ist Wahrscheinlichkeit von Treffer a=t/N nach Messung
Damit ist klar, dass statt H n jede Transformation ausreicht, die |0i auf eine fast uniforme Superposition abbildet