Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/0612.1./23.1.

Untere Schranken im Black Box Modell

Das Black Box Modell

Eine Eingabe x1,…,xn ist als Orakel gegeben

Es kann nach Eingabe xi gefragt werden

Ein Algorithmus berechnet eine Funktion f(x1,…,xn)

Bsp: Deutsch Problem: x1,x2 sind Werte einer Funktion auf 0 und 1Frage ab Funktion balanciert oder nicht) Berechnen Parität von x1,x2

Beispiel Grover: Finde i mit xi=1

Beispiel OR: Entscheide, ob es xi=1 gibt

Das Black Box Modell

Kosten eines Algorithmus sind durch die maximale Anzahl Fragen auf einer Eingabe gegeben

Komplexität einer Funktion sind die minimalen Kosten eines Algorithmus, der die Funktion berechnet

Typen von Algorithmen

Deterministische Algorithmen: immer korrekt, keine Randomisierung, Komplexitätsmass D(f)

Randomisierte Algorithmen: haben Fehlerwahrscheinlichkeit 1/3 über verwendete Zufallsbits, R(f)

Quantenalgorithmen: Verwenden Quantenfragen etc. Mit Fehler 1/3: Q(f) Ohne Fehler: QE(f)

Beispiele

Wir haben bereits gesehen: QE(XOR2)=1, aber R(XOR2)=2

QE(XORn)· n/2 Q(OR)=O(n1/2) R(OR)=(n) Q(OR)=(n 1/2) Q(Element Distinctness)=O(n2/3)

Weitere untere Schranken für Quantenalgorithmen?

Wieviel schneller können Quantenalgorithmen sein im Vergleich zu randomisierten Algorithmen?

Beispiele

Unsere untere Schranke für OR wurde mit einem Adversary Argument gezeigt

Andere Techniken?

Exponentielle Speedups haben wir für bestimmte Suchproblem gesehen (Finden von Perioden)

Für Boolesche Funktionen?

Die Mutter aller Funktionen Betrachte ID mit ID(x)=x Wie viele Fragen braucht ID?

R(ID)=n Denn, wenn eine Position nicht gefragt,

kann sie nicht ausgegeben werden Formal: wende Yao Prinzip an: Fixiere

Zufallsstring, deterministischer Algorithmus mit n-1 Fragen muss Fehler ½ haben

Q(ID)· n/2+O(n1/2)

Ansatz: Verwende Orakeltransformtion wie bei

D-J oder Grover (-1)xi |ii Formel für Hadamard Transformation:

Erneute Hadamard Transformation bildet zurück ab auf |xi

Es reicht also die obige Superposition zu erzeugen

Dies braucht allgemein n Fragen Anzahl Fragen abhängig von |y|, Hamming

Gewicht Verwende nur die y, die kleines |y| haben, das

sind fast alle y wenn |y|· n/2+O(n1/2)

Der Algorithmus

Erzeuge eine uniforme Superposition über alle y mit |y|· n/2+O(n1/2)

Verwende Transformation, die für Zustand |yi alle Bits xi fragt, wenn yi=1

Bilde Zustand mit Hadamard ab und messe

Was ist die Erfolgswahrscheinlichkeit?

Analyse

Man kann zeigen, dass 1- aller Strings y Hamming Gewicht · n/2 + O(n1/2) haben

Daher ist der erreichte Zustand beliebig nah am gewünschten |xi

Fehler ist 5% bei n/2+n1/2 Fragen

Schlussfolgerung

n/2· Q(ID)· n/2+n1/2

…wenn wir untere Schranke Q(XOR)¸ n/2 zeigen können

Die Polynom Methode

Ein Quanten Black Box Algorithmus ist formal eine Folge von alternierenden unitären Operationen und Orakeltransformationen

Wir wollen einen Algorithmus mit wenigen Fragen auf ein Polynom mit geringem Grad abbilden

Dann untersuchen wir den notwendigen Grad um eine Funktion als Polynom darzustellen

Die Polynom Methode

Gegeben sei also ein Quantenalgorithmus im Black Box Modell mit T Fragen

Wir behaupten, dass sich die Amplituden des Endzustandes als Polynom vom Grad T darstellen lassen

Beweis durch Induktion: T=0: Amplituden sind Konstanten T! T+1: Seien die i(x) jeweils durch ein Polynom mit

Grad T gegeben Es folgt eine unitäre Transformation, unabhängig von

der Eingabe x: aufgrund der Linearität ist das neue i(x) einer Summe von vorherigen, also steigt der Grad nicht

Die Fragetransformation: Zustand |ii|ai|ki wird auf |ii|a© xii|ki abgebildet

Damit ist iak(x) danach gleich xi¢ i, a© 1, k+(1-xi)¢ i, a, k Also ein Polynom vom Grad T+1

Die Polynom Methode

Akzeptanzwahrscheinlichkeit ist eine Summe von quadrierten Amplituden, also ein Polynom von Grad 2T

Polynom kann multilinear gemacht werden durch Ersetzung von xi

k durch xi

Polynom hat nur reelle Werte

Schlussfolgerung

Wenn es einen Quantenalgorithmus gibt, der f mit T Fragen exakt berechnet, so gibt es ein Polynom p(x) vom Grad 2T, das auf allen Booleschen x erfüllt: p(x)=f(x).

Wenn der Quantenalgorithmus Fehler 1/3 hat, dann gibt es ein solches Polynom mit p(x)2[0,1/3] für f(x)=0 und p(x)2[2/3,1] für f(x)=1

Betrachte den Grad solcher Polynome!

Exakte Quantenalgorithmen Zu einer totalen Booleschen Funktion gibt

es genau ein multilineares Polynom, dass die Funktion exakt darstellt

deg(f) sei der Grad dieses Polynoms QE(f)¸ deg(f)/2 Beispiel: XOR, Polynom ist

Also Grad n, und somit QE(XOR) =n/2

Multilineare Polynome

Behauptung: Zu jeder Booleschen Funktion gibt es genau ein multilineares Polynom, das f exakt darstellt, d.h. f(x)=p(x) für alle Booleschen x.

Beweis: Sei f(x)=p(x)=q(x) für alle Booleschen x, aber p

q Dann ist p-q ein multilineares Polynom für g(x)=0,

aber nicht das Polynom mit nur Nullkoeffizienten Sei m ein Monom minimalen Grades mit

Koeffizient a0 in p-q Sei z der String, der alle zi in m als Einsen enthält

und sonst keine Einsen m(z)=1, und ebenfalls p(z)=a, Widerspruch

Weiteres Beispiel

Polynom für OR:

Also Grad n

Daher QE(OR)¸ n/2

Tatsächlich: QE(OR)=n

QE(OR)

Betrachte Amplituden des Endzustandes eines optimalen Algorithmus‘ für OR ohne Fehler als Polynome vom Grad T

Basiszustände |0yi seien verwerfend. Menge B solcher Zustände Für i aus B ist pi(x)=0 wenn x nicht 0n

Es gibt ein j aus B mit pj(0n) 0 Betrache reellen Teil q(x) von

1-pj(x)/pj(0n)

Klar: deg (q) · T= QE(OR) und q(0n)=0 und q(x)=1 sonst, daher deg(q)¸ deg(OR)=n

Weitere Fakten über exakte Polynome Wenn f von n Variablen abhängt, ist

deg(f)¸ log n-loglog n Nicht konstante symmetrische f haben

Grad n-o(n) Also QE(f)¸ (log n)/2 –o(log n)

Und QE(f)¸ n/2-o(n) für symmetrische nichttriviale f

Approximative Polynome

Wenn der Quantenalgorithmus mit T Fragen Fehler 1/3 hat, dann gibt es ein Polynom p mit Grad 2T mit p(x)2[0,1/3] für f(x)=0 und p(x)2[2/3,1] für f(x)=1

adeg(f) sei der minimale Grad eines solchen Polynoms

Wir erhalten: Q(f)¸ adeg(f)/2 Beispiel OR von 2 Bits: x1/3+x2/3+1/3,

somit adeg(OR2)=1

Symmetrisierung

Sei f eine symmetrische Funktion, also f konstant auf allen x mit |x|=k, d.h. es existieren Funktionswerte f0,…,fn

Betrachte Polynom p mit einer reellen Variablen, das p(k)2[0,1/3] für fk=0 und p(k)2[2/3,1] für fk=1

Aus einem Polynom für f erhalten wir ein solches Polynom gleichen Grades

Betrachten wir XOR

Wir erhalten also ein Polynom mit Grad T in einer Variablen, das erfüllt

p(k)2[0,1/3] für k gerade und p(k)2[2/3,1] für k ungerade, mit k2{0,…,n}

Beobachtung: p(k)-1/2 hat n Nullstellen! Also Grad n

Daher Q(XOR)=n/2

Symmetrisierung

Seien Permutationen von [1,…,n], p Polynom in n Var.

Setze psym(x)=

Lemma: Wenn p ein multilineares Polynom vom Grad d ist, dann gibt es ein Polynom mit einer Variable mit q(|x|)=psym(x) für alle x Beweis: Sei Vj die Summe aller Produkte von j Variablen p sym(x) kann als Summe

geschrieben werden Wert von Vj auf x ist Also Polynom vom Grad j abhängig von |x| Das gesuchte Polynom ist also