Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 04/051.12.

Fourier Transformation

Klassische Fouriertransformation: g sei Funktion ZL ! C

[Vektor mit L Einträgen]

Mit w=e2 i/L ist Matrix für Fouriertransformation durch FTL(i,j)=wij; 0· i,j· L-1 gegeben

Trivialer Algorithmus zur Fouriertransformation: Zeit O(L2)

Schnelle Fouriertransformation [FFT] in ZeitO(L log L)

Quanten Fourier Transformation

Sei L=2l. Sei |i=j=0,...,L-1 j |ji ein Zustand. Die Fouriertransformation von |i ist

|i =j=0,...,L-1 j |ji, mit

Also Fouriertransformation auf Superpositionen Auch QFT genannt Gibt es einen effizienten Algorithmus der QFT

implementiert? Effizient:polynomiell in l=log L

Quanten Fourier Transformation

Sei L=2l. Sei |i=j=0,...,L-1 j |ji ein Zustand.

Schreibe j=j1 jl; j = j12l-1 ++jl20

Setze 0.jt jt+1 ... jl = jt/2++jl/2l-t+1

Es gibt die folgende Produktrepräsentation der QFT:

|j1...jli wird abgebildet auf

1/2l/2 ¢ t=l,...,1 (|0i+ e2i 0. jt...jl |1i)

=1/2l/2 ¢ t=1,...,l (|0i+ e2ij/2t |1i)

Quanten Fourier Transformation

|j1...jli wird abgebildet auf 1/2l/2 ¢ t=l,...,1 (|0i+ e2i 0. jt... jl |1i)

Sei Rk folgendes Gatter

Wende H auf j1 an. Ergebnis: 1/21/2 ¢ (|0i+ e2i 0. j1 |1i) |j2,...,jli Wende nun durch jt mit t=2,...,l kontrollierte Rt

Gatter auf erstes Qubit an. Ergebnis: 1/21/2 ¢ (|0i+ e2i 0. j

1,...,j

l |1i) |j2,...,jli

Erstes Qubit korrekt (wie gewünschtes letztes Qubit)

Quanten Fourier Transformation

Bis auf Vertauschungen von Qubits vollständig;Anzahl der Gatter: l+(l-1)++1=O(l2)=O(log2 L)

Quanten Fourier Transformation

Achtung: Ergebnis der QFT ist eine Superposition, daher keine exponentielle Beschleunigung der normalen Fourier Transformation

Eigenschaften QFT

Kann in Zeit O(l2) berechnet werden, bzw. beliebig nah approximiert werden wenn nur Standard Gatter erlaubt

QFT ist unitär, da Schaltkreis unitär Setze w=e2i/L, dann ist FT-1

L(i,j)=w-ij;0· i,j· L-1

Translationsinvarianz: Sei QFT j=0,...,L-1 j |ji = j=0,...,L-1 j |ji

Tk: |ji |j+k mod Li. Dann istQFT Tk j=0,...,L-1 j |ji= QFT j=0,...,L-1 j |j+k mod Li

= j=0,...L-1 e2 ijk /L j |ji Also ist bei sofortiger Messung Tk ohne Wirkung

Phase Estimation

Problem: Gegeben für unitären Operator U, Potenzen Uj als Black Box; j=1,2,4,8,...,2t-1

Ausserdem gegeben: Eigenvektor |ui von U Gesucht: Eigenwert e2i, d.h. unbekannes Annahme: mit t Nachkommastellen (binär)

darstellbar Verwende t Qubits q0,...,qt-1 im Zustand |0i sowie

Zustand |ui Wende Hadamard auf q0, und kontrolliertes U=U1

mit Kontrolle q0 und Ziel |ui an Ergebnis: (|0i+e2i |1 i)/21/2 in q1, |ui unverändert Analoges für alle q1,...,qt-1

Phase Estimation

Ergebnis: (|0i+exp(2i2p) |1 i)/21/2

auf Qubit p, also 1/2t/2 ¢ p=t-1,...,0 (|0i+ e2i 0. p..t-1 |1i)insgesamt

QFT-1 gibt uns (Annahme hier: mit t Stellen darstellbar)

Phase Estimation

|0i+e2i2t-1|1i

|0i

|0i|0i

|ui

H

H

H

H

U1 U2 U4 U2t-1

|0i+e2i4|1i

|0i+e2i2|1i

|0i+e2i|1i

|0i

|ui

QFTy ergibt |i

Phase Estimation

Wenn nicht mit t Stellen darstellbar, dann ergibt sich Approximation

Um Genauigkeit 1/2n mit Wahrscheinlichkeit 1- zu erhalten setze t=n+log(2+1/)

Finden von Perioden

Funktion f:Z!ZN als Black BoxEs gibt ein r<N: f(i)=f(i+r) für alle i2Z i j+k ) f(i)f(j)

Finde r Lösen für beliebige periodische f

Uf: |ji |yi |ji |f(j) yi; j2ZL; f(j)y 2 ZN

Shors Algorithmus

log L+log N Arbeitsqubits log L Qubits im Zustand |0i ; 02ZL

log N Qubits im Zustand |1i ; 12ZN

Wende Hadamard auf 1. Register an Wende Uf an Ergebnis:

Messe zweites Register Ergebnis:

Shors Algorithmus

Ergebnis:

0 · j0 · r-1;

L-r · j0+(A-1)r · L-1 A-1 < L/r < A+1

Messung des ersten Registers jetzt wäre nutzlos

Shors Algorithmus

Ergebnis:

Wende QFT an Ergebnis:

d.h. Wahrscheinlichkeit von k ist unabhängig von j0 (Translationsinvarianz)

Shors Algorithmus

Ergebnis:

Messung: Wahrscheinlichkeit von k ist

Vereinfachende Annahme: r teilt L, d.h. A=L/r, dann

Shors Algorithmus

Vereinfachende Annahme: r teilt L, d.h. A=L/r, dann

Wenn A Teiler von k, dann =1/r Wenn A kein Teiler von k, dann = 0 (weil r mal

Wahrscheinlichkeit 1/r weg) D.h. wir erhalten Vielfaches von A=L/r, also cL/r

mit 0· c· r-1 Mit hoher Ws. ist c teilerfremd zu L/r Dann ggt(cL/r,L)=L/r, L bekannt, erhalten r

Shors Algorithmus

Allgemein: Wahrscheinlichkeit von k ist

„favorisiert“ Werte von k mit kr/L nahe an Integer Geometrische Reihe

mit k=2kr (mod L)/ L

Shors Algorithmus

mit k=2kr (mod L)/ L

Es gibt genau r Werte von k2ZL mit -r/2· kr (mod L) · r/2

Für diese also - r/L· k· r/Ld.h. mit j· A-1<L/r liegen die Winkel k

j alle in einer Halbebene ) kontruktive Interferenz!

Betrachte solches k

Shors Algorithmus

Es gilt |1-eik|· |k|[direkte Distanz „1“ von „eik“ ist kleiner als Bogenlänge]

Es gilt |1-eiAk|¸ 2A|k|/, wenn A|k|· denn sei dist(0,)=|1-ei|,dann ist dist(0,)/||¸ dist(0,)/=2/

Tatsächlich ist A < (L/r)+1,also Ak · A r/L < (1+r/L)

Shors Algorithmus

|1-eik|· |k| ;|1-eiAk|¸ 2A|k|/, wenn A|k|· Ak · A r/L < (1+r/L)

Shors Algorithmus

Wir erhalten jedes der r gewünschten k mit Wahrscheinlichkeit proportional zu 1/r, also insgesamt mit konstanter Wahrscheinlichkeit ein k mit-r/2· kr (mod L) · r/2 [Erfolg]

|kr-cL|· r/2 für ein c Dann:|k/L-c/r|· 1/(2L), d.h. k/L ist Approximation von c/r Wir kennen k und L. Wähle reduzierte Darstellung von k/L als

rationale Zahl. c ist uniform zufällig aus 0,...,r-1 c kein Teiler von r mit Wahrscheinlichkeit 1/log c Dann: Berechnung von c/r gibt uns auch r Wähle also L gross genug, um gute Approximation zu erhalten

Shors Algorithmus

Wir erhalten mit konstanter Wahrscheinlichkeit ein k mit |k/L-c/r|· 1/(2L)

Mit Wahrscheinlichkeit 1/log c<1/log L ist ggt(c,r)=1

Sei r<N, L=N2

c/r ist rationale Zahl mit Nenner <N Zwei solche Zahlen liegen nicht dichter

aneinander als 1/N2=1/L > 1/(2L) Es gibt also im Intervall nur die eine rationale Zahl

c/r mit Nenner < N Finde die rationale Zahl mit Nenner < N, die nah

an k/L liegt Kettenbruchmethode

Kettenbruchmethode

Die Kettenbruchmethode berechnet zu einer reellen Zahl die Kettenbruchdarstellung

Wenn |c/r-|· 1/(2r2), dann wird in einem der Schritte das Paar c,r erzeugt, nach höchstens O(t3) Operationen für t-Bit Zahlen

Performance insgesamt

Mit konstanter Wahrscheinlichkeit ist k gut Mit Wahrscheinlichkeit 1/log N ist auch c gut (d.h.

teilerfremd zu r) Anzahl Wiederholungen daher O(log L)

Zum Finden der Ordnung in ZN wähle also L=N2,

d.h. 2 log N +log N Qubits insgesamt Fouriertransformation in O(log2 L) Dann kann mit dem Kettenbruchalgorithmus r

bestimmt werden aus k/L in O(log3 L) Zeit Errechnetes r kann mit Black Box getestet

werden Also Zeit erwartet O(log4 N), kann auf O(log3 N)

gesenkt werden

Kettenbruchmethode

Gegeben reelles Approximiere durch

Finde Darstellung so: Nehme ganzzahligen Teil als a0, invertiere Rest, iteriere

Theorem: |p/q-|· 1/(2q2), dann tritt p/q im Algorithmus nach O(log (p+q)) Schritten auf