Quantum Computing Hartmut Klauck Universität Frankfurt WS 04/05

Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 04/05

Organisatorisches Vorlesung: Mi. 14-16 c.t. Übung: Fr. 16-17 (ab 29.10.) Schein: Fachgespräch Zuordnung T2,T3 Voraussetzung: Vordiplom

(Informatik, Mathematik oder Physik) Website:

www.thi.informatik.uni-frankfurt.de/~klauck/QC04.html

Literatur

Nielsen/Chuang: Quantum Computation and Quantum Information

(Cambridge)

Ebenfalls empfohlen (online):

John Preskill's lecture notes

Umesh Vazirani's course

Warum Quantum Computing? Quantenmechanik: physikalische Theorie

(vor allem) der mikroskopischen Welt Moore’s Law: Alle ... (18 Mon?) verdoppelt

sich die Rechenleistung/Anzahl der Transistoren pro mm2

Grenze: 1 Transistor pro Elektron Quantenmechanische Effekte !

(binnen <20 Jahren)

Hitzeentwicklung in integrierten Schaltungen:

“Löschen” von Information nur möglich durch Abstrahlen von Wärme

) Reversible Berechnungen!

Quantenberechnungen sind reversibel

Warum Quantum Computing?

Warum Quantum Computing? Können Quanteneffekte sogar nützlich

sein? Es gibt einen Quantenalgorithmus, der

ganze Zahlen in polynomieller Zeit in Primfaktoren zerlegt, und so das RSA Kryptoverfahren bricht

Es gibt Quantenkryptographische Verfahren, die sicher sind (unter der Annahme, dass QM korrekt ist)

Weitere Gründe

Landauer: Information is physical Computation is physical Quantenmechanik ist ein

Berechnungsmodell

Quantenmechanik

Quantenmechanik

Selber Ausgang des Experimentes, wenn einzelne Elektronen/Photonen ausgestossen werden

) Wellenverhalten nicht bloss “statistisch”

Quantenmechanik

Historisches

Entwicklung der Quantenmechanik:Planck 1900, Schrödinger, Heisenberg, Bohr, Einstein.....

von Neumann’s Formalismus 1935: Einstein, Podolsky, Rosen

beschreiben quantenmech. “Verschränkung” (entanglement)

heute bestbestätigte physikalische Theorie

(Quanten) Informatik

1936: Turing schlägt universelle Berechnungsmaschine vor (Church Turing These)

1948 Shannon’s Informationstheorie 1965 Moore’s Law 1982: Feynman beobachtet, dass

Quantensysteme nicht effizient auf klassischen Computern simulierbar sind, schlägt quantenmechanische Computer

1982 Wiesner: Quantenkryptographie

Quanten Informatik

1985 Deutsch: erster Quantenalgorithmus 1993 Quantum Teleportation 1994 Shor: Quantenalgorithmus zum

Faktorisieren ganzer Zahlen 1996 Grovers Algorithmus:

unsortierte Datenbank mit n Elementen kann Zeit durchsucht werden

Qubits

Quantenmechanik ist eine Theorie von Zuständen und Transformationen

Zustände: Vektoren

Bits: 0 oder 1, in einem Register Zugeordnete Zustände |0i, |1i

Beispiele: Weg eines Elektrons im Doppelschlitzexperiment, Polarisation Photon

Quantenzustände: |0i+ |1i, ||2 +||2=1

Qubits (II)

|0i, |1i Basisvektoren im 2-dimensionalen komplexen Vektorraum C2

Qubits: |0i+ |1i, ||2 +||2=1 ,: Amplituden Einheitsvektoren (euklidische Norm) Vergleich: Wahrscheinlichkeitsverteilungen:

0 mit Ws. p, 1 mit Ws. 1-p) Einheitsvektoren 1-Norm

Qubits: , sind (komplexe) Zahlen, möglich. negativ!

Quadrate ergeben Ws. Verteilung

Quantenformalismus

Quantenzustände sind Vektoren in einem Hilbertraum (Vektorraum mit innerem Produkt)

Hilbertraum entspricht Qubit Register

Hilbertraum hier: Ck mit Standardprodukth (vi) | (wi) i =i=1…k vi

*wi

x*: komplex konjugierte Zahl

Dirac Notation

h | “BRA” Zeilen Vektor | i “KET” (Spalten) Vektor h | i inneres Produkt

(Produkt von Zeilenvektor und Spaltenvektor)

Mehrere Qubits

Hilbertraum: Dimension 2k

D.h. 2k Basisvektoren Notation |ii, i=1,...,2k

Einheitsvektoren (Zustände) sind von der Form i i |ii; i=1....2k

Alternativ: identifiziere i=1...2k mit x2{0,1}k

Basiszustände |xi, x2 {0,1}k

Basiszustände entsprechen klassischen Belegungen des “Registers”

Allgemeine Zustände sind “Superposition” von 2k Strings

Tensorprodukt

Hilberträume H, K, Dimension dH und dK

Tensorprodukt H K ist Raum der Dimension dH¢dK

Tensorprodukt von Vektoren: (a1,..., al) (b1,...,br)= (a1b1,a1b2,...,a1br,a2 b1,......,albr)

Beispiel: |0i = (10)T; |1i= (01)T

und |01i= |0i |1i = (0100)T

Basiszustände von H K: |xi |yi =|xyi

Was geschieht man mit Qubits? Quantensysteme evolvieren gemäss der

Schrödinger Gleichung Ergebnis: Quantentransformation;

entspricht unitärer Transformation auf Zuständen

Lineare Algebra

Lineare Abbildungen A(x+y)=Ax+Ay x,y: Vektoren in Ck, A: k £ k Matrix Reelle Zahlen: Abbildungen O orthogonal, wenn

OOT=I komplexe Zahlen: U unitär, wenn UUy =I

U*: Einträge komplex konjugiertUy = (U*)T

unitäre Abbildungen bewahren die Länge von Vektoren (bilden Zustände auf Zustände ab)

Transformation in QM:unitäre Abbildung (reversibel)

Beispiel unitäre Transf.

Auf einem Qubit:klassische Transformationen:Identität, Negation

Hadamard Transformation:

Beispiel Transformation

Beispiel Transformation

Beispiel Transformation

Unitäre Transformationen U |xi definiert für alle x2 {0,1}k

) U definiert

Tensorprodukt:

A B=

Beispiel: H n=H H: n-faches Produkt von H, Hadamard Transformation auf n Qubits

H n ( |0i ) n = ( H|0i ) n

Messungen

Quantenzustände (Vektoren in Ck) werden durch unitäre Abbildungen transformiert

Wie bekommt man eine Ausgabe in einer Berechnung?

“Messe” i i |ii

Ergebnis: i mit Wahrscheinlichkeit |i|2

i |i2|=1

Nach der Messung ist der Zustand zu |ii “kollabiert”, wenn Ausgabe i beobachtet

Messprozess ist “Postulat” wie unitäre Entwicklung

Zusammenfassung

Zustände: Einheitsvektoren in Hilbertraum, log Dimension entspricht Anzahl Qubits

Superposition der Strings Länge k ergibt ein Register mit k Qubits, Hilbertraum dim 2k

Evolution: unitäre Transformation Messung: i |ii ergibt Ausgabe i

mit Ws |i|2, Zustand kollabiert zu |ii bei Ausgabe i

Quanteninformatik

Jede lokale unitäre Transformation ist berechenbar (auf 2 Qubits)

Globale Transformation aus lokalen zusammensetzen (Quanten Schaltkreise)

Zeit für einen Algorithmus David Deutsch s Algorithmus Setup: Input ist Black Box Funktion f:{0,1} {0, 1}

unbekannt (Eingabe) Zugriff: Lese f(0), f(1) Entweder f(0)=f(1) oder f(0) f(1) Problem: Welcher Fall?

Deutschs Problem

Zugriff f:{0,1}{0,1} durch Lesen von f(0) oder f(1)

klassische deterministische Algorithmen ohne Fehler müssen f(0) und f(1) lesen.

Randomisierte Algorithmen mit 1 Frage haben Fehlerwahrscheinlichkeit 1/2

Quantenfragen

randomisierte Fragen: Ws verteilung auf 0 oder 1

Quanten Frage: SuperpositionNotwendig: unitäre Operation!

Uf |ii|ai=|ii|a© f(i) für alle i,a2{0,1}; © ist XOR Operation: 0©0=0; 0©1=1; 1©1=0

Uf auf allen Basiszuständen definiert) Uf definiert

Idee “Parallele” Berechnung Uf: Frage an das f-Orakel Zwei Qubits

(H I) |00i I: Identität=1/21/2 (|00i+|10i)

Wende Uf an Ergebnis 1/21/2 ( |0,f(0)i+|1,f(1)i ) f:{0,1}n {0,1}: wende Uf H n an Ergebnis:

“Parallele” Berechnung

Was kann man mit diesem Zustand anfangen?

Messung ergibt nur uniforme Verteilung auf x,f(x)

Deutschs Algorithmus

Starte mit |01i Wende H H an Ergebnis:

1/2 (|0i +|1i) (|0i -|1i) Wende Uf an Ergebnis:

1/2 ( |0,f(0)i-|0,f(0)©1i+|1,f(1)i-|1,f(1)©1i )

Deutschs Algorithmus

Idee für Analyse:Effekt Uf auf |xi 1/21/2(|0i-1i):

(-1)f(x) |xi 1/21/2(|0i-|1i)

Uf |0i 1/21/2( |0i-|1i ) = |0i 1/21/2 ( |f(0)i -|f(0) © 1i )= (-1)f(0) |0i 1/21/2( |0i-|1i)

Deutschs Algorithmus

Idee für Analyse:Effekt Uf auf |xi 1/21/2(|0i-1i):

(-1)f(x) |xi 1/21/2(|0i-|1i)

Uf |1i 1/21/2( |0i-|1i ) = |1i 1/21/2 ( |f(1)i -|f(1) © 1i )= (-1)f(1) |1i 1/21/2( |0i-|1i)

Zweites Qubit ist nur zur Hilfe....und kann jetzt vergessen werden

Deutschs Algorithmus

Wende Hadamard an (auf verbleibendem Qubit)

Zustand vorher:f(0) = f(1): § 1/21/2 (|0i+|1i)f(0) f(1): § 1/21/2 (|0i-|1i)

Fall 1: f(0)=f(1):H § 1/21/2 (|0i+|1i) = § |0i

Fall 2: f(0) F(1):H § 1/21/2 (|0i-|1i) = § |1i

Messung unterscheidet Fälle sicher

Deutsch Algorithmus

H

Uf

H|0i

|1i

MessungH

Deutsch-Josza Algorithmus

f:{0,1}n {0,1} Ist f balanciert (50% 0, 50 % 1) oder konstant?

Annahme: einer der beiden Fälle, ansonsten Ausgabe egal

Quantum : 1 Frage Deterministisch: 2n/2+1 Fragen!

Warum? Lege f abhängig von den Fragen eines

Algorithmus’ fest, f(x1)=0,...,f(xl)=0 Bis l > 2n/2 keine korrekte Entscheidung möglich Algorithmus funktioniert für f nicht “Adversary Argument”

Deutsch Josza Algorithmus

n Qubits im Zustand |0ni 1 Qubits im Zustand |1i Wende H n+1 an, dann Uf

Ergebnis:

Wende H n an und messe Ergebnis: 0n iff f ist konstant

Diskussion

Deterministisch: 2n/2+1 Fragen Quantum: 1 Frage, O(n) Gatter (lokale

Transformationen), kein Fehler Randomisierte Algorithmen sind ebenfalls

effizient, aber nur mit Fehler