Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 04/0519.1.

Element Distinctness

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

Letzte Vorlesung: Zeit O(n3/4 log n)

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

[Szegedy04] Spezialfall einer Quantisierung von random walks

Random Walks

Gegeben sei ein ungerichteter Graph mit n Knoten

Beginne in Knoten i mit Wahrscheinlichkeit pi

Folge einer Kante an einem Knoten mit Grad di mit Wahrscheinlichkeit 1/di

Betrachte resultierende Verteilung auf Knoten, wenn genügend oft iteriert

Random Walks

Betrachte resultierende Verteilung auf Knoten, wenn genügend oft iteriert

Übergangsmatrix PP [i,j]=1/dj, wenn Kante j,i im Graphen

P ist stochastisch, i P[i,j] =1

Verteilung u1,...un auf 1...n entspricht Vektor u

Pku ist Verteilung nach k Schritten

Random Walks

“Gute” Graphen für random walks: Zusammenhang (jeder Punkt von jedem

erreichbar) nicht bipartit (keine Periode in Folge der

Wahrscheinlichkeiten) d.h. ergodische Markov Kette

Theorem: Dann gibt es eine stationäre Verteilung v, d.h. Pv=v

Diese Verteilung ist durch vi=di/(2m) gegeben für m=Anzahl Kanten: (Pv)i=(j,i)(dj/2m) ¢ (1/dj)= (j,i) 1/2m=di/2m

Random walk konvergiert von jedem Startpunkt aus zu der stationären Verteilung

Random Walks

Random walk konvergiert von jedem Startpunkt aus zu der stationären Verteilung

Sei G regulär (d.h. di=d) Dann ist Gleichverteilung stationär P ist symmetrisch Es gibt n reelle Eigenwerte 1 ¸ ...¸ n und n

orthogonale Eigenvektoren ei zu P Da P stochastisch, sind alle |i|· 1 Pv=v für stationäres v, d.h. 1=1, e1=v stationär Sei w eine beliebige Verteilung auf 1...n w=ii ei Pk w=ii Pkei=ii i

k ei Wenn |1-2| gross, dann schnelle Konvergenz zu e1

Random Walks

Hitting Time: M sei eine Menge markierter Knoten Hitting time ist die erwartete Zeit um

einen Knoten in M zu treffen PM sei P nach Streichung der Zeilen und

Spalten zu Knoten in M Eigenwerte von PM sind · 1 Erwartete Hitting time ist höchstens

1/(1-) für grössten EW von PM

Random Walks

Erwartete Hitting time ist höchstens1/(1-) für grössten EW von PM

Beispiel:vollständiger Graph, P(i,j)=1/(n-1),M={1}; PM(i,j)=1/(n-1) wenn ij,

PM: Matrix für vollst. Graphen mit n-1 Knoten mult. mit (n-2)/(n-1), EW=1-1/(n-1)Hitting time · O(n)Anders: Prob (spezieller Knoten nach T Schritten nicht getroffen) · (1-1/(n-1))T

Random Walks

Wenn |M|=, EW=1,2,... dann 1-¸ (1-2)/2d.h. Hitting time < 2/((1-2))

Beispiel:Element Distinctness Problem

Random walk Algorithmus: Wähle Aµ {1,...,n}; |A|=r Teste ob xi=xj für zwei Elemente von A Entferne ein zufälliges Element von A, nehme

zufälliges neues Element, Wiederhole Betrachte Graph: Knoten Mengen der Grösse r

Kanten: Wenn zwei Mengen genau in zwei Elementen unterschiedlich

Markierte Knoten: solche mit xi=xj

Random Walks

Betrachte Graph: Knoten Mengen der Grösse rKanten: Wenn zwei Mengen genau in zwei Elementen unterschiedlich

Markierte Knoten: solche mit xi=xj Anzahl Knoten ist Wenn es xi=xj gibt, dann ist Anzahl

markierter Knoten Damit:

Zweitgrösster EW vom Graphen ist 1-1/r Wenn |M|=N, EW=1,2,... dann 1-¸ (1-2)/2

d.h. Hitting time < 2/((1-2)) Hitting Time also 2(n2/r2)¢ r=n2/r Laufzeit: O(r+n2/r), bestenfalls O(n)

Random Walks

Hitting Time also 2(n2/r2)¢ r=n2/r Laufzeit: O(r+n2/r), bestenfalls O(n) Behauptung: Quantum walk hat

quadratisch kürzere Hitting time Dann Laufzeit O(r+n/r1/2), optimal für

r=n2/3

Vergleiche mit Walk auf vollständigem Graphen, Hitting time n1/2 entsprechend Grover Algorithmus

Random Walks

Klassischer Walk Algorithmus für Element Disctinctness, r=n2/3

Argument für Hitting time O(n4/3) Fange bei zufälligem Knoten an Prob(Kollision gefunden) ¼ (n2/3/n)2=n-2/3

Walk für n2/3 Schritte führt zu “fast wieder zufälligem Knoten”:

• Sei Menge A von n2/3 Indizes gegeben als Start• Wähle Index aus A, entferne und ersetze durch

Index aus T-A, k Iterationen• Jeder Index: Noch in A mit Prob (n2/3-1)/n2/3)k,

konstant wenn k=n2/3,• Also erwartet Hälfte der Indizes neu, Ws dass

diese die Kollision enthalten (n-2/3 )• Also Hitting time O(n4/3)

Quantum Walks

Mehrere verschiedene Definitionen Superposition über Knoten Z.B. Walk mit Münzwurf:

Erzeugen einer Superposition entsprechend Münzwurf in Extraregister, entsprechend der nächsten Kante folgen, Münzwurfregister löschen(funktioniert nur bei regulären Graphen)

Quantum Walks

Hier: Betrachten Walks auf bipartiten Graphen (verdoppele Knotenmenge, Übergänge auf Kopie der Nachbarn in der jeweils anderen Menge)

P: Matriz des ursprünglichen walks Basis: Zustände |ii|ji i sei Knoten auf linker Seite, j auf rechter Seite Zustände |ii=j (P[j,i])1/2|ii|ji

|ji=i (P[i,j])1/2|ii|ji

Möchten: Operator: |ii|ri wird für alle |ri auf |ii abgebildet, analog für j, aber unmöglich!

Quantum Walks

Basis: Zustände |ii|ji Gegeben Walk mit Matrix P i sei Knoten auf linker Seite, j auf rechter Seite Zustände |ii=j (P[j,i])1/2|ii|ji |ji=i (P[i,j])1/2|ii|ji Sei A die Matrix (|ii)i=1...n

(d.h. n Spalten / n2 Zeilen) B ebenso für |ji AA*: Projektion auf Unterraum EA von |ii

aufgespannt BB* für |ji 2AA*-I Reflektion um Unterraum Walk Operator: W=(2BB*-I)(2AA*-I)

Quantum Walks

2AA*-I Reflektion um Unterraum Walk Operator: W=(2BB*-I)(2AA*-I) (2AA*-I) lässt EA unverändert P symmetrisch, dann |i = i,j(P[i,j])1/2/N1/2 |i,ji

stationär Intuition: amplifiziere Zustände, die dem walk

entsprechen Frage 1: Ist W unitär? Frage 2: Was ist Hitting time im Quantum walk?

1): AA* ist Projektion auf EA, symmetrisch (2AA*-I) (2AA*-I)*=I

Quantum Walks

2AA*-I Reflektion um Unterraum Walk Operator: W=(2BB*-I)(2AA*-I) Frage 2: Was ist Hitting time im Quantum

walk? Sei M markierte Menge im ursprünglichen

Graphen Verändere den ursprünglichen random

walk: Wenn markierter Knoten erreicht, niemals verlassen

Quantum Walks

Verändere den ursprünglichen random walk: Wenn markierter Knoten erreicht, niemals verlassen

Neue Matrix:

Lasse quantum walk für den modifizierten random walk auf |i laufen

Wenn M leer, dann wird immer | i erreicht Plan: Wenn M nicht leer, und wenn genügend viele

Iterationen, dann wird ein Zustand erreicht, der konstanten Abstand von |i hat, Messung ergibt Entscheidung

Es wird i.A. nur Entscheidung erzielt (vergl. Element Distinctness)

Quantum Hitting time: Anzahl Schritte, bis h |Wt|i < 3/4

Quantum Walks

Quantum Hitting time: Anzahl Schritte, bis h|Wt | i < 3/4

Theorem: Hitting time ist O( 1 / (1-||PM||)1/2)

Damit: Element Distinctness kann in Zeit O(n2/3log n) entschieden werden.

Beispiel

Random Walk auf vollständigem Graph,ein markierter Knoten (1), dieser stoppt walk

Verändere in bipartiten Graphen | i=i,j(P[i,j])1/2/N1/2 |i,ji

=i,j 1/N |i,ji

|1i=|1i|1i; |1i =|1i|1i

|ii=j (1/N])1/2|ii|ji

|ji=i (1/N)1/2|ii|ji

Beispiel

Beispiel

Effekt von W Wie wird gesuchtes Element (1)

“amplifiziert”? |1i|1i stationär Amplitude in Zuständen |1i|ji wird durch

2AA*-I mit -1 multipliziert, dann Grover Iteration vollständig nach 2BB*-I

Amplitude in Zuständen |ji|1i wird durch 2BB*-I mit -1 multipliziert etc.

Zustände |ii |ji:Grover Schritt auf beiden Registern

Quantum Walks

Quantum Hitting time: Anzahl Schritte, bis h|Wt | i < 3/4

Theorem: Hitting time ist O( 1 / (1-||PM||)1/2)

Quantum hitting time

r=n-|M| nichtmarkierte Knoten |v1i,...,|vri sei Orthonormalbasis aus

Eigenvektoren von PM mit Eigenwerten 1,...,r

Sei |vxi=i i,x |ii, wobei i,x=0 wenn i in M |eA,xi=ii,x |ii=i,j i,x (P[j,i])1/2 |i,ji 2 EA

|eB,xi=ii,x |ii=i,j i,x (P[i,j])1/2 |i,ji 2 EB

Eigenschaften: h eA,x | eB,xi=x

(2BB*-I) |eA,xi =x |eB,xi

Quantum hitting time

Vx sei von |eA,xi, |eB,xi aufgespannt

Vx ist invariant unter 2BB*-I und 2AA*-I:2AA*-I reflektiert in Vx über |eB,xi

Ergebnis von W in Vx : Rotation um Winkel zwischen |eA,xi, |eB,xi

W rotiert in Vx um 2x, wobei x=cos-1 (x)

Quantum hitting time

Sei |uxi die Projektion von | i auf Vx

Man kann zeigen, dass x ||ux||2=r/n, ObdA ¸ 1/2

Wenn ungefähr l ¼ 1/x Schritte gemacht sindist h ux | Wl |uxi=1-(1)

Wenn ungefähr 1/=max 1/x Schritte, dannh |Wl| i · 1-(1)¢ x ||ux||2 · 1-(1)

Zufällige Wahl von l aus 1,...,1/ Auch h |Wl| i2 · 1-(1) ¸ sin¸ (1-cos)1/2=(1-||PM||)1/2 ergibt sich Ergebnis