View
108
Download
1
Category
Preview:
Citation preview
Quantum Computing
Hartmut KlauckUniversität FrankfurtWS 04/0517.11.
Simons Problem
Gegeben: Black Box Funktion f:{0,1}n!{0,1}n Es gibt ein geheimes s2{0,1}n:
Für alle x: f(x)=f(x©s) Für alle x,y: x y©s ) f(x) f(y)
Bestimme s !
Beispiel: f(x)=2bx/2c Jedes k: f(2k)=f(2k+1); s=00 ... 01
Simons Algorithmus löst das Problem in Zeit poly(n)
Jeder klassische randomisierte Algorithmus benötigt (2n/2) Fragen an die Black Box, selbst wenn Fehler erlaubt sind
Klassische Algorithmen
Gegeben: randomisierter Fragealgorithmus, der s berechnet, gegeben Orakelzugriff auf f
Fixiere ein f=fs für jedes s Wenn es randomisierten Algo mit T Fragen (worst
case) und Erfolgswahrscheinlichkeit p gibt, dann gibt es einen deterministischen Algo mit T Fragen und Erfolg p für zufällige s
Randomisierter Algorithmus ist Schaltkreis mit zusätzlicher Eingabe r2{0,1}m
Es Er [Erfolg auf fs bei Zusatzeingabe r]=p ) es gibt ein r, so dass Es [Erfolg auf fs bei Zusatzeingabe r]¸ p
Fixiere r ) deterministischer Algorithmus
Klassische Algorithmen
s sei zufällig aus {0,1}n-{0n} Dies bestimmt f=fs
Gegeben: deterministischer Fragealgorithmus, Erfolg 2/3 auf zufälligem s
k Fragen seien schon gestellt; Fixiere Werte (xi,f(xi)) Wenn es xi,xj gibt mit f(xi)=f(xj), dann Erfolg, Stop Sonst: alle f(xi) verschieden,
kein Wert xi©xj=s, Anzahl Paare Es gibt noch mindestens 2n-1- mögliche s s kann noch als uniform zufällig unter diesen
angesehen werden
Klassische Algorithmen
Es gibt noch 2n-1- ¸ 2n-k2 mögliche s s kann noch als uniform zufällig unter
diesen angesehen werden Frage xk+1 (abhängig vorherige
Fragen/Antworten) Für jedes feste xk+1 gibt es k Kandidaten
s‘(1),...,s‘(k): s‘(j)=xj©xk+1 für s Wahrscheinlichkeit, dass ein Kandidat
richtiges s trifft · k/ (2n-k2)[über Wahl von s]
Klassische Algorithmen
Wahrscheinlichkeit, dass ein Kandidat richtiges s trifft · k/(2n-k2)[über Wahl von s]
Gesamterfolgswahrscheinlichkeit:
Wenn T<2n/2/10, dann Erfolg zu klein
Variation
Entscheidungsproblem: mit Wahrscheinlichkeit 1/2: s=0n
mit Ws 1/2: s uniform aus {0,1}n-{0n} Algorithmus entscheide, welcher Fall Analyse analog zu vorher, bei weniger als
2n/2/10 Fragen Erfolgswahrscheinlichkeit nah 1/2
Der Quantenalgorithmus
Beginne mit Zustand |0ni|0ni Wende H n auf erste n Qubits an Wende Uf an Messe Qubits n+1,...,2n Ergebnis f(z) Es gibt z, z©s mit f(z)=f(z©s) Zustand: (1/21/2 |zi + 1/21/2|z©si) |f(z)i Vergesse |f(z)i
Der Quantenalgorithmus
Zustand: 1/21/2 |zi + 1/21/2|z©si Jedes z2{0,1}n mit Wahrscheinlichkeit 1/2n,
gegeben also Wahrscheinlichkeitsverteilung auf Zuständen [„gemischter Zustand“]
Messung ergäbe einfach zufälliges z aus {0,1}n [zufälliges z aus Messung 1, dann mit Ws. 1/2: z, mit Ws. 1/2: z©s, insgesamt zufälliges z]
Wie bekommt man Information über s?
Wende wieder an H n an
Der Quantenalgorithmus
Zustand: 1/21/2 |zi + 1/21/2|z©si z uniform zufällig Wende wieder an H n an Ergebnis:
y y |yi mit y=1/21/2 ¢1/2n/2 (-1)y¢z +1/21/2¢1/2n/2(-1)y¢
(z©s)
=1/2(n+1)/2 ¢ (-1)y¢z [1+(-1)y¢s]
y¢z=i yizi
Der Quantenalgorithmus
y y |yi mit
y=1/2(n+1)/2 ¢ (-1)y¢z [1+(-1)y¢s]
Fall 1: y¢s ungerade ) y=0
Fall 2: y¢s gerade ) y=§ 1/2(n-1)/2
Messe nun[Wahrscheinlichkeiten unabhängig von z]
Immer: Ergebnis y: yi si ´ 0 mod 2
Also Gleichung über Z2, alle y mit yi si ´ 0 mod 2 gleich wahrscheinlich
Postprocessing
Ergebnis Gleichung yi si ´ 0 mod 2
Alle y mit yi si ´ 0 mod 2 gleiche Ws. Reduziert Anzahl der möglichen s um 1/2
Weiteres Vorgehen: Wiederhole n-1 mal Löse Gleichungssystem
Wenn n-1 linear unabhängige Gleichungen erhalten, dann ist s bestimmt
Simons Algorithmus
H|0ni
|0niUf
n-1 mal, dann Gleichungssystem lösen
H
y(1),...,y(n-1)
Analyse
Durch n-1 linear unabhängige Gleichungen ist s bestimmt, jede Gleichung hat uniform zufällige Koeffizienten y(j)1,...,y(j)n unter Bedingungy(j)¢s=0 mod 2[d.h. aus Unterraum U Dim. n-1 von (Z2)n]
Wahrscheinlichkeit, dass y(j+1) linear abhängig von y(1),...,y(j): Vj=span[y(1),...,y(j)] hat Dim. j
Ws, dass zufälliges y(j+1) aus U in Vj liegt:2j/2n-1
Wahrscheinlichkeit, dass alle lin. unabh.:j=1,...,n-1 (1-2j-1/2n-1)= j=1,...,n-1 (1-1/2j)
Analyse
Wahrsch. dass alle lin. unabh.:j=1,...,n-1 (1-1/2j)
Abschätzung: mindestens1/2 ¢ (1-[j=2,...,n-1 1/2j])¸ 1/4[Benutze (1-a)(1-b)¸ 1-a-b für 0<a,b<1]
D.h. mit Wahrscheinlichkeit 1/4 findet der Algo n-1 linear unabh. Gleichungen, und s kann berechnet werden
Durch Gauss Elimination O(n3) oder durch andere Verfahren O(n2.376)
Variation
Entscheidungsproblem: mit Wahrscheinlichkeit 1/2: s=0n
mit Ws 1/2: s uniform aus {0,1}n-{0n} Algorithmus soll entscheiden, welcher Fall Verwende selben Algorithmus wie zuvor
Zusammenfassung
Simons Problem kann durch einen Quantenalgorithmus mit Zeit O(n2.376) und O(n) Fragen mit Erfolgswahrscheinlichkeit 0.99 gelöst werden
Jeder klassische randomisierte Algorithmus mit Erfolgswahrscheinlichkeit 2/3 braucht (2n/2) Fragen (und Zeit)
Bisherige Algorithmen
Deutsch-Josza und Simon: f balanciert oder konstant f hat „Periode“ s (über (Z2)n)
Erst Hadamard, dann Uf, dann Hadamard und Messung
D-J: Black Box mit Ausgabe (-1)f(x)
S: normale Black Box
Bestimmen der Ordnung über ZN
Gegeben seien ganze Zahlen x, N, x<N Ordnung r(x) von x in ZN:
min. r: xj =1 mod N „Periode“ der Potenzen von x Black Box Ux,N rechne
Ux,N |ji|ki= |ji|xjk mod Ni Quantenalgorithmus, um r(x) zu
bestimmen?
Bestimmen der Ordnung über ZN
Ux,N |ji|ki= |ji|xjk mod Ni Quantenalgorithmus, um r(x) zu
bestimmen? Algorithmus von Shor findet r(x) in Zeit
poly(log N) trivialer klassischer Ansatz: berechne xi
für i=1,...,r(x) ist ineffizient, da r(x)=N möglich
Anwendung eines solchen Algorithmus
Faktorisierungsproblem: Gegeben natürliche, zusammengesetzte Zahl N finde einen nichttrivialen Faktor
Kann durch einen Algorithmus zur Ordnungsbestimmung gelöst werden !
Faktorisierung
Wenn ein nichttrivialer Faktor in polynomieller Zeit gefunden werden kann, kann die komplette Primfaktorisierung in polynomieller Zeit gefunden werden, da es zu N höchstens log N Primfaktoren gibt
polynomieller Zeit: in der Länge von N, d.h. log N
Naiver Algorithmus: teste alle Faktoren <N1/2, d.h. exponentielle Zeit
Bester bekannter klassischer Algo: Zeit exp( O ( log1/3 N loglog2.3N ) )
Reduktion Faktorisierung auf Ordnungsfinden Eingabe natürliche Zahl N
1. Test ob N Primzahl, Ausgabe N2. Test ob N= ab für nat. Zahlen a,b>1,
Ausgabe a3. Test ob N gerade, Ausgabe 24. Wenn nein: N=p1
(1) pm(m) mit
m>1,(j)¸1
Reduktion Faktorisierung auf Ordnungsfinden N=p1
(1) pm(m) mit m>1,(j)¸1
Ansatz: Wenn man eine nichttriviale Lösung zu x2=1
mod N finden kann, dann kann ein Faktor von N berechnet werden
Wenn y aus [1,...,N-1] gezogen wird und teilerfremd zu N ist, dann ist die Ordnung r von y mit hoher Ws. gerade und yr/2 -1 mod N
yr/2 1 mod N Dann erfüllt x=yr/2 die Gleichung x2=1 mod N
und x ist nichttrivial Z*
N : Gruppe der y aus [1,...,N-1] die teilerfremd zu N sind, mit Multiplikation
Reduktion Faktorisierung auf Ordnungsfinden Theorem V.1:
Sei N eine zusammengesetzte Zahl und x eine Lösung von x2=1 mod N mit1 < x < N-1. Dann sind nichttriviale Teiler von N: ggt(x-1,N) ggt(x+1,N)
Theorem V.2:Wenn N=p1
(1) pm(m) Primfaktorisierung, und x
uniform aus Z*N gezogen wird, dann ist
Prob[r(x) ist gerade und xr/2 -1 mod N] ¸ 1-1/2m-
1¸ 1/2
Reduktion Faktorisierung auf Ordnungsfinden Eingabe natürliche Zahl N
1. Test ob N Primzahl, Ausgabe N2. Test ob N= ab für nat. Zahlen a,b>1,
Ausgabe a3. Test ob N gerade, Ausgabe 24. Wenn nein: N=p1
(1) pm(m) mit
m>1,(j)¸1
Reduktion Faktorisierung auf Ordnungsfinden
4. N=p1(1) pm
(m) mit m>1,(j)¸1
5. Bestimme zufälliges x aus [1,...,N-1]. Wenn ggt(x,N) 1, dann Ausgabe ggt(x,N)
6. Bestimme Ordnung r von x in ZN
7. Wenn r gerade ist, und xr/2 -1 mod N, dann berechne ggt(x-1,N) und ggt(x+1,N)
8. Wenn nicht, dann wiederhole 5.-7.
Analyse:
Schritt 1 [Primzahltest] deterministisch in Zeit poly(log N) [AKS02][Test, ob ab für nat. Zahlen a,b; Test ob Primzahl]
Schritt 5: ggt(y,N) kann in Zeit O(L3) berechnet werden, Euklidischer Algorithmus
Schritt 6: per Reduktion Schritt 7: mit Wahrscheinlichkeit 1/2 Schritt 8: erwartet O(1) Wiederholungen
Bemerkung
Finden der Ordnung von x in ZN ist tatsächlich per Polynomialzeit-Reduktionen äquivalent zum Faktorisierungsproblem
Shors Algorithmus löst Ordnungsfinden bezüglich einer als Black Box gegebenen Potenzierungsfunktion
Theorem V.1
Theorem V.1:Sei N eine zusammengesetzte Zahl und x eine Lösung von x2=1 mod N mit1 < x < N-1. Dann sind nichttriviale Teiler von N: ggt(x-1,N) ggt(x+1,N)
Beweis:
x2=1 mod N) (x-1)(x+1)=0 mod NN teilt (x-1)(x+1), x-1<x+1<N, daher gibt es einen nichttrivialen gemeinsamen Faktor
Recommended