Quantencomputer und Quantenkryptographie – demnächst auch in Ihrem Laptop? Fakultät für Physik...

Quantencomputer und Quantenkryptographie –

demnächst auch in Ihrem Laptop?

Fakultät für PhysikUniversität Wien

Institut für Quantenoptik und QuanteninformationÖsterreichische Akademie der Wissenschaften

Club IT der Fachgruppe UBIT

WIFI Wien, 19. Mai 2011

Johannes Kofler

Überblick

• Einleitung

• Quantenphysikalische Grundbegriffe Superposition & Verschränkung Bellsche Ungleichung

• Quantenkryptographie Funktionsweise Realisierungen

• Quantencomputer Grundlagen Algorithmen & Implementierungen

• Ausblick

Entwarnung

“I think I can safely say that nobody understands quantum mechanics.”

Richard Feynman

(Physik-Nobelpreis 1965 für eine der Formulierungen der Quantenmechanik)

Isaac Newton

(1643–1727)

Ludwig Boltzmann

(1844–1906)

Albert Einstein

(1879–1955)

Niels Bohr

(1885–1962)

Erwin Schrödinger

(1887–1961)

Werner Heisenberg

(1901–1976)

Kontinuität

Newtonsche und Maxwellsche Gesetze

Definitive Zustände

Determinismus

„Makro-Welt“

Quantisierung

Schrödinger-Gleichung

Superposition &Verschränkung

Zufall

„Mikro-Welt“

Klassische Physik Quantenphysik

Zwei verschiedene Welten

Klassische Physik Quantenphysik

Physik und Technik

(ca. 30% des BIP der USA)

Das Doppelspalt-Experiment

Quelle: http://www.blacklightpower.com/theory/DoubleSlit.shtml

Teilchen Wellen Quanten

Interpretation bisheute strittig

Quanten-Superposition

Materie-Teilchen: Elektronen, Atome, Moleküle

Licht-Teilchen: Photonen

Superposition (Überlagerung):

| = |linker Spalt + |rechter Spalt

Quanten-Verschränkung

Verschränkung (Mehrteilcheneigenschaft):

|AB = |AB + |AB

NichtlinearerKristall

Vertikal polarisiert

Horizontal polarisiert

UV-Laser

AABB

= |AB + | AB

Superposition: | = | + |

Polarisation: horizontal, vertikalE

BobAlice

lokal: zufällig

/: /: /: /: /: /: /: /:

/: /: /: /: /: /: /: /: global: perfekte Korrelation

„Entanglement“

Erwin Schrödinger

“Total knowledge of a composite system does not necessarily include maximal knowledge of all its parts, not even when these are fully separated from each other and at the moment are not influencing each other at all.” (1935)

Lokaler Realismus

Realismus: Objekte haben ihre Eigenschaften unabhängig von der Messung

Lokalität: Messungen an einem Ort beeinflussen nicht die (gleichzeitigen) Messungen an einem anderen

Alice und Bob sind in zwei entfernten Laboratorien, bekommen Teilchen (zB. Würfel) und messen jeweils eine von zwei Größen (zB. Farbe und Parität)

Messung 1: Farbe Resultat: A1 (Alice), B1 (Bob)Messung 2: Parität Resultat: A2 (Alice), B2 (Bob)

Mögliche Werte: +1 (gerade bzw. rot)–1 (ungerade bzw. schwarz)

A1 (B1 + B2) + A2 (B1 – B2) = ±2

A1B1 + A1B2 + A2B1 – A2B2 ≤ 2

A1B1 + A1B2 + A2B1 – A2B2 = ±2

für alle lokal realistischen (= klassischen) Theorien

Alice

Bob

Die Bellsche Ungleichung

John S. Bell

A1B1 + A1B2 + A2B1 – A2B2 ≤ 2

Mit dem Quantenzustand

|AB = |AB + |AB

kann die linke Seite der Bellschen Ungleichung (1964)

Fazit:

Quantenmechanisch verschränkte Zustände verletzen die Bellsche Ungleichung und können daher nicht durch lokalen Realismus (dh. klassische Physik) beschrieben werden (Albert Einstein: „Spooky action at a distance“)

Experimentell hundertfach bestätigt (Photonen, Atome etc).

gleich 22 2,83 werden. Damit: 2,83 ≤ 2.

A1

A2

B1

B2

Kryptographie

Klartext Verschlüsselung Geheimtext Entschlüsselung Klartext

Symmetrische Verschlüsselungsverfahren

Asymmetrische („public key“) Verfahren: zB. RSA

Beispiele aus der Antike

Geheimtext: „ohhoq hcrom“

Klartext: „attac today“

Caesar-Verfahren(ca. 50 v. Chr.)

Skytale(ca. 500 v. Chr.)

Ältestes militärisches Verschlüsselungsverfahren

Schlüssel: Stabdurchmesser

Neuzeit

One-Time-Pad

Idee von Gilbert Vernam (1917)

Beweis der Sicherheit durch Claude Shannon (1949) [einziges Verfahren]

Kriterien:

- zufälliger und geheimer Schlüssel

- (mindestens) gleiche Länge wie der Klartext

- nur einmal verwenden („one time“)

Quantenmechanik kann das leisten:

Quantum Key Distribution (QKD)

Idee: Wiesner 1969 & Bennett et al. 1984 (BB84), erstes Experiment 1991

Mit Verschränkung: Idee: Ekert 1991, erstes Experiment 2000

Gilbert Vernam Claude Shannon

Quantum Key Distribution (QKD)

0

0 0

1111

0

Messbasis: / / / / / / / …

Resultat: 0 1 1 0 1 0 1 …

Messbasis: / / / / / / / …

Resultat: 0 0 1 0 1 0 0 …

- Alice and Bob teilen sich Wahl der Messbasis mit (nicht die Resultate)

- bei gleicher Basiswahl verwenden sie das (lokal zufällige) Resultat

- der Rest wird verworfen

- perfekte Korrelation ergibt den Schlüssel: 0110…

- zwischendurch wählen sie weitere Messbasen und verletzen damit die Bell-Ungleichung

- jedwedes Abhören würde detektiert werden

- Sicherheit garantiert durch Quantenphysik

Quantenkryptographie

O rig ina l:

X O R X O RB itw eises B itw e ises

Versch lüsse lt:

A licesS chlüsse l

B obsS chlüsse l

E ntsch lüsse lt:

S chlüsse l: 51840 B it, B it Fehler W ahrsch. 0 .4 %

Erste Quantenkryptographie mit verschränkten Photonen (Wien, 2000)

Schlüssellänge: 51840 bitBit-Fehlerwahrscheinlichkeit: 0,4%

T. Jennewein et al., PRL 84, 4729 (2000)

8 km „free space“ über Wien (2005)

K. Resch et al., Opt. Express 13, 202 (2005)

Millennium Tower Twin Tower

Kuffner Sternwarte

144 km von Insel zu Insel (2007)

T. Schmitt-Manderbach et al., PRL 98, 010504 (2007)QKD mit 2,3 bit/s

Wien – St. Pölten (2008)

http://www.secoqc.net/index.html

Erstes Quantenkryptographie-Netzwerk: 2008

41 Partner aus 12 Ländern6 Knoten, 8 Links (davon einer free-space)80 km, Rate:einige kbit/s

Tokio-QKD-Netzwerk (2010)

http://www.uqcc2010.org/highlights/index.html

Partners:

Japan: NEC, Mitsubishi Electric, NTT NICTEurope: Toshiba Research Europe Ltd. (UK), ID Quantique (Switzerland) and “All Vienna” (Austria).

Toshiba-Link (BB84): 300 kbit/s über 45 km

QKD-Zeitlinie

1984Idee (BB84)

1991Erstes Experiment BB84

2000Erstes Experimentmit Verschränkung

2010Tokio-Netzwerk

O rig ina l:

X O R X O RB itw e ises B itw e ises

Versch lüsse lt:

A licesS ch lüsse l

B obsS chlüsse l

E ntsch lüsse lt:

Schlüsse l: 51840 B it, B it Fehler W ahrsch. 0 .4 %

2004Kommerzielles

Produkt

Von der Idee zur Anwendung

2008Wien-Netzwerk

VorschlagVerschränkung

2004: QKD-Banküberweisung vom Wiener Rathaus zu einer Bank-Austria-Filiale (1,5 km)2007: QKD-Übertragung der Parlamentswahlresultate des Kantons Genf nach Bern (100 km)

China-Netzwerk

Zukunftsmusik

“Our two greatest problems are gravity and paper work. We can lick gravity, but sometimes the paperwork is overwhelming.” – Wernher von Braun (1958)

ISS (350 km Höhe)

Das Moorsche Gesetz (1965)

Gordon Moore © Kurzweil Technologies

Transistorgröße

2000 200 nm2010 20 nm2020 2 nm (?)

Computer und Quantenmechanik

David Deutsch

1985: Formulierung des Konzepts einer Quanten-Turingmaschine

Richard Feynman

1981: Die Natur kann am besten durch Quantenmechanik simuliert werden

Bit vs. Quantenbit

Bit Qubit

1

0

|Q = (|0 + |1)2

1

„0“ oder „1“ „0“ und „1“

Klassischer Computer

Logische Gatter Schaltungen

Qubits

Allgemeiner Zustand eines Qubits:

Physikalische Realisierungen:

Photonen-Polarisation: |0 = | |1 = |

Elektronen/Atom/Kern-Spin: |0 = |up |1 = |down

Atom-Energie-Niveaus: |0 = |ground |1 = |excited

Supraleitung-Fluss-Qubit: |0 = |left |1 = |right

etc…

P(„0“) = cos2/2

P(„1“) = sin2/2

… Phase (Interferenz)

| = |0 + |1|R = |0 + i |1

Bloch-Kugel:

Quantengatter

Quantengatter sind Operationen auf Qubits

werden benutzt um Algorithmen auf Quantencomputern zu implementieren

darstellbar als unitäre n x n Matrizen wobei n = 2Anzahl der Qubits auf Qubitzustände (Vektoren: |0 = (1,0)T, |1 = (0,1)T)

H |0 (|0 + |1)H |1 (|0 – |1) erzeugt Superposition

X (a|0 + b|1) = a|1 + b|0 NOT-Operation

allgemein für 1 Qubit:Rotationen auf der Bloch-Kugel

2-Qubit-Quantengatter

2 Qubits: 4 x 4 Matrizen

Basis-Operation: CNOT

CNOT |c|t = |c|tc

|0A

|0B

H

|0A|0B

(|0A+|1A) |0B = |0A|0B + |1A|0B

|0A|0B + |1A|1B erzeugt Verschränkung!

Ein kleiner Schaltkreis:

Quantencomputer

Klassischer Input 01101… Präparation Messung

KlassischerOutput

00110…

Evolution

Input und Output der Rechnung sind klassisch.

Die Informationsverarbeitung ist quantenmechanisch.

Deutsch-Algorithmus

erster Quantenalgorithmus, 1985 durch David Deutsch

gegeben eine „bit to bit“ Funktion f: {0,1} {0,1}

Aufgabe: ist die Funktion konstant, dh. f(0) = f(1)

oder balanciert, dh. f(0) f(1)

klassisch: man muss sowohl f(0) als auch f(1) auswerten: 2 Aufrufe

quantenmechanisch reicht ein einziger Aufruf!

die Funktion f wird auf eine Superposition angewandt

„Quantenparallelismus“ (many worlds)

Verallgemeinerung: Deutsch-Josza (1992)

„n bits to one bit“ f: {0,1}n {0,1}

klassisch: worst case 2n-1+1 Aufrufe

Quantencomputer: 1 Aufruf

(„exponential speed-up“)n = 1: Deutsch-Algorithmusn > 1: Deutsch-Josza-Algorithmus

Shor-Algorithmus

1994 durch Peter Shor

Aufgabe: Primfaktor-Zerlegung einer b-Bit Zahl (RSA-Krypographie)

541 1987 = ? (einfach)

1074967 = ? ? (schwer)

klassisch: super-polynomial: , bisheriges Optimum

quantenm.: sub-polynomial: O(b3), probabilistisch

für b = 1000 (301-stellig) bei THz-Geschwindigkeit:

klassisch quantenmechanisch

1024 Schritte 1010 Schritte

100000 Jahre < 1 Sekunde

L. M. K. Vandersypen et al., Nature 414, 883 (2001)

Grover-Algorithmus

1996 durch Lov Grover

Aufgabe: Datenbank-Suche in einer unsortierten Datenbank mit N Elementen (zB. eine markierte Seite in einem Buch finden)

klassisch: O(N), man muss im Schnitt das halbe Buch durchblättern

quantenm.: O(N), „quadratic speed-up“ (probabilistisch)

|00 |01 |11|10

Input

|00 |01 |11

|10

Markierung

|00 |01 |11|10

Inversion um Mittelwert

Implementierungen

NMR (nuclear magnetic resonance) Quantum Computation

Ensemble von organischen Molekülen in einem Kryostaten (Flüssigkeit)

Qubits: Kernspin-Zustände (der C-Atome)

Gatter: Radiopulse

7-Qubit-Quantencomputer faktorisiert 15 in 35 (IBM 2001)

Probleme: Kurzlebigkeit (Dekohärenz), keine Adressierbarkeit einzelner Moleküle, keine Speicherung von Information

Alanin-Molekül

Implementierungen

Trapped Ion Quantum Computation

Elektrisch gefangene Ionen

Qubits: Elektronen-Energieniveaus

Gatter: Manipulation durch Laserlicht

14 verschränkte Kalzium-Ionen(IQOQI Innsbruck 2011)

Probleme: Skalierbarkeit (ein-dimensional), aufwändig (Vakuumkammer etc.), langsame Gates (Millisekunden)

Vorteile: präzise Kontrolle, individuelle Adressierbarkeit, Informationsspeicherung (Millisekunden)

Ziel: zweidimensionale Arrays von Ionen („trapped ions on a microchip“)

Ionenfalle

http://www.uibk.ac.at/th-physik/qo/research

Fluoreszenz-Signal

Implementierungen

Optical Quantum Computation

Photonen

Qubits: Polarisation (oder Pfad)

Gatter: Strahlteiler, Wellenplatten

Grover-Suche für N = 4 (Wien 2007)

Probleme: Skalierbarkeit (Detektoren), Information kann schwer gespeichert werden

Vorteile: schnell (Nanosekunden-Gates) gut geeignet für Kommunikation zwischen Quantencomputern oder Subsystemen eines Quantencomputers (Hybridsysteme)

Optischer Tisch

Implementierungen

SQUIDs (superconducting quantum interference devices)

Supraleitende Ringe mit Josephson-Kontakt (Festkörper)

Fluss-Qubit (wie Spin)

Gatter: Änderung der Kopplung durch magnetische Felder

Verschränkung zwischen 4 SQUIDs

Probleme: Dekohärenz (Mikrosekunden)

Vorteile: schnelle Operation, Skalierbarkeit gut (SQUID-Arrays), Mikrofabrikation etabliert

SQUID

M. W. Johnson et al., Nature 473, 194 (2011)

Implementierungen

Andere Festkörper-Möglichkeiten

NV-Zentren

Quantenpunkte

Spintronik

Ausblick

Quantenkryptographie und Quantencomputer demnächst in Ihrem Laptop?

– Ich denke nein. Aber:

– Quantenkryptographie: denkbar: Banken, Ämter, Militär etc.physikalische Implementierung: sicher Photonen

– Quantencomputer: vielleicht in ein bis drei Jahrzehnten: Forschung, Militär etc.physikalische Implementierung: noch unentschieden (vermutlich Festkörper)Problem: wenige Algorithmen

„Das Telefon hat zu viele ernsthaft zu bedenkende Mängel für ein Kommunikationsmittel. Das Gerät ist von Natur aus von keinem Wert für uns.“

– Western Union Financial Services (1876)

„When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.“

– Arthur C. Clarke (1962)

Die Wiener Quantengruppe

Herzlichen Dank für Ihre Aufmerksamkeit!

Backup-Folien:

BB84

Teleportation

12 3

AnfangszustandEPR Quelle

Verschränktes Paar

Alice Bob

klassischer Kanal

Teleportierter Zustand

4