Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/0631.10.

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

unbekannt (ist die Eingabe) Zugriff: Lese f(0), Lese f(1)

Entweder f(0)=f(1) oder f(0) f(1) Problem: Entscheide, welcher Fall

Deutschs Problem

Wieviele Fragen müssen gestellt werden? 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 (Frage f(0) mit Ws. p und f(1) mit 1-p)

Quanten Frage: Superposition Notwendig: Frage als unitäre Operation! Definition der Frageoperation:

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

Damit ist Uf auf allen Basiszuständen definiert ) Uf vollständig definiert

Erste Idee: “Parallele” Berechnung Uf: Frage an ein 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 ) Was nun?

Deutschs Algorithmus

Etwas anderer Ansatz 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):

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

DennUf |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

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|0

|1

MessungH

Quantenschaltkreise

Schaltkreise auf n Qubits, unitäre Transformationen als Boxen

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

Quantenalgorithmus : 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

H

Uf

H n|0in

|1i

MessungH n

nn n

Hadamard Transformation

Dabei sind x,z2{0,1}n und x¢z= xizi

x fest, H n |xi=

1/2n/2 (|0i +(-1)x(1) |1i) (|0i +(-1)x(n) |1i)

Uf Gatter/Black Box

Uf |xi|ai=|xi|a © f(x) i für alle x2{0,1}n,a2{0,1}

f:{0,1}n ! {0,1} Uf so vollständig definiert (durch

Linearität) reversibel auf klassischen Eingaben )

unitär © ist XOR Operation: 0©0=0; 0©1=1;

1©1=0

Deutsch Josza Algorithmus

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

Ergebnis:

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

Deutsch Josza

Dann Hadamard Transformation auf n Qubits

Amplitude von |0ni:

f konstant ) § 1 f balanciert) 0

Bemerkungen

Deutsch Josza Problem kann effizient durch randomisierten Algorithmus mit Fehler gelöst werden (später finden wir bessere Beispiele von Quantenalgorithmen)

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

Transformationen), kein Fehler Randomisierte Algorithmen sind ebenfalls

effizient, aber nur mit Fehler

Mehr über Messungen (I)

Etwas lineare Algebra: Vektorraum V (dim d) Unterräume: U µ V und U ist selbst Vektorraum

(dim e < d) Es gibt orthonormale Basis:

v1,...,ve,...,vd, span(v1,...,ve)=U Projektion auf einen Unterraum U: PU = i=1...e | v iih vi |

Beispiel: Projektor P=|v1ih v1|P |v1i = |v1ih v1| v1i = |v1i

P ( |v1i+ |v2i)= |v1i + |v1ih v1| v2i = |v1i

Messungen (II)

A? B iff v?w für alle v2 A, w2 B A © B=V iff A? B und

für alle v2 V: v = u + w,u2A, w2B, kuk,kvk = 1, ||2 + ||2=kvk2

Messungen (III)

Hilbertraum V, dim k Observable:

System l · k Unterräume S0,...,Sl-1, paarweise orthogonal

S0© © Sl-1 = V Ws des Messergebnisses i ist

k Proj(Si) |i k2

Zustand |i kollabiert zu Proj(Si) |i / kProj(Si) |ik(renormalisiert)

Observable entspricht einem Messinstrument

Messungen

Hilbertraum: Register Vektoren: Zustände Unitäre Transformation: Evolution der

Zustände/Berechnung Observable: Messinstrument Wahrscheinlichkeitsverteilung auf

Unterräumen/Index der Unterräume: (probabilistisches) Messergebnis

Projizierter und normalisierter Vektor: verbleibender Zustand

Messergebnisse sind die einzige Möglichkeit, klassische Information aus der Berechnung zu erhalten!

Messungen: Beispiel

Zwei Qubits C4

Observable: S0=span(|00i,|01i)S1=span(|10i,|11i)S0 ? S1

Observable entspricht Messung des ersten Qubits

Messung EPR-Paar

Zustand 1/21/2 ¢ (|00i+|11i) Messe erstes Qubit Resultat:

Wenn 0 gemessen wird, kollabiert Zustand zu |00iWenn 1 gemessen wird |11i

Jeder Fall mit Ws. ½ Kollaps von Qubit 2 instantan nach Messung Qubit

1 Sind die Qubits räumlich getrennt, dann verhalten

sich Messergebnisse trotzdem wie perfekt korrelierte Münzwürfe