Date post: | 28-Aug-2018 |
Category: |
Documents |
Upload: | nguyencong |
View: | 213 times |
Download: | 0 times |
Quantengatter und Quantenschaltkreise Seite 1/16
UNKONVENTIONELLE COMPUTER
Seminar SS2001 Vortrag von Jan Rödling
Technische Universität Braunschweig
4XDQWHQJDWWHU�XQG�4XDQWHQVFKDOWNUHLVH�
��������� � �
Das Modell
Quantengatter
Quantenschaltkreis
Quantenmessungen
Universelle Quantengatter
Quantengatter und Quantenschaltkreise Seite 2/16
Das Modell :
Das Modell eines Quantencomputers beruht auf einem geschlossenen
quantenmechanischen System.
Die Register eines konventionellen Computers entsprechen in diesem Modell den
Qubitregistern, welche als Einheitsvektoren im k
C 2interpretiert werden.
Die auf diesen Qubitregistern durchgeführten Operationen werden durch unitäre
Operationen realisiert, d.h., sie sind in jedem Falle reversibel.
Wir betrachten hier nur die theoretischen und mathematischen Prinzipien, nach
denen die Quantencomputer arbeiten, ohne auf die physikalischen Vorgänge
einzugehen.
Quantengatter
Definition: Ein Quantengatter besitzt n Eingänge und
n Ausgänge (mit n = 1, 2, 3, ... ) und wird durch eine unitäre Matrix
(unitärer Operator) vom Grad 2n dargestellt.
Entstehung der Indizes
11100100
11011000
1010
11100100
1111
11
0000
00
aaaa
aaaaaaaa
aaaa
+++=
+++=
+⊗+=⊗Ψ
ΨΨΨΨ
ΨΨ
ϕϕϕϕ
ϕϕϕ
=
44434241
34333231
24232221
14131211
uuuu
uuuu
uuuu
uuuu
U
Quantengatter und Quantenschaltkreise Seite 3/16
Das Tensorprodukt:
Das Tensorprodukt wird bei den Operationen auf Quantengattern zwischen
unabhängigen Qubits bzw. Teilschaltkreisen verwendet. Dabei werden Vektoren und
Matrizen gleichermaßen behandelt:
Jeweils paarweise werden die einzelnen Elemente der Vektoren und Matrizen
miteinander multipliziert.
Vektoren:
10
10
dc
ba
+=
+=
ϕ
φ
Tensorprodukt der Vektoren :
=
⊗
=⊗
bd
bcadac
dc
ba
ϕφ
Tensorprodukt der Matrizen:
=⊗
=
=
dBcBbBaB
BAhgfe
Bdcba
A
Formale Definition:
)()(:
:,,,
φϕφϕ
φϕ
⊗⊗=⊗
∈∈∈∈ ××
BABA
dannCCCBCA nmnnmm
Quantengatter und Quantenschaltkreise Seite 4/16
Darstellungen der Gatter:
z.B. : das Toffoligatter
Die Qubits a, b, c sind unabhängig und werden durch das Tensorprodukt miteinander
verknüpft. Der Punkt an den sich kreuzenden Leitungen bedeutet, daß die jeweiligen Qubits
eine Kontrollfunktion erfüllen, aber selbst nicht verändert werden.
Das Symbol am Kreuzungspunkt vom Qubit c entspricht dem des klassischen XOR-Symbols.
Da in Quantencomputern nur reversible Funktionen berechnet werden können, ist immer
mindestens ein Kontrollqubit notwendig. Im obigen Beispiel heißt das, daß Qubit c genau
dann invertiert wird, wenn die (Kontroll-)Qubits a und b den Wert 1 annehmen.
Unitäre Matrix :
==
0100000010000000001000000001000000001000000001000000001000000001
CCNOTTOFFOLI
011011
010010
001001
000000
→
→
→
→
110111
111110
101101
100100
→
→
→
→
Quantengatter und Quantenschaltkreise Seite 5/16
Beispiel:
Die Hadamard - Transformation versetzt ein Qubit in einen Zustand, der sich genau
„zwischen“ den zwei Basiszuständen eines Qubits befindet.
Hadamard auf ein Qubit :
−
=11
11
21
H
Im folgenden Beispiel werden 2 Qubits einer unitären Operation unterworfen. Das
obere Qubit erfüllt eine Kontrollfunktion, d.h., das untere Qubit wird genau dann in
den überlagerten Zustand versetzt, wenn das Kontrollqubit im Zustand „1“ ist.
controlled-Hadamard (2 Qubits) :
−
=
21
21
00
21
21
00
00100001
cH
Quantengatter und Quantenschaltkreise Seite 6/16
Quantenschaltkreise
Ein Quantenschaltkreis besteht aus verschiedenen Quantengattern, die durch
Quantenleitungen miteinander verbunden sind.
Dabei sind Quantenleitungen und –gatter nur abstrakte Modelle. Die Leitungen
stellen einen zeitlichen Ablauf dar, während die Gatter die Zustandsänderungen
repräsentieren.
Rechenregeln in Quantengattern und -schaltkreisen:
22121 ,mit MatUUUU ∈⊗
42112 ,mit MatUUUU ∈
z.B.:
trixEinheitsmaCICUCUistdabei
IUUU
CBAABC
xxx 22882
441
12
,,
)(
∈∈∈
⊗=
⊗⊗==
ϕϕ
ϕ
Quantengatter und Quantenschaltkreise Seite 7/16
Regeln für Quantenschaltkreise :
Es gelten drei wichtige Regeln in Quantengattern und –schaltkreisen :
1) Es sind nur nichtzyklische Schaltkreise erlaubt. Das bedeutet, daß Ausgänge
eines Gatters (Schaltkreises) nicht wieder mit bereits benutzten Eingängen
verbunden werden können. Es können also keine Schleifen realisiert werden.
Soll ein Gatter mehrmals durchlaufen werden, so muß eine entsprechende
Anzahl dieses Gatters hintereinander geschaltet werden.
2) Im Gegensatz zu klassischen Gattern ist es wegen der Reversibilität nicht
möglich, mehrere Eingänge zu einem Eingang zusammenzuschalten.
KEIN FANIN
3) Es ist ebenfalls nicht möglich, eine Quantenleitung in zwei oder mehrere
identische Quantenleitungen aufzuteilen.
KEIN FANOUT
Dies wird im folgenden NO-CLONING-THEOREM bewiesen :
Quantengatter und Quantenschaltkreise Seite 8/16
NO-CLONING-Theorem:
Es gibt keine unitäre Operation, mit der Qubits kopiert werden können !
Annahme: Es existiert ein unitärer Operator U , welcher beliebige Zustände
kopieren kann, also ϕϕϕ ,0, =U für alle Zustände ϕ erfüllt.
Zwei beliebige verschiedene orthogonale Basiszustände βα ,
können folgendermaßen kopiert werden :
βββββ
ααααα
⊗==
⊗==
,)0,(
und ,)0,(
U
U
Weiterhin sei γ ein speziell gewählter Zustand :
( )βαγ +=2
1:
Dann ist:
( ) 2
1)00U(
2
1)0( ββααβαγ +=+=U
Andererseits gilt:
( ) 21
)(2
1)(
2
1 ββαββαααβαβαγγ +++=+⊗+=
Offensichtlich gilt also :
γγγ ≠ )0(U , was im Widerspruch zur Annahme steht.
Man sieht, dass das Kopieren eines beliebigen Qubits nicht möglich ist. Daher ist das
"Vervielfältigen" von Qubits nicht realisierbar.
Quantengatter und Quantenschaltkreise Seite 9/16
Quantenprogramm
Um mit einem Quantenrechner Ergebnisse erzielen zu können, muß ein
Quantenprogramm realisiert werden. Ein solches besteht aus einem
Quantenschaltkreis und einer oder mehrerer abschließender Messungen der
Zustände des Quantensystems.
Ein Quantenprogramm realisiert eine probabilistische Quantenturingmaschine. Alle
Ergebnisse der Messungen sind in geeigneter Form als Wahrscheinlichkeiten
interpretierbar. Gegebenenfalls muß das Quantenprogramm mehrfach ausgeführt
werden, um die Ergebnisse zu verifizieren.
Trotzdem liefern Quantenrechner bei Anwendung geeigneter Algorithmen sehr viel
schneller Ergebnisse als herkömmliche Computer.
Quantengatter und Quantenschaltkreise Seite 10/16
Quantenmessungen
Messungen beschreiben wir durch Projektionen des Zustands auf geeignete
Unterräume des Quantenregisters n
C 2 . Bis zur Messung ist der Zustand eines
Systems unbestimmt. Als Ergebnis einer Quantenrechnung haben wir einen noch
unbestimmten Zustand (blauer Pfeil) erhalten. Eine Messung in eine beliebige
Richtung (gestrichelte Linie) verändert den Systemzustand irreversibel in
Messrichtung (roter Pfeil)!
Die Koeffizienten des (herunter-)projezierten Zustands ergeben eine als
Wahrscheinlichkeit interpretierbare Größe.
Beispiel 1 : (unbestimmter Zustand) :
12
10
21 +=φ
Die Koeffizienten der Basisvektoren sind in geeigneter Form wegen 122 =+ βα als
Wahrscheinlichkeiten interpretierbar . Im obigen Beispiel erhält man durch eine
Messung mit einer Wahrscheinlichkeit von p = 0,5 eine klassische „0“.
Der Zustand ist nach der Messung in Messrichtung festgelegt: 0=φ .
Bei einer erneuten Messung in die eben benutzte Messrichtung würde man mit
100%-iger Wahscheinlichkeit eine klassische „0“ erhalten.
Das Messen eines 2-Bit-Zustandes ijij∑= αφ ergibt 2 Bits ij mit der
Wahrscheinlichkeit 2
ijα und zwingt φ in den Zustand ij .
Quantengatter und Quantenschaltkreise Seite 11/16
Beispiel 2:
11100100 11100100 aaaa +++=φ
Das Ergebnis “01” wird mit einer Wahrscheinlichkeit 2
01a erzielt.
Nach der Messung in Richtung 'φ ist der Zustand des 2-Qubit-Systems im
Meßrichtung festgelegt und wird wieder auf einen Einheitsvektor normiert.
)1'(01
'01
01 == φα
φa
Beispiel 3:
Zustand des Systems vor Messung sieht wieder wie folgt aus :
11100100 11100100 aaaa +++=φ
Das erste Qubit ist mit Wahrscheinlichkeit 2
012
00 aa + im Zustand „0“. Die
Messung führt zu der Änderung des Gesamtzustandes φ nach :
201
200
0100 0100'
aa
aa
+
+=φ
Auch hier wurde der Bildvektor auf einen Einheitsvektor normiert .
Quantengatter und Quantenschaltkreise Seite 12/16
Vorgehensweise der Zustandsmessung:
Wir können uns auf folgenden Standpunkt stellen :
Wenn ϕ z.B. in der Form
111110101100011010001000 111110101100011010001000 ααααααααϕ +++++++=
vorliegt, dann existiert eine Meßvorschrift, die den Zustand „101“ mit der
Wahrscheinlichkeit p=2
101α liefert.
Durch geeignete Algorithmen können durch Interferenz einzelner Amplituden
(=Faktoren der Basisvektoren) die Wahrscheinlichkeiten einzelner Basiszustände
beeinflusst werden.
Die zugehoerige Messung koennen wir uns wie folgt vorstellen:
Die Messapparate � erzeugen eine klassische Anzeige aus {0,1} für jeweils eine
Quantenleitung (entspricht einem Qubit).
Quantengatter und Quantenschaltkreise Seite 13/16
Universelle Quantengatter
Klassische (boolesche) Schaltkreise können aus wenigen Grundgattern aufgebaut
werden. So genügt eine geeignete Verschaltung von NAND-Gattern für die
Realisation eines beliebigen Schaltkreises.
Für Quantenschaltkreise sind solche Zerlegungen in universelle Gatter ebenfalls
sinnvoll.
Definition: Eine Menge M von Quantengattern heißt universell, wenn jede
beliebige unitäre Transformation U als Quantenschaltkreis mit
Quantengattern aus M realisiert werden kann.
Die Menge M1 ist universell:
} :{}{ 221 unitäristUCUCNOTM x∈∪=
CNOT ist das Controlled-NOT-Gatter, d.h. das Zielqubit wird genau dann invertiert,
wenn das Kontrollqubit den Wert „1“ hat.
Es gibt überabzählbar viele unitäre C2x2 – Matrizen, daher ist M1 unendlich groß.
Eine Approximation von unitären Abbildungen bzw. Quantenschaltkreisen liefert oft
ausreichende Ergebnisse.
Quantengatter und Quantenschaltkreise Seite 14/16
εε - Approximation von universellen Quantengattern
Motivation : Eine unendliche Zahl von Quantenoperationen soll durch
möglichst wenige Grundgatter realisiert werden.
Die Quantenrechnung ist aufgrund der Messungen immer probabilistisch, d.h., die
Ergebnisse sind nicht mit beliebiger Genauigkeit bestimmbar.
Da effiziente Implementierungen von beliebigen Gattern erwünscht sind, genügt oft
eine entsprechende Approximation durch universelle Quantengatter.
Die Matrix M ist eine Approximation des gesuchten unitären Operators U, wenn gilt :
10 ≤≤≤− εε mitMU
Der Gatteraufwand eines approximierten Schaltkreises kann im günstigsten Fall
polynomial sein, im schlechtesten Fall erhalten wir einen exponentiellen Aufwand.
Der Aufwand ist natürlich abhängig von der gewünschten Genauigkeit ε .
Beispiel einer universellen εε-approximierenden Menge:
0
01 },,{
42
== πi
eWwobeiWHCNOTM
Die Menge M2 wird in der Quanteninformatik häufig verwendet.
Quantengatter und Quantenschaltkreise Seite 15/16
Beispiel eines approximierten Schaltkreises mit M2:
Gesuchte Funktion :
01F ,10 ==F
z.B.:
11
0
0
1
11
11
21
10
01
11
11
21
)0( =
=
−
−
−
=F
φφ FHWH →→→ ......4
Hinweis :
−
=10
014W
Der Aufwand (hier 6 Gatter) ist ziemlich hoch, da die gesuchte Funktion durch ein
einziges Gatter
=
0110
XOR realisiert werden könnte.
Die Approximation eines beliebigen Schaltkreises auf n Qubits mit einer Genauigkeit
ε hat einen Aufwand an Gattern von
)4
log4(2
2
ε
nn n
nO
Es ist also nicht in jedem Fall sinnvoll (s.o.), einen Schaltkreis durch universelle
Quantengatter zu realisieren.
Quantengatter und Quantenschaltkreise Seite 16/16
Literatur JOZEF GRUSKA, Quantum Computing, McGraw-Hill, London, 1999
JOHANNES BLÖMER, Skript zur Vorlesung Quantencomputer, Universität
Paderborn, SS 2000
MICHAEL A. NIELSEN, ISAAC L. CHUANG, Quantum Computation and Quantum
Information, Cambridge University Press, Cambridge, 2000