Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 04/0512.1.

Finden von mehreren markierten Elementen Angenommen unter x0,...,xN-1 gibt es t mal

xi=1, finde alle solche Positionen Verwende Grover Algorithmus t mal

Zeit: s=1,...,t O((N/s)1/2)

· O(N1/2 s=1,...,t 1/s1/2)

· O(N1/2 s1...t 1/s1/2 ds)

· O(N1/2 t1/2)

Minima

Gegeben: Zahlen z0,...,zN-1, gesucht wird das Minimum

[Dürr/Hoyer]: kann in Zeit O(N1/2) gefunden werden

Algorithmus: ziehe zufälliges j aus 0...N-1 Wiederhole:

• Suche zi: zi < zj mit Grover-suche

• Abbruch wenn kein i gefunden, Ausgabe j• Setze j=i

Analyse

O.B.d.A. seien alle zi paarweise verschieden Rang r(i) sei Anzahl zj· zi

p(r,t) sei Wahrscheinlichkeit, dass Element von Rang r irgendwann gefunden wird, wenn bereits Element von Rang t gefunden p(r,t)=0 wenn t· r Ansonsten p(r,t)=1/r

• Induktion: t=r+1: einfach• t->t+1:• p(r,t+1)=1/t+k=r+1....t p(r,k)/t

=1/t + (t-r) (1/r) (1/t)=1/r

Analyse

Erwartete Laufzeit höchstens: r=1...N p(r,N) O((N/r)1/2)

· O(N1/2 r=1...N (1/r)/r1/2)· O(N1/2 (1+sr=1...N 1/r3/2 dr) )· O(N1/2)

Anzahl der Suchen insgesamt ·r=1...N p(r,N)

· O(log N) erwartet, Daher Speicherplatz O(log2N)

Amplituden Amplifikation

Problem: Gegeben Quantenalgorithmus, der mit Erfolgswahrscheinlichkeit a<1 funktioniert, wobei Erfolg verifizierbar ist[Ohne interne Messungen]Erreiche Erfolg mit konstante Ws.!

Klassische Wiederholungstechnik braucht (1/a) Iterationen um konstante Erfolgswahrscheinlichkeit zu erzielen

Verallgemeinerung von Grovers Technik erlaubt selbiges in O(1/a1/2) Wiederholungen

Amplituden Amplifikation

Gegeben Quantenalgorithmus, 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

|i=A|0i=|gi+|si ||g||2=a Operator S wechsele Vorzeichen von guten |xi, bilde

schlechte |xi auf sich selbst ab Operator P wie bei Grover (wechsele Vorzeichgen von |

0i) Q= - A PA-1 S [A anstatt Hadamard]

Amplituden Amplifikation

Q= - A PA-1 S Q|gi= (1-2a) |gi-2a|si

Q|si= (2-2a) |gi+(1-2a)|si

Z.B. hg| Qgi=hg| APA-1gi=h A-1g| PA-1gi

Sei A-1|gi= a|0i+ b |i

Dann PA-1|gi= |gi -2a|0i

Und obiges =h g | gi-2h 0|A-1gi=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 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

Element Distinctness

Problem: Gegeben n Zahlen von [1...10n] Sind die n Zahlen paarweise verschieden? Lösung zum Beispiel durch Sortieren

(Counting Sort), lineare Zeit Schneller Quantenalgorithmus? Lösung in Zeit O(n3/4 log n) Benutze Amplituden Amplifikation

Element Distinctness

Problem: Gegeben Menge T von n Zahlen aus [1...10n] Sind die n Zahlen paarweise verschieden?

Ziehe n1/2 Elemente zufällig, lese sie und sortiere sie in Zeit O(n1/2), Menge A

Wenn zwei gleiche Elemente gefunden, Ausgabe Benutze Grover Algorithmus, um festzustellen, ob es

in T-A ein Element gibt, das auch in A liegt, Zeit O(n1/2 log n), da A sortiert[Suche Element in T-A, Black Box im Grover wird durch Suche in A ersetzt]

Prozedur findet zwei gleiche Elemente mit Wahrscheinlichkeit 1/n1/2 wenn vorhanden

Amplituden Amplifikation! Laufzeit O(n1/2 log n¢ n1/4)

Element Distinctness

Wir haben Algorithmus mit O(n3/4 log n)Zeit gesehen (und SpeicherplatzO(n1/2 log n)

Tatsächlich können wir mit weniger Speicher, aber mehr Zeit auskommen

Element Distinctness

Algorithmus Ziehe S Elemente zufällig, lese sie und sortiere

sie in Zeit O(S), Menge A Wenn zwei gleiche Elemente gefunden, Ausgabe Benutze Grover Algorithmus, um festzustellen,

ob es in T-A ein Element gibt, das auch in A liegt, Zeit O(n1/2 log n), da A sortiert

Prozedur findet zwei gleiche Elemente mit Wahrscheinlichkeit S/n, wenn vorhanden

Amplituden Amplifikation! Laufzeit also O((n1/2log n +S) ¢ (n/S)1/2)=

O(n log n/S1/2) für beliebiges S < n1/2log n

Element Distinctness

[Shi02] Zeit (n2/3) notwendig [Ambainis03] O(n2/3) reicht !

[Szegedy04] Spezialfall einer Quantisierung von random walks