Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/0626.1.

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

Approximative Polynome uns symmetrische Funktionen Sei (f)=min {|2k-n+1|: fk fk+1} für

symm. f Paturi: adeg(f)=( (n (n-(f)))1/2 )

Beispiel: OR: (OR)=n-1, also adeg:

Beispiel MAJORITY:

Charakterisierung Q(f) für symmetrische Funktionen Paturi gibt uns Q(f)¸((n (n-(f)))1/2

Es gilt auch: Q(f)· O((n (n-(f)))1/2

Beweis: Beobachtung: Es reicht, zu wissen:

• |x|, wenn |x|· (n-(f))/2• |x|, wenn |x|¸ (n+(f))/2• Ansonsten: f ist konstant zwischen (n-(f))/2

und |x|¸ (n+(f))/2

Charakterisierung Q(f) für symmetrische Funktionen

Beobachtung: Es reicht, zu wissen:• |x|, wenn |x|· (n-(f))/2• |x|, wenn |x|¸ (n+(f))/2• Ansonsten: f ist konstant zwischen (n-(f))/2 und

|x|¸ (n+(f))/2

Suche i mit x_i=1 bis (n-(f))/2 viele gefunden oder keine mehr vorhanden

Suche i mit x_i=0 bis (n-(f))/2 viele gefunden oder keine mehr vorhanden

Entscheide Laufzeit: Finde t markierte Positionen: O( ) Daher:

Wie gut sind untere Schranken mit der Polynom Methode? Behauptung: adeg(f) und Q(f) sind

polynomiell verwandt für totale Funktionen f Für partielle Funktionen ist dies falsch!

Plan: Zeigen: Untere Schranken für adeg via „block-

sensitivity“ bs(f) Zeigen obere Schranken für D(f) via bs(f)

Weiteres Korollar: D(f) und Q(f) polynomiell verwandt!

(Block)-Sensitivität

s(f,x) sei die Anzahl von Bits, die man in x flippen kann, so dass für das erhaltene x‘ gilt f(x‘) f(x)

Beispiel: s(OR,0n)=n

s(f)=maxx(s(f,x) )

Blocksensitivität: Erlaube ganze Blöcke zu flippen

(Block)-Sensitivität

Blocksensitivität: Erlaube ganze Blöcke zu flippen

bs(f,x): max k, so dass folgendes möglich: Bilde k disjunkte Mengen von Variablen

(Blöcke) Flippe alle Variablen in Block i) f-Wert

wechselt bs(f) is Maximum über alle x von bs(f,x)

Unterschied s(f) und bs(f) Es gibt eine Boolesche Funktion f mit s(f)=n1/2 und

bs(f)=n/2 Beweis:

f: n1/2 Blöcke von n1/2 Variablen f(x)=1, wenn es einen Block gibt mit 2 Einsen

nacheinander und sonst Nullen bs(f)¸ n/2: 0n ist sensitive Eingabe s(f)· n1/2: Übung

Wir zeigen:

Q(f)¸ ( bs1/2(f) )

Beispiel: bs(OR)=s(OR)=n

Dann: D(f)· C2(f) C(f): Zertifikatskomplexität

Und C(f)· s(f) bs(f)

Damit: Q(f)¸ D1/8 (f)

Die untere Schranke via bs(f) FAKT [Ehlich und Zeller]:

Sei p ein Polynom mit b1· p(i)· b2 für alle ganzen Zahlen 0· i· n

Es gelte |p‘(x)|¸ c für ein reelles 0· x· N Dann ist deg(p)¸

Theorem: adeg(f)¸ (bs(f)/4)1/2

Die untere Schranke via bs(f) Sei x eine Eingabe mit bs(f,x)=bs(f) ObdA nehmen wir an, x=0k, bs(f)=k Betrachte Symmetrisierung eines

Polynoms mit minimalem Grad, erhalten univariates p

0· (0)· 1/3 1¸ p(1)¸ 2/3 1¸ p(i)¸ 0 für i=2,…,n Daher: p‘(z)¸ 1/3 für z aus [0,1] Dann gilt: deg(p)¸

Die untere Schranke via bs(f) FAKT [Ehlich und Zeller]:

Sei p ein Polynom mit b1(x)· p(i)· b2 für alle ganzen Zahlen 0· i· n

Es gelte |p‘(x)|¸ c für ein reelles 0· x· N Dann ist deg(p)¸

Folgt aus Markov‘s Theorem: Sei p ein univariates Polynom vom Grad d, so dass

für alle a· x· b gilt: c· p(x)· e. Dann gilt |p‘(x)|· d2(e-c)/(b-a)

Beweis: Es gilt: für alle reellen x aus [0,n]: b1-c/2· p(x)· b2+c/2

Markov: c· deg2(p)(c+b2-b1)/n Damit: deg2(p)¸

Die obere Schranke durch bs(f) Wollen zeigen: D(f)· bs4(f)

Dazu betrachten wir die Zertifikatskomplexität C(f)

Wir zeigen D(f)· C2(f) Und C(f)· bs2(f)

Zertifikate

Definition Ein Term der Form

c=(xi(1)=b1 Æ…Æ xi(k)=bi(k)) heisse ein a-Zertifikat für eine Boolesche Funktion f, wenn für alle Eingaben x2 {0,1}n die mit dem Term übereinstimmen, f(x)=a gilt

Eingabe x hat Zertifikat c, wenn c auf x wahr k sei die Länge des Zertifikates f habe Zertifikatskomplexität k, wenn es für

alle Eingaben ein Zertifikat der Länge k gibt, und für kleinere k‘ dies nicht gilt

Dann sei C(f)=k

Zertifikate

Definition f habe a-Zertifikatskomplexität k, wenn

es für alle Eingaben mit f(x)=a ein Zertifikat der Länge k gibt, und für kleinere k‘ dies nicht gilt

Dann sei Ca(f)=k

Beispiel

C1(OR)=1,

Verwende Zertifikate xi=1

C0(OR)=n Wenn nicht alle Bits auf 0 gesetzt sind, ist

OR(x)=1 möglich C(OR)=n

C(f) vs. D(f)

Theorem D(f)· C0(f) C1(f)

D(f) gross: wenn C0(f) klein, dann ist C1(f) gross Beispiel:

AND(OR(…),OR(…),…,OR(…)) Formel Tiefe 2 mit Grad n1/2

Beispiel

C0(f),C1(f)=n1/2

C0: fix. OR C1: fix. 1 per AND

Aber: D(f)=n Also Theorem optimal

Beweis

Beobachtung: Jedes Paar von 1-Zertifikat und 0-Zertifikat hat

gemeinsame Variable Denn sonst gibt es eine Eingabe, die mit

beiden konsistent! Algorithmus:

Exponiere 1-Zertifikat Kürze alle 0-Zertifikate Bis nicht mehr möglich

Der Algorithmus

C1(f)=k, C0(f)=l K:Menge von 1-Zertifikaten der Länge k, die 1-Eingaben

überdeckt L:Menge von 0-Eingaben …

Wähle c aus K, Frage alle Variablen in c c erfüllt: Akzeptiere Sonst: Entferne c aus K Für alle d aus L: wenn d noch konsistent mit

gelesenen Var., dann entferne aus d bekannte Variablen, sonst entferne d

Wenn L leer ist: akzeptiere Wenn L nur noch triviale Zertifikate enthält:

Verwerfe Wenn K leer ist: verwerfe

Analyse

Korrektheit: Für alle Eingaben x gibt es ein 0-Zert. oder ein 1-

Zert. f(x)=0, dann wird 0-Zert. nie entfernt, also wird

verworfen f(x)=1, mit 1-Zert. c: Entweder

c wird gefragt, dann wird akz. Oder: Es werden andere c‘ aus K gefragt, bis L

leer Es wird akzeptiert

Laufzeit

Wenn c aus K gefragt wird, werden alle d aus L entweder gestrichen, oder um 1 Variable gekürzt

Kosten des Fragens von c: k Anzahl der Runden, bis L leer: höchstens l In allen anderen Fällen wird vorher entschieden Gesamt: D(f)· kl=C0(f)C1(f)

Zusammengefasst

C(f)· D(f)· C2(f) C1(f),C0(f)· D(f)· C0(f)C1(f)

Nichtdeterminismus entspricht C1

C(f) vs. bs(f)

Theorem C(f) · bs(f) s(f)

Beobachtung: Wenn (für f und x) B ein minimaler Block von

Variablen ist, den zu flippen den Funktionswert ändert,dann ist s(f)¸ |B|.

Denn: Sei x‘ wie x mit B geflippt Dann ändert auf x‘ jede Variable in B den

Funktionswert, d.h. s(f,x‘) ¸ |B|

Beweis

Idee: für jedes x konstruiere ein kurzes Zertifikat Wenn für alle x ein Zertifikat der Länge s(f)bs(f,x)

existiert, gilt C(f)· s(f) bs(f) Sei x gegeben, B1,..., Bk Blöcke wie in Def mit

k=bs(f,x) Blöcke seien minimal, d.h. |Bi|· s(f)

Setze alle Variablen in [i Bi wie in x Klar: Monom c mit s(f)bs(f,x) Variablen

Beweis

Ist c ein korrektes Zertifikat? Sei x‘ eine Eingabe mit f(x‘) f(x) und x‘

konsistent mit c Sei Bk+1 die Menge der Variablen, wo x, x‘

unterschiedlich Klar: auf x ist f für Bk+1 sensitiv

Aber Bk+1 ist disjunkt von den Variablen in c, denn dort sind x und x‘ gleich!

Also ist bs(x)>k, Widerspruch!