Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/065.1.

Element Distinctness

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

Wir wissen: 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)