Upload
aleit-schimming
View
112
Download
2
Embed Size (px)
Citation preview
Quantum Computing
Hartmut KlauckUniversität FrankfurtWS 04/0510.11.
I) BQP vs. PSPACE
BQP: Klasse von Funktionen f:{0,1}*!{0,1}, die durch uniforme Quantenschaltkreise mit Fehler 1/3 berechenbar sind (Gatterfunktionen aus endlicher Menge)
PSPACE: Klasse von Funktionen f:{0,1}*!{0,1}, die durch deterministische Turingmaschinen mit polynomiellem Speicherplatz berechenbar sind
Heute: BQP µ PSPACE BQP PSPACE nicht bekannt, würde
P PSPACE implizieren (schwierig)
I) Simulation in PSPACE
Gegeben ist uniforme Quantenschaltkreisfamilie (d.h. „Bauanleitung“) für Schaltkreise für alle Eingabelängen n2N mit polynomieller Grösse für eine Funktion f
Gesucht ist polynomiell platzbeschränkter Algorithmus für f
Auf Eingabe x2{0,1}n simuliere Schaltkreis und berechne für Ausgaben a Prob(a)= |ha|U|x0i|2
I) Simulation in PSPACE
Idee 1: Stelle Zustand als Vektor da, beschränkte Präzision der Einträge, Matrixmultiplikation
Problem: Zustand ist Vektor mit dim exp(n) ha|U|x0i=ha|UT U1|x0i
= z(1),…,z(T-1) h a | UT | z(T-1)i hz(T-1) |UT-1| z(T-2)i hz(2) |U2 | z(1)i hz(1) |U1 | x0iz(j)2{0,1}n+s
hz(i) |Ut | z(j)i ist ein Eintrag in Ut
[Zeile z(i), Spalte z(j) ]
I) Simulation in PSPACE
Es ist also eine Summe mit 2(n+s)(T-1) Termen zu evaluieren. Jeder Term ist Produkt von T Matrixeinträgen, aus den T Matrizen Ui
Wert jedes Terms mit Präzision 1/(10 ¢ 2(n+s)(T-1)) ausreichend
Term Produkt von T Zahlen, jede mit Präzision 1/(20 ¢ 2(n+s)(T-1)) ausreichend
Runde Matrixeinträge, komplexe Zahlen als Paar reeller Zahlen, O((n+s)T) Bits pro Zahl
I) Simulation in PSPACE
Simulationsalgorithmus: Laufe durch alle z(1),...,z(T-1) Berechne h a | UT | z(T-1)i
hz(T-1) |UT-1| z(T-2)i hz(1) |U1 | x0i
Addiere zu bisher berechnetem Wert Für jeden Matrixeintrag hz(T-1) |UT-1| z(T-2)i benutze
Turingmaschine aus der Uniformitätsbedingung, d.h. in polynomieller Zeit berechenbar
Platz insgesamt: O(T(n+s)) für z(j) und für zu speichernden Wert der Teilsumme, poly(n) zur Berechnung der Matrixeinträge
Zeit insgesamt: exp(T(n+s))
II) Beschränkte Präzision
Schaltkreis berechnet |Ti=UT UT-1 U1 |xi |0…0i
Ui unitäre Transformationen
Angenommen statt UT wird VT angewendet Wegen unpräziser Implementierung Wegen Simulation mit beschränkt
genauer Arithmetik Ergebnis VT|T-1i=|Ti+|ETi, wobei
|ETi=(VT-UT) |T-1i (nicht normiert)
II) Beschränkte Präzision
Ergebnis VT|T-1i=|Ti+|ETi, wobei |ETi=(VT-UT) |T-1i (nicht normiert)
Wenn Vi statt Ui für alle i:
|1i=V1|0i=|1i+|E1i
|2i=V2|1i=|2i+|E2i+V2|E1i
|Ti=VT|T-1i=|Ti +|ETi +VT|ET-1i + + VTV2 |E1i
Daher ist k |Ti |Ti k · i=1…T k |Eii k i=1…T k (Vi-Ui) |i-1i k
II) Approximation von Transformationen Sei U ein beliebiger unitärer Operator auf
n Qubits Gegeben sei ein Operator U‘ Wir sind an der Approximationsqualität
interessiert Spektralnorm kUk=maxx: kxk =1 k U x k Approximationsfehler: k U – U‘ k
II) Approximationsfehler gesamt i=1…T k (Vi-Ui) |i-1i k · i=1…T k (Vi-Ui) k Wenn also der Approximationsfehler pro
Transformation /T ist, dann ist der Abstand zwischen korrektem und erreichtem Zustand
k |Ti |Ti k · , wie gross ist der Fehler der Berechnung?
Messung Standardbasis (n+s Qubits) Messergebnis a mit Wahrscheinlichkeit
P(a)=|h a|Ti|2 bzw. Q(a)=|h a|Ti|2
II) Approximationsfehler gesamt Messergebnis a mit Wahrscheinlichkeit
P(a)=|h a|Ti|2 bzw. Q(a)=|h a|Ti|2
Approximationsfehler fürjede Berechnung höchstens
a|P(a)-Q(a)|· 2 k |Ti |Ti k · 2
II) Fehlertoleranz
Es ist möglich, zu jedem Quantenschaltkreis einen nur wenig grösseren Quantenschaltkreis zu konstruieren, der noch funktioniert, wenn Gatter unabhängig zufällig jeweils mit konstanter Wahrscheinlichkeit ausfallen
Konstruktion verwendet Quantenversion fehlerkorrigierender Codes
III) Schaltkreise mit endlicher Menge von Gatterfunktionen Aus praktischen Gründen wollen wir eine
endliche Menge von Gatterfunktionen Fehlertolerante Schaltkreise nur bei
endlicher Menge von Gatterfunktionen möglich
Definition uniformer Schaltkreisfamilien(damit auch PSPACE Simulation)
III) Resultate zu möglichen Basen CNOT und jedes unitäre Gatter auf 1 Qubit CNOT, Hadamard, einige Rotationsgatter Toffoli Gatter und Hadamard
Für all diese gilt, dass ein Schaltkreis mit beliebigen 2-Qubit Gattern durch einen mit Gattern aus der jeweiligen Basis mit geringem Overhead approximiert werden kann
CNOT und Hadamard reichen nicht!
III) Rotationsgatter
Definieren einige Transformationen auf einem Qubit
Diese + CNOT + Hadamard sind ausreichend
Inwiefern kann ein Qubit rotiert werden?
Qubit: |i = |0i+|1i, |0i ||2+||2=1
Äquivalent: |i=ei [cos(/2) |0i + ei sin(/2) |1i] ei irrelevant, da in keiner Messung feststellbar Also cos(/2) |0i + ei sin(/2) |1i Parameter ,
III) Bloch Sphäre
Winkel x,y Ebene
Winkel z-Achse
III) Rotationsgatter
Qubit cos(/2) |0i + ei sin(/2) |1i
x-Rotation
y-Rotation
z-Rotation
IV) Doch vor der Konstruktion einer universellen Basis
Bomb Testing!
IV) Bomb Testing
[Vaidman] Paket mit oder ohne Bombe Wenn eine Bombe mit nur einem Photon
in Berührung kommt, so detoniert sie Oder ist es doch ein Geschenk?
Klassische Physik: Entweder Hineinschauen oder nicht. Wenn Bombe dann Explosion
IV) Bomb Testing
Quantenphysikalisch „nur ein wenig“ hineinschauen?
Angenommen, folgendes kann getan werden:Es gibt ein Kontrollqubit (hineinschauen oder nicht) und ein Ergebnisqubit (Bombe explodierte oder nicht)
|0i|ai ! |0i|ai immer |1i|ai ! |1i|ai wenn keine Bombe präsent |1i|ai ! |1i|a©1i wenn Bombe präsent
IV) Bomb Testing
Wende Rotation Ry(/N) auf erstes Qubit von |00i an Ergebnis: cos(/(2N)) |00i + sin(/(2N)) |10i Jetzt Test-Transformation Gefolgt von Messung des zweiten Qubits (Explosion
wäre auch nicht zu ignorieren) Keine Bombe:
cos(/(2N)) |00i + sin(/(2N)) |10i Bombe: mit Wahrscheinlichkeit cos2(2/(2N))
Zustand |00i und keine Explosion, mit Wahrscheinlichkeit sin2(/(2N)) Explosion
sin2(/(2N))¼ O(1/N2) Wiederhole N mal Bombe: Wahrscheinlichkeit einer Explosion O(1/N),
sonst Endvektor |00i Keine Bombe: Endvektor |10i
IV) Bomb Testing
R|0i
|0iTest
N mal
CNOT oder ID
IV) Bomb Testing
Experimentell getestet[ohne Bombe!]
III) Simulation beliebiger unitärer Transformationen U auf n Qubits durch Schaltkreis
berechnen Ziel 1: Exakte Berechnung durch CNOT
und beliebige 1-Qubit Gatter
III) Kontrollierte Gatter
Eine unitäre Operation U auf k+d Qubits heisst kontrolliert von den k Qubits, wenn es eine unitäre Operation U‘ auf d Qubits gibt, so dass U definiert ist durch
U|xyi=|xyi, wenn es ein xi 1 gibt
U|1k yi=|1k i U‘ |yi
d Qubits heissen Ziel Qubits k Qubits Kontroll Qubits
III) Erster Schritt
Jede unitäre Transformation U auf m Qubits kann durch einen Schaltkreis aus 22m Gattern exakt simuliert werden, die kontrolliert sind, mit je 1 Ziel Qubit
III) Schritt 2
CNOT, Toffoli und beliebige 1-Qubit Gatter Behauptung: beliebiges kontrolliertes
Gatter mit 1 Ziel Qubit und k Kontroll Qubits kann exakt durch Schaltkreis mit O(k) CNOT, Toffoli und 1-Qubit Gattern simuliert werden
Daher ist Basis CNOT, Toffoli, 1-Qubit Gatter exakt universell (kann jede Operation berechnen)
III) Schritt 3
Simuliere beliebiges 1-Qubit Gatter durch Folge von konstant vielen Rotationen
Exakte Simulation ist unmöglich
III) n-Qubit Operationen
U auf n Qubits, Matrix 2n £ 2n ; 2n=M Behauptung: repräsentierbar als Produkt
von O(M2) Matrizen der Form
1 0 0 0 1 0 0 0 a b 0 0 0 c d 0 0 1 0
01
abcd
unitär
III) n-Qubit Operationen
Zu jedem Einheitsvektor (a,b)T gibt es unitäre Transformation V: V(a,b)T=(1,0)T
Zu jedem Vektor aus CM gibt es M-1 Transformationen der notwendigen Form, die zusammen auf den Vektor (100000000)T abbilden
Multipliziere U-1 von links mit M(M-1) Transformationen, um die Spalten auf die Vektoren der Standardbasis abzubilden, Produkt mit U-1 ist also I, daher ist Produkt der Transformationen U
III) n-Qubit Operationen
Jetzt durch kontrollierte Gatter ersetzen
1 0 0 0 1 0 0 0 a b 0 0 0 c d 0 0 1 0
01
abcd
U, unitär
III) n-Qubit Operationen
Operation bildet Basiszustände |si und |ri nichttrivial ab Schreibe Sequenz von Bitflips, die String s auf r
transformiert 0010111-> 1010111->1110111 -> 1111111 s -> g1 -> g2 -> -> gm-1 -> r Idee: Serie von Transformationen, die |gii mit |gi+1i tauschen und sonst nichts tun bis zu n NOT und CCCCNOT (mehrfach konstrolliertes
NOT) auf gm-1 wende kontrollierte Operation U an, Ziel:
unterschiedliches Bit, Kontrolle: gleiche Bits Vorherige Transformationen wieder umkehren Alle Operationen sind nun kontrollierte Operationen mit
1 Ziel Qubit
III) Schritt 2
Gegeben kontrollierte Operation mit k Kontrollqubits und 1 Zielqubit [Operation U auf einem Qubit]
Benutze klassischen Schaltkreis (reversibel, Toffoli Gatter), der das AND der Kontrollqubits berechnet
Dann durch Ergebnisqubit kontrolliert U auf Zielqubit anwenden
Multiplikation nun wieder invertieren
Jetzt nur noch Toffoli, und kontrollierte 1-Qubit Gatter
Verwendet Hilfsqubits, auch ohne möglich
III) Effizienz
Zerlegung in kontrollierte Gatter: auf n Qubits werden n24n Gatter erzeugt
Zerlegung in Toffoli, CNOT und 1-Qubit Gatter weiteren linearen Faktor
III) CNOT und 1-Qubit Gatter Jedes 1-Qubit Gatter kann durch Folge
von Rotationen dargestellt werden (Bloch Sphäre)
Für jede unitäre Transformation auf 1 Qubit gibt es Rotationen A,B,C, so dass ABC=I eiAXBXC=U
D.H. wenn anstelle X=NOT das CNOT vom Kontrollqubit aus angewendet wird, erhalten wir einen Schaltkreis aus Rotationen und CNOT
III) Bloch Sphäre
Winkel x,y Ebene
Winkel z-Achse
III) CNOT und 1-Qubit Gatter
C B A
D
III) Dekomposition
Später werden nur Hadamard und Rotationen verwendet
Zeigen Dekompositon nur für diese Toffoli durch CNOT, Hadamard und
Rotationen auch darstellbar
III) z-Rotation um
C B A
A: Rz() B: Rz(-/2) C: Rz(-/2)
ABD=I XBXC=XX=I
III) Hadamard
C B A
D
III) Hadamard
ABC=I offensichtlich ei/2 AXBXC = H
Ausmultiplizieren sin(/4)=cos(/4)=1/21/2
Additionstheoreme für sin und cos
III) Approximation 1-Qubit Gatter Approximiere beliebiges U auf 1 Qubit
durch Folge von H und Rz(/4) und Ry(/4) Gattern mit beliebig guter Qualität
U kann immer dargestellt werden als
Jedes U kann als Folge von 3 Rotationen (um z,y,z) dargestellt werden
III) Approximation 1-Qubit Gatter Es ist möglich, jede Rotation durch eine
Folge von Rotationen um /4 darzustellen[mit Fehler]
Idee: Rotation um irrationales Vielfaches von 2 möglich (durch Kobination von Rotation entlang x,z Achse) entlang einer anderen Achse als x,y,z
Vielfache dieses Rotationswinkels “füllen” das Intervall [0,...,2] langsam auf, bilden dann eine dichte Teilmenge des Intervalls
III) Effizienz
Pro 1-Qubit Gatter abhängig von Präzision
Bestes Ergebnis insgesamt:[Solovay, Kitaev] Approximation mit log2(1/) Gattern
Wenn also poly(n) Gatter mit Fehler 1/poly(n) approximiert werden sollen, reicht ein Overhead von log2(n)