Simulatietechnieken voor kwantumcomputers
Dirk Nuyens
Academiejaar 2001-2002 versie: 21 mei 2002
Voorwoord There are plenty plenty of worlds to choose from an anonymous photon Deze thesis is tot stand gekomen door een volledig jaar exploratie in het onderzoeksdomein van kwantumtheorie en kwantumcomputers. Het was niet makkelijk om volledig vanaf nul te beginnen. Mijn interesse voor kwantumcomputers is ontstaan op Osdem 2001, waar Prof. Dr. Bruno Marchal van de ULB een inleidende voordracht gaf. Het is niet moeilijk om in de populaire media nu en dan een artikel over kwantumcomputers mee te pikken en het zal iedereen telkens wel verwonderen over wat voor fantastische eigenschappen de betreffende journalist het weer heeft. Kwantumcomputers zouden vele malen krachtiger zijn dan klassieke computers. Ze zouden de huidige populaire vormen van encryptie met gemak kunnen kraken. Met behulp van kwantumtechnologie is het mogelijk om deeltjes te teleporteren. Enzovoorts... Een interessant onderwerp om een thesis over te maken, toch? Heel veel tijd is er gekropen in het zoeken en begrijpen van (goede) publicaties uit het vakgebied. Nog veel meer tijd in het ontrafelen van de soms tegenstrijdige en onvolledige informatie. Het heeft dan ook lang geduurd voordat ik me een conceptueel beeld kon vormen van hoe een kwantumcomputer juist werkt. Toen de belangrijkste puzzelstukjes in december eindelijk op hun plaats gevallen waren, bleken de basisingredi¨enten voor een simulator helemaal niet zo moeilijk te zijn. Het was nu enkel nog een kwestie van de simulator te optimaliseren? Uiteindelijk heb ik enkele simulatiealgoritmen ontworpen en getest en heb ik de exponenti¨ele complexiteit aan den lijve ondervonden. Mijn poging om simulatietechnieken, -algoritmen en optimalisaties te beschrijven is verre van volledig, maar voorlopig nog wel uniek – al worden er meer vragen gesteld dan beantwoord omdat de kennis van de wetenschap voor bepaalde kwantumfenomenen nog te beperkt is. Ik wil voornamelijk Prof. Dr. ir. Ronald Cools bedanken dat hij deze uitdaging samen met mij wou aangaan en bereid was te luisteren naar mijn waarschijnlijk weinig samenhangende uiteenzettingen over mijn ‘ontdekkingen’ in de kwantumwereld. Ook Dr. ir. Koenraad Audenaert ben ik dankbaar voor het verduidelijken van enkele moeilijke punten rond verstrengeling. Verder wil ik ook mijn vriendin, zus en ouders bedanken voor de steun en het proberen lezen van deze tekst. Dirk Mei 2002
Inhoudsopgave I
Kwantumcomputers
1
1 Inleiding tot kwantumtheorie
2
1.1
Enkele belangrijke begrippen . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2
De kwantumbit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2.1
Een kwantummechanische informatie-eenheid . . . . . . . . . . . . . .
4
1.2.2
Superpositie van toestanden . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.3
Observatie van een kwantumbit . . . . . . . . . . . . . . . . . . . . . .
6
De postulaten van de kwantummechanica . . . . . . . . . . . . . . . . . . . .
7
1.3.1
Toestandsbeschrijving en -evolutie . . . . . . . . . . . . . . . . . . . .
7
1.3.2
Observatie van een kwantumtoestand
. . . . . . . . . . . . . . . . . .
8
1.3.3
Waarneembare toestanden . . . . . . . . . . . . . . . . . . . . . . . . .
8
Een kwantumregister . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.4.1
Meerdere kwantumbits . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.4.2
Superpositie in een register . . . . . . . . . . . . . . . . . . . . . . . .
10
1.4.3
Verstrengeling van toestanden . . . . . . . . . . . . . . . . . . . . . . .
11
1.4.4
Observatie van een kwantumregister . . . . . . . . . . . . . . . . . . .
13
Meerdere werelden interpretatie . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.5.1
De kat van Schr¨odinger . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.5.2
Alternatieve interpretaties . . . . . . . . . . . . . . . . . . . . . . . . .
17
1.3
1.4
1.5
2 Kwantumtoestanden 2.1
19
De amplitudevoorstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
2.1.1
De berekeningsbasis van een kwantumregister . . . . . . . . . . . . . .
20
2.1.2
Alternatieve basissen . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.1.3
Mogelijke configuraties van een toestandsvector . . . . . . . . . . . . .
21
i
2.1.4 2.2
2.3
Alternatieve voorstellingswijzen voor een kwantumtoestand . . . . . .
22
Pure en gemengde toestanden . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.2.1
De densiteitsmatrix
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.2.2
Observatie van een pure toestand . . . . . . . . . . . . . . . . . . . . .
23
2.2.3
Gemengde toestanden . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.2.4
De kat van Schr¨odinger herbekeken . . . . . . . . . . . . . . . . . . . .
27
2.2.5
Gereduceerde densiteitsmatrices
. . . . . . . . . . . . . . . . . . . . .
28
Verstrengeling van toestanden . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.3.1
Algemene vereisten voor het ‘meten’ van verstrengeling . . . . . . . .
30
2.3.2
Verstrengeling bij pure toestanden . . . . . . . . . . . . . . . . . . . .
31
2.3.3
Verstrengelingsmaten voor gemengde toestanden . . . . . . . . . . . .
34
3 Berekeningsmodellen 3.1
3.2
3.3
37
Berekeningsmodellen en kwantumcomputermodellen . . . . . . . . . . . . . .
37
3.1.1
Een kwantum-Turing-machine . . . . . . . . . . . . . . . . . . . . . . .
37
3.1.2
Kwantumcircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
De Church-Turing-hypothese . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.1
De klassieke hypothese . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.2.2
De interpretatie van Deutsch . . . . . . . . . . . . . . . . . . . . . . .
41
Berekeningscomplexiteit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.3.1
Klassieke complexiteitsklassen . . . . . . . . . . . . . . . . . . . . . . .
41
3.3.2
Kwantumcomplexiteitsklassen . . . . . . . . . . . . . . . . . . . . . . .
43
4 Kwantumpoorten 4.1
4.2
45
Eigenschappen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.1.1
De evolutie-operator . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.1.2
Unitair
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.1.3
Omkeerbaar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.1.4
Gevolgen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.1.5
Definitie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.1.6
1-bit, 2-bit, 3-bit, ... . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
Enkele elementaire kwantumpoorten . . . . . . . . . . . . . . . . . . . . . . .
49
4.2.1
49
De Hadamard-poort . . . . . . . . . . . . . . . . . . . . . . . . . . . .
ii
4.3
4.2.2
De not-poort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.2.3
De wortel-van-not-poort . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.2.4
De cnot-poort – een conditionele poort . . . . . . . . . . . . . . . . . .
51
4.2.5
De swap-poort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.2.6
De Toffoli-poort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.2.7
Een universele set van kwantumpoorten . . . . . . . . . . . . . . . . .
52
Klassieke poorten en willekeurige functies . . . . . . . . . . . . . . . . . . . .
53
4.3.1
Omkeerbaar maken van een klassieke poort . . . . . . . . . . . . . . .
53
4.3.2
Klad-qubits en het herstellen van qubits . . . . . . . . . . . . . . . . .
53
5 Kwantumcircuits & kwantumcomputers
II
58
5.1
Een voorbeeldcircuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5.2
Voorstelling van kwantumpoorten in een circuit . . . . . . . . . . . . . . . . .
59
5.3
Universele sets van kwantumpoorten . . . . . . . . . . . . . . . . . . . . . . .
60
5.3.1
Algemene eigenschappen van unitaire matrices . . . . . . . . . . . . .
60
5.3.2
De universele set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.3.3
Benaderingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.3.4
Enkele voorbeelden van universele sets . . . . . . . . . . . . . . . . . .
62
5.4
Toepassen van een 1-bit kwantumpoort . . . . . . . . . . . . . . . . . . . . .
66
5.5
Toepassen van een ∧1 (V(1) )-poort . . . . . . . . . . . . . . . . . . . . . . . . .
67
5.6
Kwantumcomputers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
5.6.1
Een kwantummodule – het QRAM-model . . . . . . . . . . . . . . . .
70
5.6.2
Vereisten voor de realisatie van een kwantumcomputer . . . . . . . . .
71
5.6.3
Een kwantumprogrammeertaal . . . . . . . . . . . . . . . . . . . . . .
72
Kwantumcomputersimulators
73
6 Representatie van een kwantumtoestand 6.1
6.2
74
Pure toestanden en gemengde toestanden . . . . . . . . . . . . . . . . . . . .
74
6.1.1
Pure toestanden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
6.1.2
Gemengde toestanden . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
6.1.3
Pure of gemengde toestanden? . . . . . . . . . . . . . . . . . . . . . .
76
Datastructuren voor pure toestanden . . . . . . . . . . . . . . . . . . . . . . .
77
iii
6.2.1
Datastructuren en talen . . . . . . . . . . . . . . . . . . . . . . . . . .
77
6.2.2
Universums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
6.2.3
Aanpassingen ter plaatse voor manipulaties . . . . . . . . . . . . . . .
80
6.2.4
Volle en ijle vectorvoorstelling . . . . . . . . . . . . . . . . . . . . . . .
81
6.2.5
Algebra¨ısche voorstelling . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.2.6
Geblokte voorstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
7 Simulatoralgoritmen
87
7.1
Benodigde functionaliteiten . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
7.2
Initialiseren van de kwantumtoestand
. . . . . . . . . . . . . . . . . . . . . .
88
7.3
Toepassen van 1-bit kwantumpoorten . . . . . . . . . . . . . . . . . . . . . .
88
7.4
Toepassen van conditionele 1-bit kwantumpoorten . . . . . . . . . . . . . . .
94
7.5
Berekenen van kansen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
7.6
Metingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
7.7
Optimalisaties van de simulatoren . . . . . . . . . . . . . . . . . . . . . . . .
100
Besluit
103
A Tensorproducten
104
A.1 Definitie van tensorproduct-vectorruimten . . . . . . . . . . . . . . . . . . . .
104
A.2 Voorbeelden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105
A.2.1 Vectortensorproduct . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105
A.2.2 Matrixtensorproduct . . . . . . . . . . . . . . . . . . . . . . . . . . . .
105
B Matrix exponentiatie
106
C Voorbeeldimplementatie van een kwantumroutine: de QFT
107
Lijst van figuren
110
Algoritmen
112
Bibliografie
113
iv
Deel I
Kwantumcomputers
1
Hoofdstuk 1
Inleiding tot kwantumtheorie In dit hoofdstuk behandelen we de basisbegrippen uit de kwantumtheorie. De kwantumtheorie zal in de volgende hoofdstukken verder opgebouwd worden tot we voldoende achtergrondinformatie hebben om te begrijpen hoe een kwantumcomputer werkt. Daaropvolgend worden in Deel II de implementatie-aspecten voor een kwantumcomputersimulator besproken. Voor de basisbegrippen uit de kwantumtheorie heb ik mij voornamelijk gebaseerd op enkele uitgebreide teksten die handelen over kwantumcomputers. De belangrijkste van deze teksten waren [1, 22, 36, 38, 53].
1.1
Enkele belangrijke begrippen
We zullen hier in het kort enkele belangrijke begrippen aanhalen en verklaren die in het verdere verloop van de tekst nog veelvuldig aan bod zullen komen. De definities zijn onvolledig en vaag en hebben enkel tot doel om de verdere tekst te situeren. Ze moeten dan ook luchtig gelezen worden. Kwantummechanica en kwantumtheorie. Het is duidelijk dat de theoretische basis van een kwantumcomputer zich bij de wetten van de kwantummechanica situeert, vandaar de naam. Volgens van Dale en Kramers: 0 kwan·tum·me·cha·ni·ca
Wetenschap die de mechanische wetten inzake atomen en moleculen bestudeert en onderzoekt.
0 kwan·tum·the·o·rie
Deel van de natuurkunde dat de discontinu¨ıteit of sprongsgewijze verandering betreft die bij veel processen op zeer kleine schaal wordt waargenomen.
Op dit kleine niveau gelden er ‘andere’ natuurwetten dan wij op ons menselijk niveau waarnemen. Het zullen deze natuurwetten zijn die bepalen hoe een kwantumcomputer zich gedraagt en die bepalen wat er mogelijk en onmogelijk is. Het zijn ook deze wetten die de kwantumtheorie moeilijk te vatten maken door hun contra-intu¨ıtieve eigenschappen (bv. deeltjesgedrag en golfgedrag van een laser). 2
B
-
C
-
A
Figuur 1.1: Meerdere werelden interpretatie van Everett Kwantumbits of qubits. Een kwantumcomputer werkt met een kwantumgeheugen waarvan de bits zich op het moleculaire niveau bevinden. We noemen zo een bit dan ook een kwantumbit of korter een qubit van het Engelse quantum bit. De informatie die een bit bevat is gecodeerd als een onderscheidbare fysische eigenschap van een kwantummechanisch systeem, bijvoorbeeld de nucleaire spin (↑ en ↓) van een atoom bij een NMR-kwantumcomputer. Een verzameling van qubits, of met andere woorden een kwantumregister, is een noodzakelijk ingredi¨ent voor een kwantumcomputer. De toestand van dit kwantumregister zullen we manipuleren – volgens de wetten van de kwantummechanica – en hierdoor zullen we berekeningen uitvoeren waarvan we het resultaat bij afloop observeren. Superpositie van toestanden. Een belangrijke kwantummechanische eigenschap is de (coherente) superpositie van toestanden. Een kwantumsysteem kan zich tegelijkertijd in al zijn mogelijke toestanden bevinden. Een qubit die zich in de basistoestanden 0 en 1 kan bevinden, kan ook 0 en 1 tegelijkertijd zijn. Hetzelfde geldt voor een kwantumregister: een kwantumregister van 2 bit kan zich in alle vier de toestanden tegelijkertijd bevinden. Voor een n-bit kwantumregister zijn dit 2n toestanden waarin het register zich tegelijkertijd kan bevinden. Het is deze superpositie-eigenschap die kwantumalgoritmen een exponenti¨ele versnelling kan bezorgen ten opzichte van hun klassieke tegenhangers. We kunnen hierdoor verschillende berekeningspaden tegelijk volgen. Klassiek kunnen we ons weinig bij deze eigenschap voorstellen. Niemand heeft ooit een glas wijn gezien dat tegelijkertijd leeg en vol was! De meest aanvaarde theorie om hier tegenaan te kijken is de meerdere werelden interpretatie (MWI) van Hugh Everett [11]: hierin zorgt een observatie van een systeem (of beter: een complexe interactie) voor een splitsing van de werelden, zodat de observatie van een bepaalde toestand een feit wordt in de nieuwe wereld, zie Figuur 1.1. Verstrengeling of entanglement van toestanden. Een tweede belangrijke eigenschap is het zogenaamd verstrengeld zijn van toestanden. Hierbij kan interactie met een deel van het verstrengelde kwantumsysteem invloed uitoefenen op een ander deel; een soort van kwantumcorrelatie die klassiek niet te begrijpen valt. Een bekend voorbeeld is het EPR-paar (Einstein-Podolsky-Rosen) waarbij aan twee fotonen dezelfde polarisatie wordt gegeven. De twee fotonen worden in het proces met elkaar verstrengeld en zullen elkaars gedrag nadien be¨ınvloeden. Zelfs al zijn ze duizenden kilometers van elkaar verwijderd, is het effect onmiddellijk. Interferentie van berekeningspaden. In de kwantummechanica worden de toestanden van een systeem voorgesteld als golven. We hebben hier te maken met het fenomeen van interferentie, waardoor bepaalde uitkomsten van een berekening versterkt of verzwakt kunnen 3
worden. Deze eigenschap wordt gebruikt om de gewenste uitkomsten bij een berekening te versterken en de ongewenste uitkomsten af te zwakken. Dit is noodzakelijk omdat we van een systeem in superpositie maar ´e´en toestand kunnen waarnemen. Met interferentie zullen we ervoor trachten te zorgen dat we de door ons gewenste toestand waarnemen. Observatie van de kwantumtoestand. Observatie van een kwantumsysteem zorgt voor een splitsing van de wereld waarin de observatie gebeurde. Men kan bij een observatie van een n-bit kwantumregister maar ´e´en getal uitlezen. We koppelen aan de toestanden die in superpositie staan een klassieke waarschijnlijkheid om waargenomen te worden. Bij een observatie splitst de wereld van een kwantumregister zich in 2 n mogelijke paden: we zullen met een bepaalde waarschijnlijkheid ´e´en van die paden volgen. Het is door deze eigenschap dat we genoodzaakt zijn om door middel van interferentie de waarschijnlijkheid van de goede uitkomst zo groot mogelijk te maken. Decoherentie van de kwantumtoestand. Een andere vervelende eigenschap is het verval of decoherentie van een (coherente) superpositie. De superpositie-eigenschap, en de daarmee samenhorende verstrengelingseigenschap, gelden alleen indien het kwantumsysteem voldoende ge¨ısoleerd is van zijn omgeving. Een interactie met een complex systeem (zoals een waarnemer) heeft een zodanige invloed op het systeem dat er een splitsing van de wereld gebeurt. Er ontstaat een kwantumcorrelatie tussen de waarnemer en het waargenomen kwantumsysteem waardoor het systeem verstrengeld raakt met zijn omgeving. Met decoherentie bedoelen we dan ook de (langzame) verstrengeling van het kwantumsysteem met zijn omgeving omdat een totale isolatie niet echt mogelijk is.
1.2
De kwantumbit
Allereerst beschrijven we de kwantumbit of qubit als eenheid van informatie in een kwantumcomputer, alsook het begrip superpositie en observatie voor een enkele kwantumbit.
1.2.1
Een kwantummechanische informatie-eenheid
Om informatie voor te stellen gebruiken we de bit die zich in twee logische toestanden kan bevinden uit de verzameling {0, 1}. Deze bit wordt klassiek voorgesteld door een elektrische lading, bijvoorbeeld een verzameling elektronen op een capaciteit, waarbij de hoeveelheid elektrische lading ´e´en van de twee mogelijke toestanden bepaalt. Door de fysische voorstelling van een bit te minimaliseren tot op atoomniveau, beginnen de wetten van de kwantummechanica mee te spelen en noemen we onze bit een kwantumbit of korter een qubit. Definitie 1.1 (Kwantumbit). Een kwantumsysteem |ψi met twee observeerbare toestanden |0i en |1i is een kwantumbit of qubit. Deze basistoestanden worden voorgesteld als orthonormale basisvectoren in een tweedimensionale Hilbert-ruimte H, 0 1 (1.1) en |1i = |0i = 1 0 4
en worden de berekeningsbasis of computational basis genoemd. De toestandsvector van een kwantumsysteem |ψi is een genormaliseerde lineaire combinatie van deze basistoestanden |ψi = α |0i + β |1i α = β met
α, β ∈ C
k |ψi k2 = |α|2 + |β|2 = 1.
(1.2)
(1.3)
De Hilbert-ruimte voor ´e´en enkele kwantumbit is gedefinieerd als H = span{|0i , |1i} ∼ = C2 .
(1.4)
Notatie. Om notatieproblemen te vermijden in de veelal hoogdimensionale vectorruimten, gebruiken we voor toestandsvectoren de in kwantummechanica gebruikelijke Dirac-notatie of bra-ket-notatie. Een ket-vector is een kolomvector en stelt een fysische toestand voor die we noteren met |ψi voor een toestand ψ. Een bra-vector is zijn Hermitiaans toegevoegde en noteren we met hψ| = |ψi ∗ . Het inwendige product van de basisvectoren in de Hilbert-ruimte kunnen we schrijven als: h0|0i = 1,
h0|1i = 0,
h1|0i = 0 en h1|1i = 1.
In het Engels kan je zeggen dat het samenvoegen van de bra hψ| en de ket |φi een bracket hψ|φi is, vandaar de naam.
1.2.2
Superpositie van toestanden
De eerste kwantummechanische eigenschap waarvan we gebruik kunnen maken door met kwantumbits te werken in plaats van met klassieke bits, is de superpositie van de toestanden 0 en 1. De toestandsvector |ψi van een kwantumbit kan zich in een willekeurige (genormaliseerde) lineaire combinatie van |0i en |1i bevinden. met |α|2 + |β|2 = 1
|ψi = α |0i + β |1i
(1.5)
De co¨effici¨enten α en β zijn de complexe amplitudes van elk van de basistoestanden. Als we complexe getallen als fasors beschouwen, hebben we met andere woorden de bijdrage van de 0-golf en de 1-golf in de ψ-golf. De toestand van een kwantumbit wordt meestal voorgesteld op een 3-dimensionale Bloch-sfeer. Voor een 2-dimensionale complexe vector hebben we natuurlijk 4 co¨ordinaten nodig, want in feite is de toestandsvector van een kwantumbit een punt op een 4-dimensionale hypersfeer met straal 1. We bekomen de Bloch-voorstelling door een vereenvoudiging te maken. We stellen een complex getal voor als z = |z| (cos φ + i sin φ) = |z| ei φ , 5
(1.6)
|0i
|di
φ θ
|ci
|ei
|ψ 0 i |0i |1i |ci =
|di = |ei =
θ 0 π √1 |0i + √1 |1i 2 √2 1 3 2 |0i + 2 |1i √ √ 3 2 |0i + ( 2 4 +
i
√ 2 4 ) |1i
π 2 π 3 π 3
φ 0 0 0 0 π 4
|1i
Figuur 1.2: De toestand van een kwantumbit op een Bloch-sfeer hierin is |z| de amplitude en φ de fasehoek van z bekeken als fasor. We krijgen dan |ψi = α |0i + β |1i = |α| ei φα |0i + |β| ei φβ |1i .
(1.7)
Hieruit zullen we de gemeenschappelijke fasedraaiing weglaten en zo enkel een faseverschuiving tussen de twee basistoestanden, φ = φ α − φβ , overhouden: |ψ 0 i = |α| |0i + |β| ei φ |1i .
(1.8)
Omdat de toestandsvector genormaliseerd is hebben we 1 ≡ |α|2 + |β ei φ |2 = |α|2 + |β|2 .
(1.9)
We kunnen nu beide termen van de som identificeren met beide leden uit de goniometrische identiteit θ θ 1 ≡ cos2 + sin2 . (1.10) 2 2 De twee hoeken φ en θ dienen nu als parametrisatie voor de fasedraaiing en de respectievelijke amplitudes van de basistoestanden. We schrijven nu |ψ 0 i = (cos θ2 ) |0i + (sin 2θ ) ei φ |1i .
(1.11)
Enkele voorbeelden zijn te zien in Figuur 1.2. De amplitudeverhouding tussen |0i en |1i lezen we af aan de hoek θ met de verticale as. De relatieve fasedraaiing is de rotatiehoek φ rond de verticale as (parallel met de horizontale). Op een Bloch-sfeer wijst de |0i toestandsvector naar boven en de |1i toestandsvector naar onder. Terwijl de klassieke toestanden zich op de noorden zuidpool bevinden, kan een kwantumtoestand zich in een ontelbaar aantal combinaties bevinden.
1.2.3
Observatie van een kwantumbit
Wanneer we een observatie doen van een kwantumbit die zich in een klassieke toestand 0 of 1 bevindt, zullen we uiteraard die klassieke toestand waarnemen. Wanneer de kwantumbit zich echter in een superpositie van de twee basistoestanden bevindt, zullen we maar ´e´en van de twee mogelijke klassieke toestanden kunnen observeren, o`f 0 o`f 1. Door de normalisatie-eis (1.3) kunnen we |α|2 en |β|2 beschouwen als klassieke waarschijnlijkheden om de respectievelijke toestanden te observeren. Het is dan ook op deze manier dat men deze complexe amplitudes definieert in de kwantummechanica. 6
Definitie 1.2 (Observatie van een kwantumbit). Indien we een kwantumbit observeren die zich in de onbekende toestand |ψi = α |0i + β |1i bevindt, dan hebben we respectievelijk |α|2 en |β|2 kans om de klassieke toestanden 0 en 1 aan te treffen. Na de observatie zal de kwantumwereld zich gesplitst hebben zodat de observatie een feit wordt. Bij een observatie van 0 zal vanaf nu α = 1 en β = 0 gelden in deze wereld, bij een observatie van 1 zal α = 0 en β = 1 gelden in die wereld. Door deze splitsing is het onmogelijk om de toestand van een onbekende kwantumbit volledig te bepalen: de kwantumbit bevindt zich na de observatie namelijk in een toestand die consistent is met de waargenomen waarde. De vorige toestand is onbereikbaar geworden. Een meting of observatie van een toestand hoeft volgens MWI niet per definitie te gebeuren door een bewuste persoonlijkheid, maar gebeurt in principe door interactie met een complex niet-reversibel proces [11].
1.3
De postulaten van de kwantummechanica
De toestandsbeschrijving en observatie van een kwantumsysteem worden beschreven in de postulaten van de kwantummechanica, we volgen hier de uitleg in [23].
1.3.1
Toestandsbeschrijving en -evolutie
Het eerste postulaat handelt over de toestand van een samengesteld systeem. Zo kunnen we een n-bit kwantumregister beschouwen als een systeem dat is samengesteld uit n deelsystemen van ´e´en kwantumbit. Postulaat 1. De toestand van een systeem dat bestaat uit K deelsystemen kan beschreven worden door een toestandsvector |ψi in de productruimte H = H 1 ⊗ H2 ⊗ · · · ⊗ HK , waarbij Hk de Hilbert-ruimte is van deelsysteem k. Het gebruik van het tensorproduct ⊗ is terug te vinden in Bijlage A. Voor een 5-bit kwantumregister |x4 , x3 , x2 , x1 , x0 i krijgen we een 32-dimensionale complexe vectorruimte H = H x4 ⊗ H x3 ⊗ H x2 ⊗ H x1 ⊗ H x0 ∼ = C2 ⊗ C 2 ⊗ C 2 ⊗ C 2 ⊗ C 2 = C2
5
= C32 . Afhankelijk van de aard van het kwantumsysteem of de deelsystemen kan de dimensie van de uiteindelijke Hilbert-ruimte oneindig, aftelbaar, continu of een mogelijke combinatie hiervan zijn. Voor kwantumcomputers werken we steeds met eindige continue Hilbert-ruimten. Het tweede postulaat handelt over de evolutie van een kwantumsysteem. Dit zal nog uitgebreid aan bod komen wanneer we het over kwantumpoorten zullen hebben in §4.1. 7
Postulaat 2. De tijdsevolutie van een toestandsvector |ψ(t)i is unitair zodanig dat ˆ (t, t0 ) |ψ(t)i , |ψ(t0 )i = U
(1.12)
ˆ (t, t0 ) een unitaire operator. met U
1.3.2
Observatie van een kwantumtoestand
De laatste twee postulaten handelen over de observatie van een kwantumtoestand. We moeten hiervoor een onderscheid maken tussen de deelsystemen die we rechtstreeks waarnemen |o n i en de deelsystemen die we niet rechtstreeks waarnemen |u n i. De toestand van het gehele systeem schrijven we als X |ψi = cn |on i |un i . (1.13) n
De {on } vormen een orthonormale basis van de toestanden die we kunnen observeren, bij elke on hebben we een un die de toestand van het niet geobserveerde gedeelte beschrijft.
Postulaat 3. De waarschijnlijkheid dat we de toestand |o k i observeren is |ck |2 . Dit is een veralgemening van het eenvoudige kwantumbitgeval waar we |α| 2 en |β|2 als waarschijnlijkheden voor de rechtstreeks geobserveerde toestanden 0 en 1 hadden. Postulaat 4 is het projectiepostulaat: Postulaat 4. Nadat we de toestand |o k i geobserveerd hebben, wordt de toestand van het volledige systeem |ψ 0 i = |ok i |uk i. De kwantumtoestand wordt geprojecteerd op een nieuwe kwantumtoestand die compatibel is met de waarneming: de wereld is gesplitst door de niet-reversibele waarneming. De niet rechtstreeks geobserveerde deelsystemen zullen hierdoor ook uitgeprojecteerd worden.
1.3.3
Waarneembare toestanden
Een rechtstreeks observeerbaar systeem noemt men een observable in de kwantummechanica. De waarden die we kunnen observeren zijn dan de eigenwaarden van het systeem en zijn per definitie re¨eel. Mathematisch stelt men een observable voor met een matrix A. Dat we maar ´e´en bepaalde waarneembare toestand kunnen observeren, drukken we uit door de eigenvectoren orthogonaal te nemen. In feite is de observable matrix A de basis van de Hilbert-ruimte waarin de toestandsvectoren leven en we normaliseren deze vectoren zodat ze de basistoestanden van het systeem voorstellen. Definitie 1.3 (Observable). Een observable A is een Hermitiaanse operator in de toestandsruimte H van het kwantumsysteem met als eigenwaarden de experimenteel waarneembare uitkomsten van een meting. Voorbeeld 1.1. We kunnen een kwantumbit voorstellen door de z-spin van een elektron. De twee waarneembare toestanden of eigenwaarden die we aan dit systeem koppelen zijn +1 voor 8
↑z en −1 voor ↓z , die we respectievelijk voor de binaire toestanden 0 en 1 zullen gebruiken. De observable matrix A is dan 1 0 (1.14) A= 0 −1 met als eigenvectoren
1 λ0 = 1 → |0i = 0 0 λ1 = −1 → |1i = 1
(1.15)
♦
1.4
Een kwantumregister
Om gegevens te kunnen verwerken en nuttige berekeningen te kunnen uitvoeren, hebben we natuurlijk niet genoeg aan ´e´en enkele kwantumbit: we willen een volledig kwantumgeheugen. We zullen dit geheugen meestal een kwantumregister noemen, zoals gebruikelijk in de literatuur, omdat we het meestal in zijn geheel moeten beschouwen. Soms zal met de term ‘register’ een deel van het geheugen aangeduid worden, soms het volledige geheugen.
1.4.1
Meerdere kwantumbits
We defini¨eren een kwantumregister als een collectie kwantumbits die samen ´e´en systeem vormen zoals in Postulaat 1. Definitie 1.4 (Kwantumregister). Een n-bit kwantumregister stellen we voor als een toestandsvector in een Hilbert-ruimte H die het tensorproduct is van de n Hilbert-ruimten van de afzonderlijke kwantumbits. H = Hn−1 ⊗ · · · ⊗ H1 ⊗ H0 n ∼ = C2 ⊗ · · · ⊗ C 2 ⊗ C 2 = C 2
(1.16)
Als orthonormale basis voor deze ruimte H nemen we de klassieke toestanden die we met n bits kunnen vormen H = span{|0 . . . 00i , |0 . . . 01i , |0 . . . 10i , . . . , |1 . . . 11i}
(1.17)
en we noemen dit de berekeningsbasis of computational basis. De toestandsvector van een kwantumregister noteren we als |ψi =
n −1 2X
k=0
ck |ki
ck ∈ C
(1.18)
en is per definitie genormaliseerd zodat |c k |2 de waarschijnlijkheid aangeeft om toestand |ki te observeren.
9
Notatie. We gebruikten hierboven een verkorte notatie. Voor de toestand |i n−1 i ⊗ · · · ⊗ |i1 i ⊗ |i0 i schrijven we ook |in−1 i · · · |i1 i |i0 i of |in−1 , · · · , i1 , i0 i. Verder schrijven we voor een basistoestand meestal het getal in decimale vorm in plaats van in binaire vorm, bijvoorbeeld |3i in plaats van |011i.
1.4.2
Superpositie in een register
Net als bij de kwantumbit kunnen we het kwantumregister in een superpositie brengen van zijn basistoestanden. Voor een n-bit kwantumregister hebben we dan 2 n complexe co¨effici¨enten ck , waaruit we de klassieke waarschijnlijkheid voor toestand |ki rechtstreeks kunnen berekenen als Prob[|ki] = |ck |2 . (1.19) De waarschijnlijkheid dat we een 1 meten voor bit j in een kwantumregister, is de som van de waarschijnlijkheden van de toestanden waarin die bit 1 is: Prob[|1i j ] =
n −1 2X
Prob[|ki],
(1.20)
k=0 k∧(1<<j)
met (1<<j) een bitmask voor bit j waardoor k over alle mogelijke toestanden van het kwantumregister loopt waarvoor bit j gezet is. De waarschijnlijkheid om een 0 te meten op index j is dan uiteraard Prob[|0ij ] = 1 − Prob[|1i j ].
(1.21)
Voorbeeld 1.2. Indien we een 3-bit kwantumregister nemen, dan kunnen we hiermee 2 3 = 8 toestanden voorstellen. De getallen 0 . . . 7 zijn onze fysische toestanden. De Hilbert-ruimte waarin dit register leeft is H = span{|000i , |001i , |010i , |011i , |100i , |101i , |110i , |111i} = span{|0i , |1i , |2i , |3i , |4i , |5i , |6i , |7i}.
(1.22)
Een toestandsvector in deze ruimte heeft 8 componenten waarbij elke component een maat is voor de waarschijnlijkheid om een bepaalde basistoestand te observeren. |ψi =
c000 c001 c010 c011 c100 c101 c110 c111
De toestand 3 noteren we als |3i = |011i
T
(1.23)
(1.24)
= |0i ⊗ |1i ⊗ |1i 1 0 0 = ⊗ ⊗ 0 1 1 T = 0 0 0 1 0 0 0 0 , 10
de gelijke superpositie van 3 en 7 als √1 2
1.4.3
|3i +
√1 2
|011i + √12 |111i T = √12 0 0 0 1 0 0 0 1 √1 |0i + √1 |1i ⊗ |1i ⊗ |1i . = 2 2
|7i =
√1 2
(1.25)
♦
Verstrengeling van toestanden
Onder verstrengeling van toestanden of entanglement verstaan we de niet-klassieke correlaties die kunnen optreden wanneer we een kwantumsysteem beschouwen dat uit verschillende deelsystemen bestaat. Indien we het over klassieke systemen hadden dan konden we het hele systeem beschrijven door alle deelsystemen afzonderlijk te beschrijven. Bij een kwantumsysteem kunnen we te maken hebben met toestanden die niet te beschrijven zijn door de deelsystemen te beschrijven: we hebben dan te maken met een kwantumcorrelatie tussen de deelsystemen en spreken over verstrengelde deelsystemen. Doordat een kwantumregister is samengesteld uit verschillende kwantumbits kan er verstrengeling optreden tussen die verschillende kwantumsystemen. Verstrengeling leidt tot het begrip ‘niet-lokale informatie’: een kwantumregister kan hierdoor informatie bevatten die enkel voor het gehele register bestaat. Indien we bijvoorbeeld een periodische functie f toepassen op een kwantumregister dat in een volledige superpositie staat van al zijn 2 n mogelijke waarden, dan kunnen we als globale informatie de periode van f uit het resultaat onttrekken. Het tegenovergestelde van verstrengeling is het scheidbaar zijn: Definitie 1.5 (Scheidbaarheid). Een kwantumsysteem met toestandsvector |ψi in de n−1 Hilbert-ruimte H = ⊗k=0 Hk , opgespannen door zijn n deelsystemen, is scheidbaar ten opzichte van {H0 , H1 , . . . , Hn−1 } als de toestandsvector geschreven kan worden als een tensorproduct Nn−1 |ψi = k=0 |ψk i , |ψk i ∈ Hk . (1.26)
Definitie 1.6 (Verstrengeling). De n deelsystemen van een kwantumsysteem zijn verstrengeld wanneer ze niet scheidbaar zijn en enkel geschreven kunnen worden als een som van basisvectoren in de globale Hilbert-ruimte van het volledige kwantumsysteem H = span{|ψ N i}, met N basisvectoren: X |ψi = cN |ψN i . (1.27) N
Verstrengeling van de deelsystemen van een kwantumregister is een zeer belangrijke kwantummechanische eigenschap. Het is een noodzakelijk ingredi¨ent om kwantumalgoritmen een exponenti¨ele versnelling te kunnen geven ten opzichte van hun klassieke tegenhangers [27]. Verstrengeling is ook verantwoordelijk voor de exponenti¨ele geheugen- en tijdscomplexiteit van een kwantumcomputersimulator. Het is heel belangrijk om verstrengeling goed te begrijpen; we zullen hier dieper op in gaan in §2.3. 11
Voorbeeld 1.3. We bekijken enkele voorbeelden van niet-verstrengelde en verstrengelde toestanden in een kwantumregister. • De gelijke superpositie van |3i en |7i uit Voorbeeld 1.2 is niet verstrengeld, we kunnen de toestand schrijven als √1 |3i + √1 |7i = √1 |0i + √1 |1i ⊗ |1i ⊗ |1i . (1.28) 2 2 2 2 Dit geldt voor alle verhoudingen van toestanden |3i en |7i, niet alleen voor een gelijke superpositie.
• De gelijke superpositie van alle mogelijke toestanden voor een 3-bit kwantumregister is ook niet verstrengeld, want: 2−3/2 (|0i + |1i + |2i + |3i + |4i + |5i + |6i + |7i) P7 = 2−3/2 k=0 |ki = √12 |0i + √12 |1i ⊗ √12 |0i + √12 |1i ⊗ · · · ⊗ √12 |0i + N = 7k=0 √12 |0i + √12 |1i .
√1 2
|1i
(1.29)
Elke bit heeft evenveel kans om 0 of 1 te zijn.
• We beschouwen enkele superposities van een 2-bit kwantumregister met α en β willekeurige co¨effici¨enten die voldoen aan de normalisatie-eis: T a. α |00i + β |01i = α β 0 0 = |0i ⊗ (α |0i + β |1i) T b. α |01i + β |11i = 0 α 0 β = (α |0i + β |1i) ⊗ |1i T c. α |01i + β |10i = 0 α β 0 T d. α |00i + β |11i = α 0 0 β T N e. 21 (|00i + |01i + |10i + |11i) = 21 1 1 1 1 = 3k=0 √12 |0i + √12 |1i De gevallen a, b en e zijn niet-verstrengeld, c en d daarentegen wel.
• Een laatste voorbeeld waarbij we de bits in een 4-bit kwantumregister herschikken. |ψi =
=
1 2 1 2
(|3i + |6i + |9i + |12i)
(|0011i + |0110i + |1001i + |1100i)
(1.30)
We zullen de bits in (1.30) nu herschikken zodat duidelijk wordt dat we toch nog twee deelsystemen kunnen onderscheiden die niet verstrengeld zijn. We duiden in subscript aan op welke positie een bit zich bevindt. |ψi =
= =
1 2 (|03 02 11 10 i + |03 12 11 00 i + |13 02 01 10 i + |13 12 01 00 i) 1 2 (|03 11 02 10 i + |03 11 12 00 i + |13 01 02 10 i + |13 01 12 00 i) √1 (|03 11 i + |13 01 i) ⊗ √1 (|02 10 i + |12 00 i) 2 2
12
(1.31)
We hebben de bits met subscripts 1 en 2 van plaats verwisseld. We stellen vast dat we twee deelsystemen A (bits 0 en 2) en B (bits 1 en 3) hebben die niet met elkaar verstrengeld zijn, maar die op zichzelf wel verstrengeld zijn: we kunnen A (of B) niet schrijven als een tensorproduct (zie geval c uit het vorige voorbeeld). ♦
1.4.4
Observatie van een kwantumregister
Voor de observatie van een kwantumregister doen we beroep op Postulaat 4, het projectiepostulaat. Hierin wordt bepaald dat door een meting van een deelsysteem, de toestand van het systeem waar het deel van uitmaakt, geprojecteerd wordt op een globale compatibele toestand. Definitie 1.7 (Observatie van een kwantumregister). Indien we een meting doen op bit j van een kwantumregister in toestand X X |ψi = ck |ki = ck |xn−1 · · · xj · · · x0 i xi ∈ B = {0, 1} (1.32) k
k
en we observeren de bit in toestand d ∈ B, dan zullen we de toestandsvector uitprojecteren zodat alleen toestanden consistent met deze meting overblijven. Als we index l gebruiken om toestanden van de vorm |xn−1 · · · d · · · x0 i aan te duiden, dan is de nieuwe toestandsvector P l cl |li (1.33) |ψ 0 i = pP 2 l |l| P cl |li =q l . Prob[|di j ]
We kunnen kwantumcorrelatie (verstrengeling) duidelijk aan het werk zien voor een 2-bit kwantumregister |x1 , x0 i wanneer we achtereenvolgens bit 0 en bit 1 meten. We beschouwen het register in twee verschillende begintoestanden: • de scheidbare toestand |ψi =
1 2
(|00i + |01i + |10i + |11i): √1 (|00i + 2 00 |ψ i = |00i
|10i)
√1 (|01i + 2 00 |ψ i = |01i
|11i)
1. 50% kans op x0 = 0, na meting: |ψ 0 i =
(1) 50% kans op x1 = 0, na meting: (2) 50% kans op x1 = 1, na meting: |ψ 00 i = |10i
2. 50% kans op x0 = 1, na meting: |ψ 0 i =
(1) 50% kans op x1 = 0, na meting: (2) 50% kans op x1 = 1, na meting: |ψ 00 i = |11i • de verstrengelde toestand |ψi = EPR-paar):
√1 2
|00i + 13
√1 2
|11i (dit is een maximaal verstrengeld
1. 50% kans op x0 = 0, na meting: |ψ 0 i = |00i
(1) 100% kans op x1 = 0, na meting: |ψ 00 i = |00i (2) 0% kans op x1 = 1, na meting: |ψ 00 i = |10i
2. 50% kans op x0 = 1, na meting: |ψ 0 i = |11i
(1) 0% kans op x1 = 0, na meting: |ψ 00 i = |01i (2) 100% kans op x1 = 1, na meting: |ψ 00 i = |11i
Als klassieke lokale informatie hadden we voor beide bits a priori 50% kans op 0 of 1 in de beide gevallen. In het scheidbare geval blijft die kans, zoals verwacht, hetzelfde na de meting van ´e´en bit. In het verstrengelde geval ‘verstoort’ deze meting de toestand en krijgen we een kwantumcorrelatie tussen de twee bits: de tweede bit levert namelijk eenzelfde resultaat op als de eerste. Deze kwantumcorrelatie is op de klassieke manier niet te begrijpen. De volgorde van een meting is dan ook belangrijk in kwantummechanica: door een meting te doen op een gedeelte van het kwantumsysteem kan het zijn dat een hoop informatie onbereikbaar wordt door een splitsing in parallelle werelden (MWI). De wereld waarin we ons bevinden na de splitsing zal alleen maar informatie bevatten die in overeenstemming is met de meting; de informatie uit de parallelle werelden is onbereikbaar. Een uitgebreider voorbeeld: Voorbeeld 1.4. We beschouwen een 3-bit kwantumregister |x 2 , x1 , x0 i dat zich in de volgende toestand bevindt √1 2
|110i + 12 |111i √ T = 1/2 0 0 0 0 0 1/ 2 1/2 ,
|ψi =
1 2
|000i +
(1.34)
met Prob[|0i] = 1/4, Prob[|6i] = 1/2 en Prob[|7i] = 1/4.
De meest significante bit, x2 , heeft als waarschijnlijkheden Prob[|0i2 ] = 1/4
(1.35)
Prob[|1i2 ] = Prob[|110i] + Prob[|111i]
(1.36)
= 1/2 + 1/4 = 3/4. We hebben 25% kans om x2 = 1 te zien en 75% kans om x2 = 0 te zien. Veronderstel dat we x2 = 1 meten, dan wordt de nieuwe toestand: √ T |ψ 0 i = (3/4)−1/2 0 0 0 0 0 0 1/ 2 1/2 p √ = 2/3 |110i + 1/ 3 |111i p √ = |1i ⊗ |1i ⊗ 2/3 |0i + 1/ 3 |1i
Deze meting heeft invloed op de kansverdeling van de andere bits:
14
(1.37)
kans Prob[|0i 0 ] Prob[|1i 0 ] Prob[|0i 1 ] Prob[|1i 1 ] Prob[|0i 2 ] Prob[|1i 2 ]
v´oo´r 3/4 1/4 1/4 3/4 1/4 3/4
(|ψi) 75% 25% 25% 75% 25% 75%
n´a (|ψ 0 i) 2/3 67% 1/3 33% 0 0% 1 100% 0 0% 1 100% ♦
1.5
Meerdere werelden interpretatie
Het is ondertussen wel duidelijk dat er een raamwerk nodig is om de schijnbare kwantummechanische paradoxen te kaderen. Er bestaan verschillende idee¨en voor zo’n raamwerk; ´e´en er van is de meerdere werelden interpretatie (MWI) van Hugh Everett [11]. MWI is de populairste verklaring vanuit het perspectief van wetenschappers die bezig zijn met kwantumcomputers [16] en is ook de visie die we in deze tekst hanteren. MWI introduceert drie voorspellingen [11]: • lineariteit van de golffunctie, waardoor het onmogelijk is om tussen verschillende parallelle werelden te communiceren; • kwantumgravitatie: gravitatie wordt veroorzaakt door kwantumdeeltjes, gravitons genaamd, en • kwantumcomputers: MWI voorspelt dat de parallelle werelden niet met elkaar interageren, maar wel interfereren (zoals het interferentiepatroon bij een laser). Hierdoor wordt het mogelijk om kwantumcomputers te maken die van deze eigenschap gebruik maken.
1.5.1
De kat van Schr¨ odinger
Een bekend historisch gedachtenexperiment is de kat van Schr¨odinger, schematisch voorgesteld in Figuur 1.3. Schr¨odinger formuleerde het als volgt [45, 49]: One can even set up quite ridiculous cases. A cat is penned up in a steel chamber, along with the following diabolical device (which must be secured against direct interference by the cat): in a Geiger counter there is a tiny bit of radioactive substance, so small that perhaps in the course of one hour one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter tube discharges and through a relay releases a hammer which shatters a small flask of hydro cyanic acid. If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed. The first atomic decay would have poisoned it. The Psi (wave) function for the entire system would express this by 15
|kat0 i = |doodi
-
|kat0 i = |levendi
-
|kati = p0 |doodi + p1 |levendi
Figuur 1.3: De kat van Schr¨odinger having in it the living and the dead cat (pardon the expression) mixed or smeared out in equal parts. It is typical of these cases that an indeterminacy originally restricted to the atomic domain becomes transformed into macroscopic indeterminacy, which can then be resolved by direct observation. That prevents us from so naively accepting as valid a “blurred model” for representing reality. In itself it would not embody anything unclear or contradictory. There is a difference between a shaky or out-of-focus photograph and a snapshot of clouds and fog banks. De kat-paradox is makkelijk verkeerd te verstaan [45]. Is het de kat die in een superpositietoestand is van leven en dood? Zal de waarnemer een moord op zijn geweten hebben door de doos te openen? Natuurlijk niet! Het kwantumelement wordt gemeten door de geigerteller. Zolang de geigerteller niets detecteert is het kwantumsysteem in superpositie. Bij detectie in de doos splitst de wereld in de doos. Voor een waarnemer buiten de doos zijn het zuiver klassieke waarschijnlijkheden om een dode kat of een levende kat aan te treffen bij het openmaken van de doos. Het onderscheid zal duidelijker worden wanneer we het hebben over gemengde kwantumtoestanden in §2.2.3 en het verschil met superposities in §2.2.4. E´en van de problemen die duidelijk worden bij het lezen van dit verhaaltje is de dunne lijn tussen de waarnemer (de geigerteller) en het waargenomen systeem, de zogenaamde Heisenberg cut [21]. Waar ligt die lijn tussen waarnemer en waargenomen systeem, en wanneer splitst de wereld zich doordat de waarnemer de informatie heeft opgenomen? We kunnen deze vragen relativeren door kwantummechanica te bekijken als een statistische beschrijving van niet-commutatieve informatie, in tegenstelling tot klassieke mechanica waar informatie over een systeem wel commutatief is en de waarnemer extra informatie krijgt [21]. Bij commutatieve informatie maakt het niet uit in welke volgorde we metingen doen, we krijgen voor alle metingen dezelfde resultaten. Bij niet-commutatieve informatie is dat niet het geval, duidelijk ge¨ıllustreerd door het onzekerheidsprincipe van Hessenberg. Met andere woorden, door het niet-commutatief zijn van informatie wordt het systeem vanuit het oogpunt van de waarnemer ‘verstoord’. De waarnemer moet breed opgevat worden: bewustzijn speelt geen rol in de observatie. De waarnemer kan een meetinstrument zijn, gekoppeld aan een computer of het meetinstrument zelf, zolang het maar informatie kan verzamelen [11, 21]. De twee hoger gestelde vragen kunnen we echter ook bij de klassieke mechanica stellen. Alleen lijken de vragen in het kwantummechanische geval spontaner door de vreemde eigenschappen. We kunnen hierdoor stellen dat ze puur filosofisch zijn en er eigenlijk niet echt toe doen, zoals we dat voor het klassieke geval zouden doen. We hebben in de twee gevallen 16
te maken met verschillende soorten informatie: commutatief en niet-commutatief en dat verklaart het ‘vreemde’ gedrag van kwantummechanica. Indien we gewoon de parallelle werelden aanvaarden, is er helemaal niets vreemd aan.
1.5.2
Alternatieve interpretaties
Naast de meerdere werelden interpretatie zijn er nog tal van andere theorie¨en. De meesten hebben allemaal wel ergens een interne inconsistentie. David Deutsch deelt de kwantumtheorie¨en op in drie categorie¨en [15]: 1. theorie¨en die op verschillende manieren het idee van parallelle universums uitdrukken; 2. theorie¨en die op allerlei manieren trachten te ontkennen dat kwantumtheorie een echte beschrijving van de werkelijkheid is en 3. verwarrende, inconsistente en onduidelijk makende theorie¨en. Tot de eerste categorie behoren allerlei varianten van MWI, waaronder die van Deutsch zelf (de multiverse theorie). In de tweede categorie vinden we statistische theorie¨en en theorie¨en die de waarnemer buiten het systeem plaatsen. De derde categorie bevat o.a. de Kopenhageninterpretatie, die in feite nog steeds geldt als de offici¨ele theorie. We kunnen een theorie ook categoriseren als lokaal of niet-lokaal opererend. Bij een niet-lokale theorie zal er op ´e´en of andere manier een onmiddellijke inwerking zijn van deelsystemen die zich niet in elkaars onmiddellijke omgeving bevinden, in Einstein’s woorden: ‘spooky action-at-a-distance’, waarmee hij communicatie bedoelde die sneller was dan het licht (bij verstrengeling van deelsystemen). Communicatie die sneller gaat dan het licht is onmogelijk volgens de speciale relativiteitstheorie van Einstein en dus moeilijk te aanvaarden. Het splitsen van de wereld gebeurt volgens MWI echter bij ontvangst van de informatie en in de wereld van de waarnemer. MWI is hierdoor een lokale en deterministische theorie [11] en bevat geen communicatie die sneller is dan het licht. Drie van de bekendere alternatieve theorie¨en zijn de (offici¨ele) Kopenhagen-interpretatie, de verborgen variabelen theorie en de niet-lineaire theorie¨en die we hier in het kort zullen beschrijven. De Kopenhagen-interpretatie. In de Kopenhagen-interpretatie ondergaat de waarnemer andere fysische wetten dan de waargenomen kwantumsystemen zelf. Bij een observatie spreekt men van een ineenstorting van de golffunctie in een eigenfunctie; het kwantumsysteem ‘kiest’ bij observatie in welke basistoestand het zich bevindt. De Kopenhagen-interpretatie is een lokale theorie als we de golffunctie niet beschouwen als een model voor de werkelijkheid en ze is niet-lokaal als we dat wel doen [11]. We willen natuurlijk een theorie die de werkelijkheid beschrijft `en die lokaal is. De verborgen variabelen theorie. Deze theorie werd geopperd door Einstein, Podolsky en Rosen om te argumenteren dat kwantumtheorie onvolledig was. Hierin is er een verborgen 17
variabele die de toestand van een kwantumsysteem reeds van bij het begin vastlegt. In plaats van een aantal mogelijke uitkomsten met hun waarschijnlijkheden, wordt van bij het begin reeds bepaald welke uitkomst het is, rekening houdend met de waarschijnlijkheidsdichtheidsfunctie van het kwantumsysteem. John Bell publiceerde in 1964 echter een artikel waarin hij aantoonde dat er kwantummechanische effecten kunnen optreden die niet te verklaren zijn met de lokale verborgen variabelen theorie. Bell’s idee¨en zijn later bevestigd door experimenten. Er bestaat echter nog een niet-lokale verborgen variabelen theorie van Bohm die isomorf is met MWI maar veel complexer [11]. Niet-lineaire theorie¨ en. Er zijn heel wat idee¨en voor niet-lineaire theorie¨en. Voor een groot aantal van deze theorie¨en kunnen er experimenten uitgedacht worden. Die tot hiertoe allemaal vernietigend waren voor de betreffende theorie. MWI voorspelt dat niet-lineaire theorie¨en altijd zullen falen in een experiment, want MWI stelt dat de golffunctie lineair is.
18
Hoofdstuk 2
Kwantumtoestanden In dit hoofdstuk zullen we dieper ingaan op de manier waarop we de kwantumtoestand van een kwantumregister kunnen beschrijven. De voorstellingswijze uit het vorige hoofdstuk zal uitgebreid worden met densiteitsmatrices. We bekijken het verschil tussen pure en gemengde toestanden en het verband tussen superpositie van toestanden, menging van toestanden en zuivere basistoestanden en we zullen verstrengeling van deelsystemen van naderbij bekijken.
2.1
De amplitudevoorstelling
Als toestandsbeschrijving van een kwantumregister hebben we in Definitie 1.4 een toestandsvector gedefinieerd van de vorm: c0···00 c0···01 X (2.1) |ψi = ck |ki = . .. k
c1···11
Deze voorstellingswijze wordt de amplitudevoorstelling genoemd omdat we de complexe co¨effici¨enten ck als complexe amplitudes kunnen bekijken. We kunnen de co¨effici¨enten ck omvormen tot een re¨ele amplitude Ak en een re¨ele fasedraaiing φk door de identiteit z = |z| ei φz . X |ψi = ck |ki k
=
X k
Ak ei φk |ki
(2.2)
= A0···00 ei φ0···00 |0 · · · 00i + A0···01 ei φ0···01 |0 · · · 01i + · · · + A1···11 ei φ1···11 |1 · · · 11i .
Met andere woorden: we hebben een 2n -dimensionale golffunctie |ψi die een superpositie is van de orthonormale basissen |ki en waarbij de bijdrage van de basisgolffuncties gekarakteriseerd wordt via de co¨effici¨enten ck . 19
Door de normalisatie-eis k |ψi k2 ≡ 1 X = |ck |2
(2.3)
k
=
X
ck ck
k
kunnen we |ck |2 beschouwen als een klassieke waarschijnlijkheid om voor een kwantumsysteem in toestand |ψi de waarneembare toestand k (met toestandsvector |ki) waar te nemen.
2.1.1
De berekeningsbasis van een kwantumregister
In Definitie 1.3 definieerden we het begrip observable als een basis voor de ruimte waarin we het kwantumsysteem beschouwen. De observable matrix A van een n-bit kwantumregister in de berekeningsbasis is gewoon A = diag(0, 1, 2, . . . , 2n − 1).
(2.4)
De eigenwaarden van het systeem zijn simpelweg de klassieke getallen die we met n bits kunnen voorstellen. De berekeningsbasis van de Hilbert-ruimte is hierdoor de canonieke basis 0 0 1 0 1 0 (2.5) H = span .. , .. , . . . , .. . . . 1 0 0 = span{|0i , |1i , . . . , |2n − 1i}.
We noemen de toestandsvectoren |ki = |0i , |1i , . . . , |2 n − 1i de basistoestanden, ze zijn tevens ook de eigenvectoren xk van A. De spectrale ontbinding van A is dan X X X λk |ki hk| = λk Pk . (2.6) A= λk xk x∗k = k
k
k
De rang 1 matrices Pk = |ki hk| zijn projectoren op de deelruimten H k van de Hilbert-ruimte H = tumregister leeft.
(2.7) N
k
Hk waarin het kwan-
Notatie. Wanneer we in het vervolg een toestandsvector schrijven als |ki, dan bedoelen we steeds de eigenvector behorende bij de fysisch waarneembare toestand k. Dit is een vector met op index k een 1 en voor de rest allemaal nullen. Wanneer we het over willekeurige toestandsvectoren hebben schrijven we meestal |ψi.
20
2.1.2
Alternatieve basissen
De basis die we kiezen om een kwantumregister te meten wordt bepaald door het fysische proces dat de meting uitvoert. Zo kunnen we bijvoorbeeld de spin van een deeltje in drie richtingen meten (x, y en z) ten opzichte van een polarisatieveld. Voor kwantumalgoritmen hebben we normaal voldoende aan de berekeningsbasis. Kwantumprotocollen maken soms wel gebruik van een verandering van basis, bijvoorbeeld het teleportatie-protocol. We kunnen de toestandsvector door een kwantumberekening (eigenlijk het toepassen van enkele unitaire transformaties, zie verder in §4) roteren in de Hilbert-ruimte en dan een meting doen ten opzichte van de berekeningsbasis om zo hetzelfde effect te bekomen [42].
2.1.3
Mogelijke configuraties van een toestandsvector
Zoals we in §1.4 gezien hebben kan een toestandsvector zich in verschillende configuraties bevinden. We kunnen de verzameling van alle toestandsvectoren Ψ opdelen in volgende klassen (de benamingen van de verzamelingen zijn niet standaard omdat ik nergens een expliciete opdeling ben tegengekomen): Basistoestanden (Λ). Voor een kwantumregister dat zich in een basistoestand bevindt is er geen verschil met een klassiek register: het bevat ´e´en enkele waarde k. E´en co¨effici¨ent ck heeft dan een amplitude van 1, de rest 0, en we bevinden ons in een basistoestand |ki met eigenwaarde k. Superposities (Υ). Wanneer er meerdere c k 6= 0 zijn, zeg r, dan staat het kwantumregister in een superpositie van r verschillende basistoestanden. Het kwantumregister bevat dan tegelijkertijd al deze r getallen. Bij observatie in de berekeningsbasis projecteren we het register op ´e´en van de mogelijke r basistoestanden met waarschijnlijkheid |c k |2 . Scheidbare superposities (Π). Indien de superpositie kan voorgesteld worden door op de klassieke manier r aparte registers te vullen met de getallen die in superpositie staan, dan is de toestand scheidbaar. We kunnen de superpositie dan schrijven als een tensorproduct in de onderliggende Hilbert-ruimten. Verstrengelde superposities (Γ). Een kwantumregister dat een superpositie bevat kan ook verstrengeld zijn. We bedoelen dan dat er minstens twee deelsystemen met elkaar verstrengeld zijn en dat observatie van het ene deelsysteem het andere op een niet-klassieke manier zal be¨ınvloeden (de zogenaamde kwantumcorrelatie). Het is dan noodzakelijk om de superpositie als een som te schrijven. Samengevat hebben we de verzameling van alle toestandsvectoren |ψi ∈ Ψ = H, met Ψ de Hilbert-ruimte van het kwantumregister, Ψ=Λ∪Υ dat de unie is van de basistoestanden |ki ∈ Λ en de algemene superposities De verzameling van de superposities Υ Υ=Π∪Γ 21
(2.8) P
k ck
|ki ∈ Υ. (2.9)
Ψ
Υ Π
Γ P
k ck
|ki
⊗i |ii
Λ |0i |2i
|1i
Figuur 2.1: Configuraties van een toestandsvector (pure toestanden) N N is de unie van de scheidbare superposities i |ii ∈ Π met |ii ∈ Hi en H = i Hi en de verstrengelde superposities Γ. Het totaalbeeld is te zien in Figuur 2.1.
2.1.4
Alternatieve voorstellingswijzen voor een kwantumtoestand
De amplitudevoorstelling is niet de enige manier waarop we een kwantumtoestand kunnen beschrijven. Een alternatieve voorstellingswijze is het stabilisator-formalisme [27]. In dit formalisme beschouwt men de n-voudige tensorproducten van de Pauli-matrices σ x , σy , σz en de eenheidsmatrix I2 als generatoren voor een Pauli-groep P n (samen met de scalars 1 en i). In deze groep zijn er bepaalde toestanden die gestabiliseerd worden door een deelgroep van Pn . De verzameling van deze toestanden noemen we S. Elementen in S kunnen beschreven worden in poly(n) en ook alle basistoestanden bevinden zich in S. De elementen die niet in S zitten hebben echter een exponenti¨ele beschrijving. Bij de amplitudevoorstelling kunnen we eenzelfde vaststelling doen: verstrengelde superposities (toestanden in Γ) hebben een exponenti¨ele beschrijving, de andere toestandsvectoren kunnen we polynomiaal beschrijven (hier gaan we in §6 verder op in). Het vreemde is echter dat S 6= Ψ − Γ. (2.10) We vermelden dit alleen maar omdat we in de verdere tekst meermaals verstrengeling doen uitschijnen als het belangrijkste ingredi¨ent voor de kracht van kwantumalgoritmen en de oorzaak van de exponenti¨ele kost bij simulatie. De eigenschap van verstrengeling prop(E) is de oorzaak van de exponenti¨ele simulatiekost bij gebruik van de amplitudevoorstelling. Verstrengeling heeft misschien echter geen alleenrecht! We besluiten dat als een kwantumalgoritme exponentieel sneller wil zijn dan zijn klassieke tegenhangers, het alle eigenschappen prop(D i ) moet hebben, om in eender welk wiskundig formalisme A voor kwantumtheorie, ergens een eigenschap prop(D A ) te vertonen waarvoor bij klassieke simulatie een exponenti¨ele kost nodig is [27].
2.2
Pure en gemengde toestanden
In kwantummechanica maakt men een onderscheid tussen ‘pure toestanden’ en ‘gemengde toestanden’, in het Engels mixed states. Een toestandsvector |ψi kan alleen maar een pure 22
toestand voorstellen. Tot hiertoe hebben we het daardoor enkel maar gehad over pure toestanden. Een eerste begrip dat we moeten invoeren is de densiteitsmatrix van een kwantumtoestand.
2.2.1
De densiteitsmatrix
Aan een pure toestand, voorgesteld door een toestandsvector |ψi (met norm 1), kunnen we eenduidig een densiteitsmatrix ρ koppelen in de ruimte van de densiteitsmatrices D(H) behorende bij de Hilbert-ruimte H: ρ = |ψi hψ| ∈ D(H)
en |ψi ∈ H.
(2.11)
De densiteitsmatrix ρ is een Hermitiaanse positieve rang 1 matrix gevormd door het uitwendig product van de toestandsvector |ψi met zichzelf. De diagonaalelementen ρ k,k geven (bij een pure kwantumtoestand) de kans aan om basistoestand |ki aan te treffen. Het spoor van ρ is 1: we hebben 100% kans om het systeem in ´e´en van de mogelijke toestanden aan te treffen. De waarschijnlijkheid om zich in een bepaalde basistoestand |ki te bevinden kunnen we berekenen als Prob[|ki] = trace(ρ Pk ),
(2.12)
met Pk = |ki hk| de orthogonale projector op deelruimte H k , opgespannen door de basistoestand |ki, van de Hilbert-ruimte H van het kwantumregister. We kunnen op een gelijkaardige manier de verwachtingswaarde van een meting defini¨eren als E[|ψi] = trace(ρ A),
(2.13)
met A de observable matrix van het systeem. Dit is niets anders dan het gemiddelde van de afzonderlijke waarschijnlijkheden (2.12). De verwachtingswaarde wordt verder in deze tekst niet meer gebruikt, maar is belangrijk bij bijvoorbeeld een NMR-kwantumcomputer waar het onmogelijk is om maar ´e´en kwantumcomputer (= ´e´en molecule) te gebruiken. Bij een meting krijgt men dan het gemiddelde van alle resultaten. Het aantal moleculen bij de 7-bit NMR-kwantumcomputer van IBM was bijvoorbeeld van grootteorde 10 18 [46].
2.2.2
Observatie van een pure toestand
Aan de hand van de densiteitsmatrix kunnen we het begrip observatie opnieuw uitdrukken. We herschrijven eerst (2.12) tot Prob[|ki] = trace(ρ Pk ) = hψ|Pk |ψi .
(2.14)
Het bewijs voor deze gelijkheid is terug te vinden in [36]. We kunnen nu de observatie van een kwantumregister herformuleren en krijgen na detectie van een basistoestand |ki de nieuwe toestand |ψ 0 i =
Pk |ψi
(hψ|Pk |ψi)1/2 23
.
(2.15)
Merk op dat we het in Definitie 1.7 (observatie van een kwantumregister) enkel hebben over de observatie van een specifieke bit j, terwijl we (2.15) op het eerste gezicht zouden lezen als de observatie van een basistoestand uit de berekeningsbasis van het kwantumregister. Dat hoeft echter niet het geval te zijn. De in (2.7) gedefinieerde projectoren zijn opgesteld aan de hand van de berekeningsbasis van het kwantumregister. Met andere woorden, we projecteren de toestandsvector op een deelruimte van de Hilbert-ruimte N H = k Hk , (2.16)
met k = 0 . . . (2n − 1), de eigenwaarden van het kwantumregister. We kunnen echter ook (0) andere projectie-operatoren defini¨eren. Bijvoorbeeld de projectie Pj die een 0 meet voor de bit met index j: N N 1 0 (0) ⊗ ( l I2 ) Pj = ( h I2 ) ⊗ 0 0 N N = ( h I2 ) ⊗ P (0) ⊗ ( l I2 ) , (2.17) met h de bits met hogere indexen en l de bits met lagere indexen dan j. We gebruiken P (0) = |0i h0| en P (1) = |1i h1| om de projectie-operatoren voor ´e´en kwantumbit aan te duiden.
Voorbeeld 2.1. We beschouwen een 3-bit kwantumregister |ψi = |x 2 , x1 , x0 i in de toestand √1 2
|110i + 12 |111i √ T = 1/2 0 0 0 0 0 1/ 2 1/2 . 1 2
|ψi =
|000i +
(2.18)
We berekenen eerst de kansen voor de berekeningsbasis {0 . . . 7} van het kwantumregister. Prob[|0i] = hψ|P 0 |ψi 1 * 0 = ψ .. .
0 = c0 c0 = |c0 |2 = 1/4
ψ
+
Prob[|1i] = hψ|P1 |ψi = c1 c1 = |c1 |2 = 0 .. .
Prob[|5i] = hψ|P5 |ψi = c1 c1 = |c1 |2 = 0 Prob[|6i] = hψ|P6 |ψi = c6 c6 = |c6 |2 = 1/2 Prob[|7i] = hψ|P7 |ψi = c7 c7 = |c7 |2 = 1/4
We bekomen uiteraard de kansen die we rechtstreeks uit (2.18) konden aflezen. De kansverdeling voor x1 kunnen we nu op dezelfde manier uitrekenen met (0)
Prob[|0i1 ] = hψ|P1 |ψi , waarbij (0)
P1
= I2 ⊗ P (0) ⊗ I2 1 1 0 0 = 1 1 0 24
0
.
(0)
We krijgen het verwachte resultaat; P 1
projecteert enkel de co¨effici¨enten waarvoor x1 nul is:
Prob[|0i 1 ] = c0 c0 + c1 c1 + c4 c4 + c5 c5 = c000 c000 + c001 c001 + c100 c100 + c101 c101 = 1/4. Indien we nu bij een meting op x1 in het niet erg waarschijnlijke geval 0 terechtkomen, kunnen we de nieuwe toestand van het kwantumregister schrijven als: (0)
|ψ 0 i =
P1 |ψi
1/2 (0) hψ|P1 |ψi √ T = 4 1/2 0 0 0 0 0 0 0 T = 1 0 0 0 0 0 0 0 = |000i .
♦
2.2.3
Gemengde toestanden
Het ideale geval: totale isolatie Tot hiertoe hebben we het eigenlijk steeds gehad over een compleet ge¨ısoleerd kwantumsysteem S beschreven door een toestandsvector |ψi ∈ H S . In zo een systeem kunnen we verschillende onafhankelijke (niet verstrengelde) deelsystemen |ψ i i hebben. Het volledige systeem is dan te beschrijven als een tensorproduct: N |ψi = i |ψi i met |ψi i ∈ Hi . (2.19)
Voor een 3-bit kwantumregister |x2 , x1 , x0 i ziet een scheidbare toestand over H 2 ⊗ H1 ⊗ H0 = HS er altijd uit als |ψi = |ψ2 i ⊗ |ψ1 i ⊗ |ψ0 i . (2.20)
Bijvoorbeeld de toestanden |0i ⊗ |0i ⊗ |1i en |0i ⊗ |1i ⊗ verstrengeld zijn, moeten we hun toestand samennemen:
√1 (|0i 2
+ |1i). Indien bits 0 en 1
|ψi = |ψ2 i ⊗ |ψ1,0 i . (2.21) p √ √ Bijvoorbeeld de toestanden |0i ⊗ (1/ 2 |00i + 1/ 2 |11i) en |0i ⊗ (1/3 |01i ⊗ 2/3 |10i). Enzovoorts... Zolang we deelsystemen |ψi i enkel maar met andere deelsystemen |ψ j i uit HS verstrengelen kunnen we de toestand volledig blijven beschrijven door een toestandsvector met maximaal 2n complexe co¨effici¨enten. Het maximum wordt bereikt P bij totale verstrengeling wanneer we 2n −1 de toestand alleen nog maar kunnen schrijven als |ψi = k=0 ck |ki ∈ Γ. 25
De werkelijkheid: geen totale isolatie Volgens de derde hoofdwet van de thermodynamica is een volledig ge¨ısoleerd systeem echter niet mogelijk. We zullen op ´e´en of andere manier de omgeving van het systeem mee in rekening moeten brengen indien we een model van de werkelijkheid nastreven. Een beschrijving alleen maar in HS kan onvolledig worden wanneer er interactie is geweest met de omgeving. Het systeem S en zijn omgeving W kunnen namelijk verstrengeld raken! Ook zullen complexe interacties met de omgeving (zoals observaties) de wereld doen splitsen en coherente superposities in het systeem vernietigen: dit noemt men decoherentie. Om S toch volledig te beschrijven hebben we een toestandsvector nodig in HT = H W ⊗ H S .
(2.22)
Het probleem is natuurlijk dat we deze ruimte T onmogelijk kunnen karakteriseren. Bijvoorbeeld voor de NMR-kwantumcomputer van IBM zouden we dan de kwantumtoestand van het labo in rekening moeten brengen, en daardoor de kwantumtoestand van Californi¨e, enzovoorts... Ook de onderzoekers bevinden zich natuurlijk in de wereld rond de proefopstelling en raken verstrengeld: hierdoor zal de toestand waar we het systeem in beschouwen een projectie zijn in de Hilbert-ruimte waarin we zelf leven (´e´en van de werelden volgens MWI), enzovoorts... Definitie Doordat we ontbrekende informatie hebben, kunnen we de toestand van het kwantumsysteem niet volledig beschrijven als ´e´en enkele toestandsvector. We zullen daarom meerdere toestandsvectoren gebruiken met elk een bepaalde klassieke waarschijnlijkheid. We verwachten dat het kwantumsysteem ρ zich in ´e´en van de mogelijke pure toestanden |ψ i i bevindt met een klassieke waarschijnlijkheid p i . Definitie 2.1 (Gemengde toestand). Een gemengde n-ledige toestand ρ is een strikt convexe combinatie van n pure toestanden Pn n i=1 pi = 1 X pi |ψi i hψi | met 0 > pi > 1 . (2.23) ρ= i=1 pi ∈ R
De ρ uit (2.23) is in feite een gereduceerde densiteitsmatrix met effecten uit de omgeving. Met elke toestandsvector stemt een densiteitsmatrix overeen, zie (2.11). Het omgekeerde is echter niet waar: er zijn densiteitsmatrices die je niet als toestandsvector kan schrijven, de zogenaamde gemengde toestanden die we net hebben gedefinieerd in (2.23). Superpositie van toestanden 6= gemengde toestanden Het onderscheid tussen pure en gemengde kwantumtoestanden is nogal verwarrend: er zijn nu twee maten om waarschijnlijkheden aan te duiden die door elkaar gebruikt worden, namelijk de complexe amplitudes ck en de klassieke waarschijnlijkheden p i . Dit zorgt voor de 26
decoherentie
superpositie
open doos
gemengd
basistoestand
Figuur 2.2: Superpositie en gemengde toestanden bij de kat van Schr¨odinger (naar [45]) nodige verwarring in teksten die handelen over kwantumcomputers, daar de auteurs meestal geen algemene achtergrondkennis hebben van kwantumtheorie. Zo trof ik in de documentatie van verschillende simulatoren de term ‘gemengd’ (mixed) aan wanneer het een toestand betrof die gewoon de superpositie van een aantal toestanden was en ‘puur’ wanneer het om een basistoestand uit de berekeningsbasis ging, o.a. in [44]. Deze verwarring duikt zelfs op in wetenschappelijke(?) artikels op de Los Alamos eprint-server doordat het terrein bevolkt wordt door wetenschappers met verschillende achtergrondkennis: wiskundigen, fysici, computerwetenschappers en elektronici. Er zijn trouwens wel meer fouten te vinden in de grote hoeveelheid (ongepubliceerde) online artikels, zo vind je in [6] een klein overzicht van een aantal verkeerde of misleidende artikels die handelen over Grover’s zoekalgoritme. Het was dan ook niet moeilijk om gemengde toestanden met verstrengelde superposities te verwarren bij een eerste exploratie van het onderzoeksgebied.
2.2.4
De kat van Schr¨ odinger herbekeken
Bij het verhaal van de kat van Schr¨odinger in §1.5.1 hebben we reeds de opmerking gemaakt dat we de kat in feite moeten beschouwen als een gemengde toestand en de toestand van het kwantumsysteem als een superpositie. In Figuur 2.2 is het verloop van de toestand schematisch weergegeven. Het kwantummechanische activeringsmechanisme bevindt zich bij de start van het experiment in een coherente superpositie van ‘radioactief verval’ en ‘geen radioactief verval’. Wanneer de geigerteller uiteindelijk een alpha-deeltje meet en dus het radioactief verval vaststelt, wordt de superpositie uit elkaar getrokken: we noemen dit decoherentie van de superpositie. De wereld van het kwantumsysteem splitst zich in twee werelden: in de ene wacht de kat nog bang af wat er gebeurt, in de andere wordt de kat vermoord. Voor een buitenstaander die niet weet wat er in de doos gebeurt, is er gewoon een klassieke waarschijnlijkheidsfunctie die aangeeft wat er met de kat gebeurt. Hij heeft onvolledige informatie en beschrijft de totale toestand als een gewogen som van de mogelijke toestanden. 27
We noemen dit een gemengde toestand. Wanneer de buitenstaander uiteindelijk de doos opent, kan hij ´e´en van de twee mogelijke uitkomsten van het experiment schrappen door rechtstreeks bewijs. We stellen vast dat er een verschil is tussen microscopische systemen en macroscopische systemen [40]. De kat is een macroscopisch object en heeft een sterke koppeling met zijn omgeving. Elke mogelijke (coherente) superpositie in de kat wordt bijna onmiddellijk vernietigd door een (complexe) interactie met de omgeving van de kat. Met andere woorden, de coherentietijd voor een macroscopisch object zoals bijvoorbeeld een kat is 0. We kunnen de decoherentie van de toestand van de kat ook nog anders formuleren. Door de interactie tussen de kat en zijn omgeving, krijgt de kat informatie over zijn eigen toestand. Wanneer er genoeg omgevingsinformatie is om de toestand van de kat vast te leggen, is er geen reden meer om de kat in superpositie te plaatsen. De omgevingsinformatie is echter niet bekend wanneer we het over een afgeschermd systeem hebben en daarom moeten wij de kat beschrijven als een statistische mengeling van toestanden. Voor microscopische systemen (´e´en kwantum) is de coherentietijd van een superpositie even lang als de levenstijd van het systeem. Voor macroscopische systemen (bv. de kat) is de coherentietijd 0. En voor mesoscopische systemen (enkele deeltjes) kunnen we de coherentietijd experimenteel vaststellen. Voor de ge¨ınteresseerde lezer verwijzen we naar ‘§3.6. What is the problem? (Is there a problem?)’, pagina’s 124–133, van [38] en ook naar [11] waar heel het probleem nog eens duidelijk in het licht van MWI wordt behandeld. Om volledig correct te zijn zouden we in Figuur 1.3 moeten schrijven: |kati =
2.2.5
p0
|vervaliatoom
|doodikat
|besef doodiik
p1
|geen vervaliatoom |levendikat |besef levendiik
+
(2.24)
Gereduceerde densiteitsmatrices
We veronderstellen dat we een kwantumsysteem hebben dat uit twee deelsystemen A en B bestaat ρA,B ∈ D(HA ⊗ HB ). (2.25) Veronderstel nu dat we enkel maar systeem A kunnen beschouwen en dat systeem B een onobserveerbare toestand is, bijvoorbeeld omdat systeem B zich op een verre plaats bevindt. We hebben dan enkel maar de beschikking over een gereduceerde densiteitsmatrix ρ A om systeem A te beschrijven. Deze toestand kunnen we wiskundig voorstellen als het parti¨ele spoor van ρA,B waarbij we enkel informatie van systeem A uit ρ A,B trekken: ρA = traceB (ρA,B ).
(2.26)
We zullen eerst duidelijk maken wat het parti¨ele spoor juist doet. Stel ρA ∈ C2×2 en ρB ∈ C4×4 en een densiteitsmatrix die een zuiver tensorproduct is van de twee ρA1,1 · ρB ρA1,2 · ρB . (2.27) ρA,B = ρA ⊗ ρB = ρA2,1 · ρB ρA2,2 · ρB 28
We kunnen eenvoudig achterhalen waar de informatie van systeem A zich zou bevinden indien systeem B niet bestond: 1 2 1 2 1 2 1 2 1 2 . ⊗ I4 = (2.28) 3 4 3 4 3 4 3 4 3 4 Op dezelfde manier vinden we de posities voor systeem B: 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 13 14 15 16 . = I2 ⊗ 1 2 3 4 9 10 11 12 5 6 7 8 13 14 15 16 9 10 11 12 13 14 15 16
(2.29)
Om de parti¨ele densiteitsmatrix ρA te bekomen moeten we de elementen met hetzelfde nummer in (2.28) optellen zodat we een 2 × 2 matrix bekomen. Voor ρ B doen we hetzelfde en bekomen we een 4 × 4 matrix. In het Engels noemt men het parti¨ele spoor ook wel eens de trace out operator, omdat we de densiteitsmatrix van het samengestelde systeem reduceren naar een densiteitsmatrix die schijnbaar maar ´e´en van de twee systemen beschouwt. In (2.26) negeren we deelsysteem B door het weg te tracen. Voor een toestand ρ A,B die uit twee deelsystemen bestaat kunnen we schrijven: ρA,B ∈ D(HA ⊗ HB ) ρA = traceB (ρA,B ) ρ ∈ D(HA ) . (2.30) met ρB = traceA (ρA,B ) A ρB ∈ D(HB )
2.3
Verstrengeling van toestanden
We hebben in §2.1.4 opgemerkt dat verstrengeling van kwantumtoestanden, prop(E), de belangrijkste eigenschap is voor de amplitudevoorstelling. Verstrengeling van kwantumtoestanden zorgt ervoor dat we een exponenti¨ele geheugencomplexiteit en hiervan afhankelijke tijdscomplexiteit hebben bij simulatie. Het is dus belangrijk om verstrengeling te herkennen en aan te kunnen duiden hoe sterk een bepaald deelsysteem verstrengeld is met een ander deelsysteem. Hoe beter we deze eigenschap begrijpen, hoe beter we er rekening mee kunnen houden bij het ontwerpen van een kwantumcomputersimulator. We delen de mogelijke toestanden (pure en gemengde) nu op in twee grote groepen: 29
• de niet verstrengelde (scheidbare) toestanden, of disentangled states: hierin zitten de klassen Λ en Π; • en de verstrengelde toestanden, of entangled states. Er is momenteel heel wat theoretisch onderzoek aan de gang naar verstrengeling van kwantumsystemen [19, 20, 25, 31, 48]. Men onderzoekt o.a. hoe men de hoeveelheid van verstrengeling het best kan uitdrukken, hoe men verstrengeling van meerdere deelsystemen kan karakteriseren en hoe men de hoeveelheid verstrengeling kan manipuleren. Het grootste deel van deze onderzoeken focust zich momenteel op het scheiden van gemengde toestanden: dit kadert in het onderzoeksgebied van kwantuminformatietheorie. De onderzoeken zijn nog volop aan de gang en er zijn nog zeer veel open vragen. Het geval van tweeledige pure toestandsverstrengeling is al wel voldoende onderzocht en we zullen dit dan ook bekijken nadat we besproken hebben aan welke eisen een maat voor de hoeveelheid verstrengeling in een toestand moet voldoen. In het nu volgende stuk wordt er gesproken over operaties die uitgevoerd kunnen worden op een kwantumtoestand. Dit wordt echter pas behandeld in §4. Voorlopig is het voldoende te weten dat die operaties kunnen voorgesteld worden door een matrix. Deze matrix is unitair voor reversibele bewerkingen, zoals bijvoorbeeld kwantumpoorten.
2.3.1
Algemene vereisten voor het ‘meten’ van verstrengeling
We defini¨eren een functie E die de hoeveelheid van verstrengeling van een toestand ρ ∈ D(HA ⊗ HB ) afbeeldt op een re¨eel getal: E : D(HA ⊗ HB ) → R.
(2.31)
Om een goede maat voor verstrengeling te zijn zal de functie E moeten voldoen aan de volgende voorwaarden [10, 37]: 1. Voor scheidbare toestanden en basistoestanden zijn er geen kwantumcorrelaties, dus E(ρsep ) = 0
met ρsep ∈ D(Λ ∪ Π).
(2.32)
2. Lokale reversibele operaties (afgekort als LUO van local unitary operations) mogen geen invloed hebben op de hoeveelheid verstrengeling omdat we kwantumcorrelatie juist beschouwen als een soort ‘niet-lokale correlatie’. Als we de lokale operaties U A en UB toepassen op de twee afzonderlijke deelsystemen, mag E niet wijzigen: E((UA ⊗ UB ) ρ (UA ⊗ UB )∗ ) = E(ρ).
(2.33)
De uitdrukking (UA ⊗UB ) ρ (UA ⊗UB )∗ betekent gewoon dat we UA en UB lokaal hebben toegepast op de respectievelijke deelsystemen. 3. We kunnen ook een bredere klasse van lokale operaties beschouwen die niet reversibel hoeven te zijn (afgekort als LO van local operations), bijvoorbeeld een meting van ´e´en 30
E E5
E1 E2
E4 E3
Figuur 2.3: Verdeling van verstrengeling door LOCC (naar [37]) van de twee systemen. In het geval van een LO kan de totale verstrengeling niet stijgen, maar wel dalen (zie bijvoorbeeld Voorbeeld 2.1). Dus: X E(ρ) ≥ pi E(ρi ), (2.34) i
met in het rechterlid de verwachte hoeveelheid van verstrengeling van alle mogelijke uitkomsten van de complexe interactie (bijvoorbeeld een meting) gewogen door de waarschijnlijkheid van die uitkomst. Dit zijn met andere woorden de situaties in de verschillende werelden volgens MWI of de verdeling van verstrengeling over andere deelsystemen waarmee interactie geweest is, zie Figuur 2.3. Dit wil niet zeggen dat het totaal onmogelijk is om van een verstrengelde toestand een meer verstrengelde toestand te maken door middel van LOCC (local operations and classical communication) [37]. We lezen dan (2.34) alsof we een bepaalde kans p i hebben om meer verstrengeling te verkrijgen, maar men kan even goed in een andere situatie terechtkomen en minder verstrengeling bekomen. 4. Verstrengeling is additief als er geen verstrengeling is tussen de twee deelsystemen waaruit het systeem bestaat: E(ρ) = E(ρA ) + E(ρB )
2.3.2
als ρ = ρA ⊗ ρB .
(2.35)
Verstrengeling bij pure toestanden
Pure tweeledige toestanden: verstrengelingsentropie De eerste maat voor verstrengeling die we bespreken is de verstrengelingsentropie of entropy of entanglement. De verstrengelingsentropie wordt algemeen als de perfecte maat gezien als het gaat over pure tweeledige toestanden [19, 37]. De verstrengelingsentropie wordt gedefinieerd als de von Neumann entropie S van de gereduceerde dichtheidsoperator van ´e´en van de twee deelsystemen, bijvoorbeeld σ A . Voor pure toestanden blijkt het echter niet uit te maken welke gereduceerde dichtheidsmatrix je neemt. We bekomen hetzelfde resultaat als we σ B zouden kiezen.
31
Definitie 2.2 (Verstrengelingsentropie). Voor een (pure) toestand σ, die bestaat uit twee afzonderlijke delen A en B, is de verstrengelingsentropie gedefinieerd als EE
= S(σA ) = − trace(σA log2 σA ) = S(σB ) = − trace(σB log2 σB ) .
(2.36)
De logaritmen in de formule van de von Neumann entropie zijn matrixlogaritmen en kunnen we in dit geval steeds berekenen via een eigenwaardenontbinding, analoog aan de exponentiatie in Bijlage B. Voorbeeld 2.2. We bekijken twee gevallen: ´e´en zonder verstrengeling en ´e´en met maximum verstrengeling (een EPR-paar). • We beschouwen een kwantumregister in de toestand |ψi = |0i ⊗
√1 (|0i 2
+ |1i) =
√1 2
(|00i + |01i),
(2.37)
met als densiteitsmatrix σ = |ψi hψ| = 1/2 ( (|00i + |01i) (h00| + h01|) ) = 1/2 (|00i h00| + |00i h01| + |01i h00| + |01i h01|) 1 1 0 0 1 1 0 0 = 1/2 0 0 0 0 . 0 0 0 0
(2.38)
De gereduceerde dichtheidsmatrices zijn: 1 0 σA = traceB (σ) = 0 0
(2.39)
EE (σ) = S(σ) = − trace(ρ A log 2 ρA ) P = − i λi log2 λi = −1 log 2 (1) = 0.
(2.40)
De twee deelsystemen zijn natuurlijk bit 1 en bit 0 uit ons kwantumregister met bit 1 deelsysteem A en bit 0 deelsysteem B: |x 1 , x0 i = |ψA , ψB i. en
1 1 σB = 1/2 . 1 1
We kunnen nu de verstrengelingsentropie berekenen:
• We beschouwen een maximaal verstrengelde toestand σ met toestandsvector |ψi =
√1 2
(|00i + |11i),
de densiteitsmatrix is dan σ = |ψi hψ| = 1/2 ( (|00i + |11i) (h00| + h11|) ) = 1/2 (|00i h00| + |00i h11| + |11i h00| + |11i h11|) 1 0 0 1 0 0 0 0 = 1/2 0 0 0 0 . 1 0 0 1 32
(2.41)
(2.42)
De gereduceerde dichtheidsmatrices zijn: 1 0 σA = traceB (σ) = 1/2 0 1
en
1 0 . σB = 1/2 0 1
(2.43)
We kunnen nu de verstrengelingsentropie berekenen: EE (σ) = S(σ) = − trace(ρ A log 2 ρA ) P = − i λi log 2 λi = −1/2 log 2 (1/2) − 1/2 log 2 (1/2) = 1.
(2.44)
♦ Pure tweeledige toestanden: Schmidt-decompositie Er is nog een tweede manier om na te gaan of een pure tweeledige toestand verstrengeld is: de Schmidt-decompositie van een toestand [38]. We kunnen een willekeurige vector over HA ⊗ HB namelijk steeds schrijven als X X |ψiA,B = ai,j |iiA |jiB ≡ |iiA |˜iiB , (2.45) i,j
i
met {|iiA } en {|jiB } orthonormale basissen voor HA en HB . Voor de tweede gelijkheid hebben we de basis voor B herschreven als X |˜iiB ≡ ai,j |jiB . (2.46) j
De basis voor A veronderstellen we zo gekozen dat ρ A gediagonaliseerd kan worden als X ρA = traceB (|ψiA,B A,B hψ|) = pi |iiA A hi| . (2.47) i
Door wat rekenwerk kan men nu aantonen dat de basis {|˜iiB } orthogonaal is [38] en we kunnen ze orthonormaal maken door een herschaling −1/2
|i0 iB = pi
|˜iiB .
(2.48)
Op deze manier krijgen we de Schmidt-decompositie: X√ |ψiA,B = pi |iiA |i0 iB .
(2.49)
Uit (2.49) kunnen we nu ook de gereduceerde dichtheidsmatrix voor ρ B halen: X ρB = traceA (|ψiA,B A,B hψ|) = pi |i0 iB B hi0 | .
(2.50)
i
i
Indien we (2.47) en (2.50) vergelijken merken we op dat ze dezelfde eigenwaarden (6= 0) hebben. De mate van verstrengeling in een pure tweeledige toestand |ψi A,B kunnen we uitdrukken aan de hand van het Schmidt-nummer. 33
Definitie 2.3 (Schmidt-nummer). Aan elke pure tweeledige toestand |ψi A,B kunnen we een Schmidt-nummer koppelen. Dit is het aantal eigenwaarden van ρ A (of ρB ) verschillend van nul. Het Schmidt-nummer voldoet echter niet aan de eisen die we gesteld hebben in §2.3.1. Aan de eisen 2, 3 en 4 is niet voldaan. Verder is het niet mogelijk om aan de hand van het Schmidt-nummer te weten welke toestand meer verstrengeld is dan een andere, bijvoorbeeld: p |ψε i = 1 − 2|ε|2 |00i + ε |11i + ε |22i , (2.51) heeft Schmidt-nummer 3 voor all |ε| > 0. Is het daarom meer verstrengeld dan een maximaal verstrengeld EPR-paar? Niet altijd. Pure n-ledige toestanden Ook voor pure n-ledige toestanden zouden we graag de hoeveelheid van verstrengeling uitdrukken. Voor sommige toestanden kunnen we de toestandsvector schrijven als X |ψiA,B,...,Z = λi |iiA |iiB . . . |iiZ , (2.52) i
met |iiA , |iiB ,. . . ,|iiZ een orthonormale basis voor elk deelsysteem zoals in de Schmidtdecompositie. De toestanden die we zo kunnen schrijven noemt men m-orthogonaal. Voor deze toestanden kunnen we de verstrengelingsentropie defini¨eren als X S=− λ2i log2 λ2i .
(2.53)
i
Maar dit is niet mogelijk voor eender welke pure n-ledige toestand en hierdoor niet zo bruikbaar.
2.3.3
Verstrengelingsmaten voor gemengde toestanden
Bij pure toestanden is het mogelijk om een absoluut cijfer toe te kennen aan de verstrengeling, bij gemengde toestanden is dit niet het geval. Bij een gemengde toestand zijn er verschillende manieren om de hoeveelheid van verstrengeling te berekenen, de ene al nuttiger dan de andere, afhankelijk van de situatie. Dit komt omdat je een gegeven gemengde densiteitsmatrix ρ op oneindig veel manieren kan zien als de samenstelling van pure toestanden [19], wat zeer duidelijk is als je (2.23) bekijkt. Een mogelijke definitie is de formatieverstrengeling die uitdrukt hoeveel verstrengeling we nodig hebben om een bepaalde verstrengelde (gemengde) toestand te maken volgens het principe van Figuur 2.3. We schrijven de formatieverstrengeling als X EF (σ) = min pi EE (|ψi i hψi |). (2.54) Eρ
i
We minimaliseren over alle mogelijk decomposities van een gemengde densiteitsmatrix. Dit maakt de formatieverstrengeling dan ook zeer moeilijk te berekenen. 34
T
Ψ
D
NPT PPT
ρ∗ |
σ
{z
D(σ||ρ∗)
D
}
(b) Geometrische kwantificatie (naar [37])
(a) PPT en NPT (naar [19] en [2])
Figuur 2.4: Verstrengeling van gemengde toestanden Om verstrengeling van een gemengde toestand te kunnen berekenen is het noodzakelijk dat we de gemengde toestand kunnen scheiden in een samenstelling van pure toestanden. Als hulpmiddel gebruikt men hiervoor een onderverdeling in positieve parti¨ele transposes (PPT) en negatieve parti¨ele transposes (NPT). Een parti¨ele transpose is een transpose in ´e´en van de deelsystemen zoals we gezien hebben bij de parti¨ele densiteitsmatrix voor een deelsysteem. De parti¨ele transpose ten opzichte van deelsysteem B in een tweeledig systeem met componenten A en B is dus: ρΓB = (IA ⊗ TB ) ρ. Aan de hand van de PPT-eigenschap toonden A. Peres en nadien M. Horodecki, P. Horodecki en R. Horodecki twee eigenschappen aan om voor 2 × 2 en 2 × 3 systemen scheidbaarheid aan te tonen voor tweeledige systemen. Stelling 2.1. Als toestand ρ scheidbaar is, dan is ρ ΓA ≥ 0, met andere woorden, dan is ρ een PPT toestand. Stelling 2.2. Als ρ een PPT toestand is, ρ ΓA ≥ 0, in een Hilbert-ruimten van 2 × 2 of 2 × 3, dan is ρ scheidbaar. De toestand is grafisch voorgesteld in Figuur 2.4(a), de NPT toestanden liggen buiten de krommen. Voor 2 × 2 en 2 × 3 toestanden vallen D en PPT samen. Rond deze twee stellingen ontstaan nu heel interessante wetenschappelijke onderzoeken over positieve operatoren, compleet-positieve operatoren en scheidbaarheid van systemen. Doordat we in het verdere verloop van de tekst ons echter voornamelijk zullen concentreren op pure toestanden gaan we daar niet dieper op in. Een laatste interessante maat die we kunnen beschouwen voor verstrengeling is een geometrische afstand tot de dichtstbij gelegen niet-verstrengelde toestand, de relatieve entropie van verstrengeling, zie Figuur 2.4(b): ERE (σ) = min D(σ||ρ). ρ∈D
35
(2.55)
Ook hier zitten we weer met een minimalisatie die de maat moeilijk berekenbaar maakt, maar we kunnen hier makkelijk kiezen voor ρ = σ A ⊗ σB . De afstandsmaat die men kiest is S(σ||ρ) = trace(σ log 2 σ − σ log 2 ρ).
36
(2.56)
Hoofdstuk 3
Berekeningsmodellen 3.1
Berekeningsmodellen en kwantumcomputermodellen
Om iets uit te rekenen maken we gebruik van een bepaald berekeningsmodel. De modellen die men gebruikt voor kwantumberekeningen zijn de kwantumequivalenten van de klassieke modellen: Turing-machines, cellulaire automaten en acyclische circuits (ook wel gate arrays genoemd). Al deze klassieke modellen hebben hun kwantumequivalent. Voor een kwantum-Turingmachine of Quantum Turing machine (QTM) [13] en kwantumcircuits [14] is aangetoond dat ze dezelfde complexiteit bezitten [54]. Met andere woorden, ze kunnen dezelfde functies berekenen in polynomiale tijd. We zullen verder voor de kwantumcircuit-voorstelling kiezen omdat deze het eenvoudigst in gebruik is. De circuitvoorstelling is ook de meest gebruikte voorstelling in publicaties.
3.1.1
Een kwantum-Turing-machine
Omdat een Turing-machine een belangrijk concept is in computerwetenschappen is het een belangrijk uitgangspunt indien we het willen hebben over een niet-conventionele machine die we als ‘computer’ wensen te gebruiken. Benioff ’s reversibele Turing-machine Begin 1980 ontwikkelde Benioff een berekeningsmodel dat kwantumtoestanden gebruikte als geheugenlocaties op de band van een Turing-machine [22, 53]. De bedoeling van Benioff was een model voor reversibele berekeningen op te stellen. De unitaire evolutie van een ge¨ısoleerd kwantumsysteem was zijn motivatie voor het gebruik van qubits als geheugenelementen. (De evolutie van een kwantumsysteem wordt verderop nog behandeld in §4.1. Dit geldt voor alle opmerkingen die hier gemaakt worden over de evolutie van een kwantumsysteem.) Benioff’s aangepaste Turing-machine is geen echte kwantumcomputer. Zijn model is equivalent met een klassiek model voor reversibele berekeningen uit 1978 van Bennett. Het is niets 37
meer dan een reversibele Turing-machine die met kwantumelementen werkt. De reden waarom we deze machine niet een echte kwantumcomputer kunnen noemen is te wijten aan het feit dat na elke toestandstransitie de kwantumgeheugenmodules terug in een klassieke toestand gedrukt worden. De geheugenlocaties worden na elke stap geobserveerd om zo de volgende stap te kunnen nemen (zoals in een klassieke Turing-machine). Bij observatie van een kwantumtoestand treedt er echter verstrengeling op met de omgeving en wordt de kwantumtoestand verstoord. Het is juist dit aspect dat we wensen te gebruiken om bijvoorbeeld kwantumparallellisme uit te buiten en dat hier verloren gaat. Feynmann’s universele kwantumsimulator In 1982 bedacht Feynmann een volledig ander berekeningsmodel [22, 53]. Vanuit de observatie dat er een exponenti¨ele vertraging is bij het simuleren van een kwantumsysteem op een klassieke computer, bedacht hij dat het wellicht voordeliger zou zijn om kwantumsystemen te gebruiken bij simulatie van andere kwantumsystemen. De Feynmann-machine kan effici¨ent andere kwantumsystemen simuleren, maar het is niet mogelijk om een willekeurige berekening uit te voeren op een Feynmann-machine. Om een bepaalde berekening uit te voeren tracht men een specifieke Hamiltoniaan op te stellen. Deze Hamiltoniaan bepaalt de evolutie van het kwantumsysteem. Vandaar dat deze kwantumsimulator ook niet geldt als (universele) kwantumcomputer. Wel vermoedde Feynmann reeds dat een kwantumcomputer krachtiger zou zijn dan een klassieke computer, omdat het simuleren van andere kwantumsystemen plots wel op een effici¨ente manier (in polynomiale tijd) uitgevoerd kan worden. Hij kreeg gelijk! Deutsch’s kwantumcomputer In 1985 ontwikkelde David Deutsch het model van een universele kwantumcomputer [13]. Deutsch volgt dezelfde weg als Benioff, alleen ditmaal met het doel om een kwantumcomputer te beschrijven en niet een reversibele computer. Zo definieert hij de kwantum-Turing-machine. Definitie 3.1 (QTM). Een kwantum-Turing-machine (QTM) Q is een eindige toestandsmachine met drie componenten: • een eindige controle-eenheid: deze bestaat uit een eindig aantal qubits p i die de toestand van de machine aangeven in een Hilbert-ruimte H P P −1 HP = span{⊗i |pi i}i=0 ,
(3.1)
• een oneindig geheugen waarvan een eindig deel wordt gebruikt: dit is een oneindige reeks qubits mi die als geheugen voor de machine dienen in een Hilbert-ruimte H M HM = span{⊗i |mi i}∞ i=−∞ en
38
(3.2)
|mx−2 i
|mx−1 i
p3
|mx i
p2
p1
|mx+1 i
|mx+2 i
p0
Figuur 3.1: De kwantum-Turing-machine (QTM) van Deutsch • een lees/schrijf-kop (cursor ) voor interactie met het geheugen in een Hilbert-ruimte H C x ∈ HC = Z.
(3.3)
Een schematische voorstelling van deze QTM is te zien in Figuur 3.1. We kunnen nu een Hilbert-ruimte HQC defini¨eren waarin Q leeft: HQC = HC ⊗ HP ⊗ HM .
(3.4)
De basisvectoren in deze Hilbert-ruimte hebben dan de vorm: |x, p, mi ∈ HQC
(3.5)
en noemen we de berekeningsbasis of computational basis. De verbanden met een klassieke Turing-machine zijn eenvoudig te leggen. Het aantal mogelijke toestanden S komt overeen met de Hilbert-ruimte van de toestanden H P . Het alfabet van de Turing-machine A is de Hilbert-ruimte van een enkele qubit C 2 . En de toestandstransities van Q worden gegeven door een unitaire operator U over H QC . De kwantumtoestand van de machine na n tijdseenheden T is: |ψ(nT )i = U n |ψ(0)i (n ∈ Z+ ).
(3.6)
De operaties per tijdstap moeten natuurlijk beperkt blijven zodat we niet oneindig veel werk verzetten in ´e´en stap. De evolutie-operator U uit (3.6) moet daarom lokaal zijn – d.w.z. dat er enkel interactie is tussen naast elkaar gelegen qubits – en tijdsonafhankelijk zijn zodat de berekening een welbepaalde uitvoeringstijd heeft. De uitbreidingen op het model van Benioff zijn het toestaan van kwantumtoestanden ook na berekeningen, zodat er kwantumparallellisme en verstrengeling mogelijk is, alsook het voorstellen van de toestand van de machine en de leeskop door een kwantumtoestand. Zoals bij gewone Turing-machines kunnen we nu een universele kwantum-Turing-machine defini¨eren die als invoer ook een programma accepteert en zo willekeurige berekeningen kan verrichten. Het model van de QTM is, zoals reeds vermeld, heel complex om mee te werken. Daarbij komt nog dat het zeer onwaarschijnlijk is dat een echte implementatie van een kwantumcomputer naar dit model gebouwd kan worden; de kop van de machine is namelijk niet klassiek. Daarom werkt men meestal met kwantumcircuits. 39
|ai
|a0 i
|bi
|b0 i (a) Kwantumcircuit
(b) Klassiek circuit
Figuur 3.2: Een circuit met xor-poorten (cnot)
3.1.2
Kwantumcircuits
Een kwantumcircuit, gedefinieerd door Deutsch in [13] met een voorbeeldje in Figuur 3.2(a), is een acyclisch circuit van kwantumpoorten en is het kwantumequivalent van een klassiek logisch circuit zoals Figuur 3.2(b). In [54] wordt aangetoond (in een heel ingewikkeld bewijs) dat kwantumcircuits en QTM’s dezelfde functies kunnen berekenen in polynomiale tijd. Men zegt van een kwantumcircuit K met n invoerqubits (en n uitvoerqubits) dat het een kwantum-Turing-machine Q, (n, t)-simuleert als de waarschijnlijkheidsdistributie van de uitgang px voor een ingang x ∈ {0, 1}n na t tijdsstappen met x als invoer voor beiden gelijk is. De stelling van Yao uit 1993 gaat als volgt [54]: Stelling 3.1 (Equivalentie). Gegeven een kwantum-Turing-machine Q en twee positieve getallen n en t, dan bestaat er een kwantumcircuit K van grootte poly(n, t) die Q (n, t)simuleert. Omdat circuits nu ´e´enmaal handiger zijn om algoritmen te visualiseren zullen we ze ook daarvoor gebruiken. Het model van de QTM is dan weer bruikbaar om bepaalde computerwetenschappelijke stellingen uit te drukken voor kwantumcomputers, bijvoorbeeld het stopprobleem (halting problem). Het circuit in Figuur 3.2(a) is te lezen van links naar rechts, waarbij de horizontale lijnen de qubits voorstellen en de vreemde verticale symbolen de kwantumpoorten. Links van de tekening bevindt zich aan de ingang van de lijnen de ingangstoestand, rechts aan de uitgang de uitgangstoestand. We veronderstellen in deze tekening dat de tijd van links naar rechts loopt. In de figuur hebben we twee qubits (2 lijnen) en 3 xor-poorten (of cnot-poorten). De bewerking die het circuit uitvoert is het verwisselen van de twee ingangen.
3.2 3.2.1
De Church-Turing-hypothese De klassieke hypothese
De Church-Turing-hypothese drukt uit wat kan berekend worden, niet door een bepaalde supercomputer of berekeningsmodel, maar los hiervan, wat kan berekend worden an sich. Deze hypothese dateert van 1936 en Turing formuleerde ze als volgt: Stelling 3.2 (Church-Turing-hypothese). Elke ‘functie die natuurlijk berekenbaar is’, kan berekend worden door een universele Turing-machine. 40
De klassieke interpretatie is dat alle mogelijke interpretaties van wat een algoritme of berekening is, in feite gelijkwaardig zijn. Onafhankelijk van de vooruitgang van de techniek blijven we met dezelfde verzameling van berekenbare functies zitten. Snellere computers zullen er alleen maar voor zorgen dat we sneller kunnen rekenen.
3.2.2
De interpretatie van Deutsch
In 1985 geeft Deutsch in [13] echter een andere interpretatie, ge¨ınspireerd door de observatie van Feynmann over simulatie van kwantumsystemen, en herformuleert de hypothese in een ‘principe’ (om het onderscheid te kunnen maken met de originele these): Stelling 3.3 (Church-Turing-principe). Elk eindig realiseerbaar systeem kan perfect gesimuleerd worden door een universele berekeningsmachine die met eindige middelen werkt. Zijn motivering is dat een ‘functie die natuurlijk berekenbaar is’ in feite gelezen moet worden als een functie die berekenbaar is door een echt fysisch systeem, omdat het nogal moeilijk te aanvaarden is een functie ‘natuurlijk’ berekenbaar te beschouwen als ze niet door de Natuur zelf berekend kan worden [13]. De term ‘perfecte simulatie’ definieert Deutsch als volgt: Definitie 3.2 (Perfecte simulatie). Een berekeningsmachine M kan een fysisch systeem S perfect simuleren, onder een bepaalde labeling van ingangen en uitgangen, als er een programma π(S) bestaat voor M dat M equivalent maakt aan S onder deze labeling. Met andere woorden, π(S) maakt van M een black box die functioneel niet te onderscheiden valt van S.
3.3
Berekeningscomplexiteit
Als we het over de kost hebben om iets te berekenen, de berekeningscomplexiteit, dan drukken we dat uit als de benodigde bronnen die we nodig hebben om de berekening uit te voeren. Voor een computeralgoritme is dat klassiek: het benodigde geheugen (geheugencomplexiteit) en de uitvoeringstijd (tijdscomplexiteit). In de originele Church-Turing-hypothese, Stelling 3.2, wordt er helemaal niets gezegd over deze berekeningscomplexiteit. De stelling drukt alleen maar uit wat berekenbaar is en wat niet berekenbaar is. Nochtans heeft niemand oneindig veel tijd en geheugen om iets uit te rekenen. We hebben nood aan een andere opdeling die ons zegt welke functies er effici¨ent te berekenen zijn en welke niet. Tussen 1960 en 1970 kwamen computerwetenschappers daarom met een asymptotische classificatie die voldeed aan hun eisen en introduceerden de welbekende bijhorende grote-O-notatie.
3.3.1
Klassieke complexiteitsklassen
De opdeling die gemaakt werd was die van de polynomiaal en niet-polynomiaal gebonden functies, de complexiteitsklassen P en NP. 41
Definitie 3.3 (Complexiteitsklasse P). Een algoritme is polynomiaal als de complexiteit polynomiaal groeit met de grootte van het probleem voor het berekenen van de correcte uitkomst. Een probleem valt onder de klasse P als er een algoritme bestaat met polynomiale complexiteit. Dit wil nog niet zeggen dat het algoritme echt effici¨ent is! Zowel O(n2 ) als O(n200 ) zitten in klasse P. Het blijkt dat de meeste algoritmen die in P zitten een redelijk effici¨ente complexiteit bezitten en de meeste algoritmen niet in P meestal een exponenti¨ele complexiteit bezitten. Of een probleem in klasse P zit of niet, hangt dus niet af van het type computer waarop we het algoritme willen laten lopen. We bekomen zo de ‘volksopvatting’ [43] van de ChurchTuring-hypothese: Stelling 3.4 (Polynomiale Church-Turing-hypothese). Elke berekenbare functie kan berekend worden door een Turing-machine met maximaal een polynomiale stijging van de tijdscomplexiteit. Met andere woorden, als een functie berekend kan worden op een computer in tijd T , dan kan ze berekend worden door een Turing-machine in een tijd O(T c ), met c een constante die enkel afhankelijk is van het type computer dat men gebruikt. Om Stelling 3.4 onderuit te halen, kunnen we op zoek gaan naar functies die zeer moeilijk te simuleren zijn op een klassieke digitale computer. Shor noemt er twee: turbulentie en kwantummechanica [43]. Kwantumcomputers lijken alvast de populaire interpretatie van Stelling 3.4 onderuit te halen (al zullen we nog even moeten wachten op een grotere schaal van kwantumcomputer dan 11 bit als effectief bewijsmateriaal). Een niet-effici¨ente, belangrijke klasse van problemen is de klasse NP: Definitie 3.4 (Complexiteitsklasse NP). Een probleem zit in klasse NP als er een algoritme bestaat in P dat aangeeft of de uitkomst van het probleem correct is. In de NP-klasse vinden we ook de belangrijke NP-compleet-klasse. Deze problemen zijn allemaal omzetbaar naar elkaar met een polynomiale complexiteit. Met andere woorden, een oplossing voor ´e´en van deze problemen met complexiteit O(C(n)), kan omgezet worden naar een oplossing voor een ander probleem uit deze klasse met een polynomiale vertraging en heeft een gelijkaardige complexiteit O(poly(C(n))). De beste oplossing voor NP-compleetproblemen heeft (momenteel) een exponenti¨ele complexiteit en men gelooft dat er geen polynomiale oplossing mogelijk is. Dit is het bekende probleem: is P 6= N P ? Een andere interessante klasse is die van de bounded probability polynomial algoritmen, de klasse BPP. Deze is vooral interessant omdat we bij de meeste kwantumalgoritmen te maken krijgen met het kwantumequivalent van deze klasse. Definitie 3.5 (Complexiteitsklasse BPP). Een algoritme zit in klasse BPP als het algoritme een polynomiale complexiteit heeft in de grootte van het probleem en na afloop met ten minste 2/3 kans de correcte uitkomst berekend is. Voor de complexiteitsklasse BPP defini¨eren we een probabilistische Turing-machine (PTM). Deze is identiek aan de gewone Turing-machine, alleen wordt er bij een overgang een willekeurige transitie gekozen uit een aantal mogelijke toestandsovergangen, in tegenstelling tot 42
een gewone Turing-machine waarbij deze overgang een deterministisch proces is. Een gewone Turing-machine wordt daarom ook wel een deterministische Turing-machine (DTM) genoemd. Door deze probabilistische uitbreiding kunnen we veel meer problemen effici¨ent berekenen met een waarschijnlijkheid die we zo groot kunnen maken als we zelf willen (door herhaling). We komen zo tot de moderne opvatting van de Church-Turing-hypothese: Stelling 3.5 (Probabilistische Church-Turing-hypothese). Een probabilistische Turingmachine kan eender welk redelijk fysisch systeem simuleren met een polynomiale kost. Dezelfde opmerkingen als bij Stelling 3.4 zijn hier van toepassing en gooien roet in het eten. Alweer blijkt het een kwantumcomputer te zijn die aandringt op een ‘herformulering’ van Stelling 3.5.
3.3.2
Kwantumcomplexiteitsklassen
Zoals al een paar maal gesuggereerd, zullen we nu twee vreemde complexiteitsklassen defini¨eren die volgens de klassieke interpretatie heel vreemd klinken. Het zijn de kwantumequivalenten van P en BPP die we zullen defini¨eren: Definitie 3.6 (QP en BQP). De complexiteitsklassen QP (quantum polynomial) en BQP (bounded-error quantum polynomial time) defini¨eren we hetzelfde als de klassieke klassen P en BPP, alleen gebruiken we hier een QTM of een kwantumcircuit in plaats van respectievelijk een DTM en een PTM. Blijkbaar introduceren we hier twee nieuwe klassen alleen maar op basis van een nieuwe machine. Nochtans hebben we eerder al gezegd dat de machine er juist niet toe doet! Als de machine niet uitmaakt dan zou QP gelijk zijn aan P en BQP aan BPP. Er zijn echter algoritmen met een polynomiale complexiteit op een kwantumcomputer en een exponenti¨ele complexiteit op een klassieke computer. We moeten vaststellen dat [1, 53]: P BP P
⊂ QP
⊆ BQP
(3.7) (3.8)
Het bewijs voor (3.7) is in 1992 geleverd door Berthiaume en Brassard. Maar het is nog niet duidelijk of een QTM krachtiger is dan een PTM, vandaar de minder strikte uitdrukking (3.8). Een overzicht van de complexiteitsklassen is te vinden in Tabel 3.1. De laatste 3 voorbeelden zijn bekende kwantumalgoritmen, waarbij het Deutsch-Jozsa’s probleem klassiek in de klasse BPP valt en kwantummechanisch in de klasse QP! Er zijn verschillende ‘speelgoed’-algoritmen die een exponenti¨ele versnelling geven op een kwantumcomputer ten opzichte van een klassieke implementatie. Er is wel maar ´e´en bruikbaar algoritme bekend dat deze eigenschap vertoont, het factorisatie-algoritme van Shor [42]. Een kwantumcomputer kan ook perfect willekeurige getallen produceren, terwijl een klassieke computer enkel maar semi-willekeurige getallen produceert. Dit heeft gevolgen voor een PTM. Er moet in feite een beroep gedaan worden op een extern fysisch systeem voor de generatie van echte willekeurige getallen. De fout in de klassieke Church-Turing-thesis is het veronderstellen van een bepaalde mechanische machine. Het lijkt wel of een Turing-machine los staat van een echte implementatie 43
klasse P NP NP-compleet BPP QP BQP
benaming polynomiale problemen niet deterministisch polynomiale problemen equivalente problemen in NP probabilistische polynomiale problemen kwantum polynomiale problemen kwantum probabilistische polynomiale problemen
voorbeeld vermenigvuldiging factorisatie (niet bewezen) handelsreizigersprobleem Deutsch-Jozsa’s probleem Simon’s probleem Shor’s factorisatie-algoritme
Tabel 3.1: Overzicht van de klassieke- en kwantumcomplexiteitsklassen van een computer, maar in werkelijkheid bouwt ze verder op de klassieke mechanica. Een Turing-machine is eigenlijk niets anders dan een mechanische rekenmachine, en juist deze impliciete veronderstelling van de mechanica beperkt de TM. Het was dan ook juist hierom dat Deutsch de Church-Turing-hypothese herformuleerde naar een fysische interpretatie [13]. We moeten dan ook besluiten dat de enige bruikbare ChurchTuring-hypothese het fysisch principe van Deutsch is (herhaling): Stelling 3.3 (Church-Turing-principe). Elk eindig realiseerbaar systeem kan perfect gesimuleerd worden door een universele berekeningsmachine die met eindige middelen werkt.
44
Hoofdstuk 4
Kwantumpoorten Kwantumpoorten zijn het kwantumequivalent van de klassieke logische poorten. Zoals we met een set van logische poorten (bv. and, or, not) bewerkingen kunnen uitvoeren op bits, zo willen we met kwantumpoorten bewerkingen uitvoeren op qubits. Deze kwantumpoorten zullen we dan later kunnen gebruiken als bouwstenen voor ingewikkeldere bewerkingen die we wensen uit te voeren. Op deze manier zullen we ingewikkelde algoritmen kunnen omzetten naar een reeks van eenvoudige bewerkingen die door een kwantumcomputer ge¨ımplementeerd kunnen worden. We volgen volledig de klassieke weg, maar dan met de nodige aanpassingen om het kwantummechanisch te maken. In dit hoofdstuk zullen we m-bit kwantumpoorten toepassen op een register |ψi dat altijd evenveel qubits zal bevatten als de poort nodig heeft. In het volgende hoofdstuk zullen we er voor zorgen dat we een m-bit kwantumpoort ook op m willekeurige qubits van een n-bit kwantumregister kunnen toepassen.
4.1
Eigenschappen
De evolutie van een kwantumsysteem moet voldoen aan de vergelijking van Schr¨odinger i~
∂|ψ(t)i = H(t) |ψ(t)i , ∂t
(4.1)
waardoor er enkele eigenschappen zijn die een kwantumpoort moet bezitten. In (4.1) is H(t) de Hamiltoniaan van het kwantumsysteem en wordt voorgesteld door een matrix. Deze Hermitiaanse operator wordt bepaald door de structuur en de ladingen van de atomen en moleculen die het kwantumsysteem vormen en houdt dus verband met de totale energie en dynamica van het systeem. Indien we een bepaalde bewerking willen uitvoeren op de qubits van een kwantumsysteem, dan zal aan de Schr¨odinger-vergelijking voldaan moeten zijn. We gebruiken hiervoor een tijdsinvariante oplossing van (4.1).
45
4.1.1
De evolutie-operator
We veronderstellen dat de Hamiltoniaan H(t) uit (4.1) tijdsonafhankelijk is, i~
∂|ψ(t)i = H |ψ(t)i , ∂t
(4.2)
en laten het kwantumsysteem vertrekken vanuit de gekende toestand |ψ(0)i. De oplossing van (4.2) wordt dan: |ψ(t)i = e
−iHt
|ψ(0)i
= U (t) |ψ(0)i
(4.3)
De operator U (t) = e
−iHt
(4.4)
noemt men de evolutie-operator van het kwantumsysteem 1 . Hierin is de Hermitiaanse matrix H de generator van een groep van unitaire matrices U , want er geldt: U
= e ⇓
U∗ = e
−iH
iH ∗
= U −1 . Voor de QTM van Deutsch hebben we reeds opgemerkt dat de evolutie-operator U uit (3.6) lokaal en tijdsonafhankelijk moet zijn. Maar zo een lokale en tijdsonafhankelijke unitaire evolutie-operator kunnen we niet vinden indien we de Hamiltoniaan tijdsinvariant veronderstellen [53]. De oplossing van (4.1) met een tijdsafhankelijke Hamiltoniaan is Z i t H(τ ) dτ |ψ(0)i , (4.5) |ψ(t)i = T exp − ~ 0 met T de tijd-geordende integraal [53]. Op deze manier kunnen we een Hamiltoniaan H kiezen waardoor U toch aan de eisen voldoet.
4.1.2
Unitair
We kunnen (4.3) lezen als: |ψ(t)i = U |ψ(0)i .
(4.6)
We herkennen hierin ook Postulaat 2. Met andere woorden we hebben de toestand op tijdstip 0 omgezet naar een toestand op tijdstip t door een bepaalde unitaire bewerking uit te voeren. Dit is juist wat we wensen te bereiken met een kwantumpoort. We besluiten hieruit dat een kwantumbewerking (en dus ook een elementaire kwantumpoort) kan (of moet) voorgesteld worden door een unitaire matrix. 1
i
We lezen (4.4) als (e− ~ H )t , eA is gedefinieerd in Bijlage B.
46
4.1.3
Omkeerbaar
Doordat een kwantumpoort een unitaire bewerking is, is ze ook steeds omkeerbaar. U ∗ = U −1
(4.7)
Dit wil zeggen dat, gegeven de uitgang van een kwantumpoort, we terug de invoer kunnen berekenen. Op een kwantummechanisch niveau zijn alle gebeurtenissen in feite omkeerbaar; de tijd loopt daar niet noodzakelijk vooruit. Dit omkeerbaar zijn wordt in allerlei meer filosofische artikels gehanteerd om de meest fantastische verhaaltjes te ondersteunen. Zo is er het veelvuldig aangehaalde voorbeeld van een kwantumcomputer die iets uitrekent zonder ooit te hebben opgestaan. Of het fantastische verhaal van een wetenschapper die zichzelf een machine bouwt die ’s morgens reeds laat zien of hij op het einde van de dag resultaat zal boeken. Indien ja, dan gaat hij werken; indien nee, dan kan hij op het strand gaan liggen. Voor het ja-geval verfijnt hij de machine zodat hij het resultaat ook reeds ’s morgens te weten kan komen. De rest van zijn leven kan hij nu aan het strand gaan liggen.
4.1.4
Gevolgen
Dit unitair zijn heeft enkele gevolgen die door Charles Benett onderzocht zijn (i.v.m. reversibele berekeningen) [8, 22, 53]: • Zolang er geen observatie van het kwantumsysteem gebeurt, kunnen we de bewerkingen terugdraaien in de tijd. • Tijdens het uitvoeren van een kwantumberekening dissipeert een kwantumcomputer geen energie. Indien dit wel het geval zou zijn, dan zou het kwantumsysteem verstrengeld raken met zijn omgeving en wordt de kwantumtoestand verstoord. In 1961 toonde Landauer reeds aan dat alle bewerkingen, uitgezonderd het wissen van informatie, op een reversibele manier uitgevoerd kunnen worden [8]. Dat de bewerkingen omkeerbaar moeten zijn legt geen beperkingen op wat betreft berekenbaarheid. Een kwantumcomputer voldoet aan dit ideaalbeeld, want volgens de tweede hoofdwet van de thermodynamica dissipeert een reversibele bewerking geen warmte. Ook in de klassieke elektronica is men bezig om reversibele gate arrays te gebruiken en te bestuderen, om te kunnen genieten van de voordelen van reversibele berekeningen.
4.1.5
Definitie
Doordat de evolutie van een kwantumcomputer moet voldoen aan de Schr¨odinger-vergelijking, komen we tot de vaststelling dat kwantumpoorten unitaire operatoren moeten zijn.
47
Definitie 4.1 (Kwantumpoort). Een m-bit kwantumpoort is een unitaire operator U ∈ m U(2m ) die inwerkt op een toestandsvector |ψi ∈ H = C 2 : |ψit1 UU
∗
U
∗
= U |ψit0
(4.8)
∗
= U U =I = U −1 .
Dat we unitaire matrices gebruiken als wiskundige voorstelling, is ook nog anders te verklaren: ze behouden de norm van onze toestandsvector en we kunnen de complexe amplitudes hierdoor blijven beschouwen als aanduidingen van waarschijnlijkheden. Met andere woorden: indien we een fysische toestand |ψi transformeren naar een nieuwe toestand |U ψi, dan moet dat ook een fysische toestand zijn: k |U ψi k ≡ 1
= hψU ∗ |U ψi
= hψ|U ∗ U |ψi
∗
U U
4.1.6
(4.9)
⇓
= 1.
1-bit, 2-bit, 3-bit, ...
Een poort heeft een aantal ingangen en een aantal uitgangen. Zo heeft de klassieke andpoort 2 ingangen en 1 uitgang. Maar hoeveel ingangen en uitgangen moet een kwantumpoort hebben? Ingangen Het lijkt alsof het aantal ingangen er in feite niet zo toe doet. Theoretisch althans, want we willen de kwantumpoort natuurlijk ook in het echt kunnen maken. Doordat het maken van een poort haalbaar moet zijn, wordt er in de literatuur meestal maar gewerkt met 1, 2 of 3 qubits aan de ingang. Om kwantummechanische effecten te kunnen gebruiken moeten de fysische systemen die we als qubit gebruiken ook met elkaar kunnen interageren. Dit blijkt de voornaamste beperking op het aantal ingangsqubits. Bij de experimentele ion trap kwantumcomputer kan men een 3-qubit cnot-poort implementeren, maar voor de nieuwere quantum dots techniek lijken 2 fysisch naast elkaar liggende qubits realistischer. Uitgangen Het aantal uitgangen van een kwantumpoort is gelijk aan het aantal ingangen. We kunnen namelijk geen qubits weglaten of toevoegen, het kwantumsysteem is vast. 48
We kunnen dit zien als een rechtstreeks gevolg van de wiskundige formulering: we vermenigvuldigen een toestandsvector met een unitaire matrix en krijgen uiteindelijk terug een toestandsvector van dezelfde grootte. Langs de andere kant is dit een gevolg van het omkeerbaar zijn van de bewerking. Een omkeerbare functie is een functie die m ingangsbits omzet naar m uitgangsbits f : {0, 1}m → {0, 1}m
(4.10)
en een ´e´en-op-´e´en-relatie heeft zodat een bepaalde uitgang teruggebracht kan worden tot een bepaalde ingang. De reversibele functie f is in feite een permutatie van zijn ingangsbits en heeft per definitie evenveel ingangsbits als uitgangsbits. Ontbinden van willekeurige m-bit poorten Indien we een 2m × 2m unitaire matrix U ∈ U(2m ) hebben die een kwantumoperatie voorstelt, dan kunnen we deze ontbinden door middel van “kwantum Givens-rotaties” in matrices die nog maar in 2-dimensionale deelruimtes opereren [12]. Deze ontbinding van een willekeurige unitaire matrix heeft dan echter wel een exponentieel aantal stappen O(2m ) [12]. Verder is het helemaal niet zeker of de bekomen poorten ook fysisch realiseerbaar zijn. Deze exponenti¨ele complexiteit zorgt ervoor dat we niet zomaar een willekeurige evolutieoperator kunnen uitvinden en dan zeggen dat we een effici¨ent kwantumalgoritme hebben gevonden. Het zal nodig zijn om een effici¨ente ontbinding in kwantumpoorten te kunnen maken opdat het algoritme ook daadwerkelijk effici¨ent zal zijn. Een voorbeeld van zo’n effici¨ente ontbinding in basiskwantumpoorten is de discrete kwantumFourier-transformatie, waarbij men door gebruik te maken van dezelfde redenering als voor de klassieke FFT een complexiteit van O(poly(log m)) bekomt.
4.2
Enkele elementaire kwantumpoorten
We bekijken nu enkele elementaire kwantumpoorten.
4.2.1
De Hadamard-poort
De Hadamard-poort H is een 1-bit poort met de volgende beschrijving op basistoestanden: |0i 7→ |1i 7→
√1 2 √1 2
|0i + |0i −
√1 2 √1 2
|1i |1i .
(4.11)
We hebben voldoende aan deze basistransformaties om een kwantumpoort te beschrijven. Een willekeurige superpositie van de invoer kunnen we namelijk schrijven als een superpositie
49
van de verschillende uitgangen. Bijvoorbeeld voor de Hadamard-poort: α |0i + β |1i 7→ α √12 |0i + √12 |1i + β √12 |0i − √12 |1i =
√1 2
(α + β) |0i +
√1 2
(α − β) |1i .
(4.12)
We kunnen dit ook schrijven zonder expliciet de α en de β te gebruiken. We kunnen deze namelijk berekenen door het inwendig product te nemen van de toestandsvector met de overeenkomstige basistoestand. α = h0|ψi (4.13) β = h1|ψi De unitaire matrix voor Hadamard is: H=
4.2.2
"
√1 2 √1 2
√1 2 −1 √ 2
#
.
(4.14)
De not-poort
De kwantum not-poort X doet hetzelfde als de klassieke not-poort voor klassieke toestanden: |0i → 7 |1i |1i → 7 |0i .
(4.15)
Voor een willekeurige toestand |ψi krijgen we weer een lineaire combinatie van deze twee basistransformaties. De unitaire matrix voor not: X=
4.2.3
0 1 1 0
.
(4.16)
De wortel-van-not-poort
De wortel-van-not-poort is een kwantumpoort die hetzelfde effect heeft als de not-poort na twee toepassingen. Na ´e´en toepassing verkrijgen we als het ware de ‘wortel van not’: |0i 7→ |1i 7→
√1 2 √1 2
|0i − |0i +
met √ X=
"
√1 2 √1 2
√1 2 −1 √ 2
|1i 7→ |1i |1i 7→ |0i , √1 2 √1 2
#
.
(4.17)
(4.18)
De wortel-van-not-poort en de Hadamard-poort zijn beiden ‘echte’ kwantumpoorten. De not-poort is eerder een semi-klassieke poort: een basistoestand aan de ingang geeft een basistoestand aan de uitgang.
50
4.2.4
De cnot-poort – een conditionele poort
De afkorting cnot staat voor conditionele not-poort of controlled not gate. We hebben voor een conditionele poort 1 input extra die bepaald of de bewerking op de andere bit wordt uitgevoerd of niet. De eerste qubit is de controlebit, als deze bit 0 is, dan wordt de bewerking niet uitgevoerd; als deze bit 1 is dan wordt de bewerking wel uitgevoerd. Let wel, dit is een klassieke interpretatie, de controlebit kan natuurlijk in een superpositie van 0 en 1 zijn. De tweede qubit is de bit waarop de bewerking wordt toegepast, in dit geval de not bewerking. Voorgesteld in basistoestanden krijgen we dit: |0i |0i |0i |1i |1i |0i |1i |1i
7→ 7→ 7→ 7→
|0i |0i |0i |1i |1i |1i |1i |0i .
(4.19)
Een duidelijkere voorstelling voor een conditionele poort bekomen we door de toepassingsbit zo algemeen mogelijk te nemen (voorgesteld als |ψi) en de (globale) mogelijkheden van de controlebit expliciet te noteren. We doen dit hier voor een willekeurige 1-bit poort U : |0i |ψi 7 → |0i |ψi |1i |ψi 7 → |1i |U ψi (α |0i + β |1i) |ψi 7→ α |0i |ψi + β |1i |U ψi .
(4.20)
De voorstelling in (4.20) is veel duidelijker dan de mislijdende waarheidstabel voor basistoestanden in (4.19). We moeten namelijk beseffen dat zo een tabel onvolledig is: er zijn oneindig veel mogelijkheden en we tonen alleen maar de klassieke gevallen. Maar ook (4.20) is mislijdend: het is niet altijd mogelijk om de controlebit en de toepassingsbit als een tensorproduct te schrijven en je mag de laatste regel dan ook zo niet lezen! We zullen een betere schrijfwijze ontwikkelen in §5.5. De cnot-poort is een 2-bit poort. We krijgen hier 1 0 0 1 X10= 0 0 0 0
een 2 2 × 22 = 4 × 4 matrix: 0 0 0 0 . 0 1 1 0
(4.21)
Notatie. We schrijven X 1 0 om aan te duiden dat we operator X (de 1-bit not-poort) toepassen op bit 0, conditioneel afhankelijk van bit 1 (met de volgorde van de bits als in |x1 x0 i). Op dezelfde manier schrijven we later V k als we 1-bit poort V niet-conditioneel toepassen op bit k en V c k als we 1-bit poort V toepassen op bit k afhankelijk van bit c.
De cnot-poort wordt ook wel eens de kwantum xor-poort genoemd omdat ze op de basistoestanden dezelfde bewerking uitvoert als de klassieke xor-poort.
4.2.5
De swap-poort
De swap-poort verwisselt 2 qubits van plaats. Afhankelijk van de fysieke implementatie van de kwantumcomputer kan het zijn dat deze operatie niet echt moet uitgevoerd worden, maar 51
dat we bij de aansturing van het kwantumgeheugen zelf moeten onthouden dat de qubits van plaats verwisseld zijn. Dit is een 2-bit poort met als matrix:
1 0 S= 0 0
0 0 1 0
0 0 . 0 1
0 1 0 0
(4.22)
Zoals bij de not-poort komen we ook hier een interessante ‘echte’ kwantumpoort tegen indien we de wortel van deze poort nemen. De wortel-van-swap-poort: 1 0 0 0 −1 0 √1 √ 0 √ 2 2 S= (4.23) . 0 √1 √1 0 2
0
4.2.6
0
2
0
1
De Toffoli-poort
De Toffoli-poort is een 3-bit poort en is in feite ´e´en van de basispoorten voor klassieke reversibele circuits. Meer nog, de Toffoli-poort alleen is voldoende als bouwsteen voor eender welk reversibel klassiek circuit. Ze voert een dubbelconditionele not-poort (ccnot) uit. In de klassieke interpretatie zullen we de toepassingsbit enkel omkeren als de twee controlebits 1 zijn. De matrix voor de Toffoli-poort lijkt heel sterk op die van de cnot-poort in (4.21), alleen hebben we hier een 23 × 23 = 8 × 8 matrix die opereert op een toestand |x 2 x1 x0 i: 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 . (4.24) T = 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0
De Toffoli-poort is in feite niets anders dan een ccnot-poort, en we kunnen schrijven T = X 2,1 0 .
4.2.7
Een universele set van kwantumpoorten
Zoals in het klassieke geval hebben we een universele set G van kwantumpoorten nodig waarmee we alle functies kunnen implementeren. Deze set zal natuurlijk sterk afhankelijk zijn van de fysieke implementatie van de kwantumcomputer waarop we ze gebruiken. In §5.3 zal blijken dat zo een universele set bestaat. 52
a 0 0 1 1
b 0 1 0 1
a∧b 0 0 0 1
a∨b 0 1 1 1
a⊕b 0 1 1 0
¬a 1 1 0 0
Tabel 4.1: Enkele klassieke logische poorten
4.3
Klassieke poorten en willekeurige functies
Doordat klassieke niet-reversibele poorten informatie uitvegen, dissiperen ze warmte en hebben ze energie nodig om te werken. Reversibele poorten vegen geen informatie weg en hebben hierdoor, in tegenstelling tot niet-reversibele poorten, geen energie nodig om te werken, aldus Landauer [8]. De Toffoli-poort uit §4.2.6 is een universele poort voor klassieke reversibele berekeningen. De vraag rijst dan: kunnen we alle berekeningen die we met klassieke poorten kunnen uitvoeren ook uitvoeren op een omkeerbare manier? Het antwoord is ja [8]. Doordat een kwantumpoort in feite ook een reversibele poort is, kunnen we afleiden dat alle klassieke poorten ook uitgevoerd kunnen worden door kwantumpoorten.
4.3.1
Omkeerbaar maken van een klassieke poort
In Tabel 4.1 staan enkele klassieke logische poorten. We moeten onmiddellijk opmerken dat ∧, ∨ en ⊕ onmogelijk reversibele poorten kunnen zijn omdat ze van 2 ingangsbits naar 1 uitgangbit gaan. Dit voldoet niet aan de eis die we formuleerden in (4.10). Enkel de klassieke not-poort (¬) is reversibel. We kunnen echter op een heel eenvoudige manier elke niet-omkeerbare functie f : {0, 1}n → {0, 1}m ,
(4.25)
met n ingangsbits en m uitgangsbits, schrijven als
zodat
f˜ : {0, 1}n+m → {0, 1}n+m
(4.26)
˜ {0}m ) = (x, f (x)). f(x,
(4.27)
We kunnen van elke n-naar-m functie f een omkeerbare versie f˜ maken die van n + m naar n + m bits werkt volgens (4.27). We garanderen niet dat dit de meest economische uitvoering is voor een willekeurige functie, wel dat deze constructie steeds mogelijk is.
4.3.2
Klad-qubits en het herstellen van qubits
De extra bits die we nodig hebben om van een niet-omkeerbare functie een omkeerbare functie te maken resulteren in het nodig zijn van klad-qubits. Het is natuurlijk duidelijk dat we liefst zo weinig mogelijk van deze klad-qubits wensen te gebruiken. Uit (4.27) blijkt ook dat deze klad-qubits op 0 ge¨ınitialiseerd moeten zijn. 53
Het probleem Stel we hebben m klad-qubits die bij het begin van de berekening op 0 gezet zijn. Bij het eerste gebruik van deze m bits zijn deze netjes 0. Even later in de berekening moeten we echter opnieuw beroep doen op klad-qubits om een berekening omkeerbaar te maken. Kunnen we nu deze m bits gewoon opnieuw gebruiken? Kunnen we ze uitvegen zodat ze terug 0 zijn? Het is natuurlijk niet mogelijk om qubits uit te vegen: deze bewerking is namelijk niet omkeerbaar! Zoals Landauer ook reeds aantoonde, moet er voor het uitvegen van een bit aan informatie warmte gedissipeerd worden (het Landauer-principe [8]). De m bits opnieuw gebruiken is uitgesloten. Het probleem is dus dat hoe meer functies we moeten gebruiken voor onze volledige omkeerbare berekening, hoe meer klad-qubits j we nodig zullen hebben (de j in de formule staat voor junk ): ˜ {0}j , {0}m ) = (x, j(x), f (x)). f(x, (4.28) Uitwissen door de omgekeerde bewerking De oplossing voor dit probleem kwam van Bennett [4]. Doordat we reversibele bewerkingen uitvoeren kunnen we de bewerking ook in omgekeerde richting terug uitvoeren. Het is duidelijk dat indien de klad-qubits allemaal 0 zijn in het begin, deze ook terug 0 zullen zijn indien we de bewerking achterstevoren terugdraaien. Omdat het resultaat ook terug uitgewist wordt, zullen we dat eerst moeten dupliceren met behulp van een fanout-operator. No-cloning principe We kunnen niet zomaar een willekeurige kwantumtoestand kopi¨eren. Dit is een onmogelijke bewerking voor een unitaire operator. Het bewijs van Wootters en Zurek is eenvoudig en in verschillende incarnaties terug te vinden [9, 33, 36]: Bewijs. We veronderstellen dat we een unitaire operator U hebben die een onbekende toestand kan dupliceren. U |ψi |0i 7→ |ψi |ψi We passen U nu toe op twee onbekende toestanden |ai en |bi. U (|ai |0i) = |ai |ai U (|bi |0i) = |bi |bi
Indien we nu een toestand |ci = α |ai + β |bi nemen (|α| 2 + |β|2 = 1), dan kunnen we aantonen dat U (|ci |0i)
def
=
|ci |ci
niet algemeen geldt, terwijl dit de definitie van onze operator U is. We rekenen beide leden
54
uit: ?
U ((α |ai + β |bi) |0i) = (α |ai + β |bi)(α |ai + β |bi) ?
U (α |ai |0i + β |bi |0i) =
α2 |ai |ai + β 2 |bi |bi 6= α2 |ai |ai + αβ |ai |bi +
(4.29)
2
αβ |bi |ai + β |bi |bi .
Uit (4.29) leiden we af dat we alleen maar orthogonale toestanden kunnen dupliceren, waarvoor de vergelijking wel opgaat. De fanout-operatie Het is echter wel mogelijk om basistoestanden te dupliceren, bijvoorbeeld met de xor-poort: X
1 0
(α |0i + β |1i) |0i 7→ α |0i |0i + β |1i |1i .
(4.30)
Dit heeft consequenties voor de fanout-operator die we op een eenvoudige manier zouden kunnen implementeren als: fanout : |x, 0i 7→ |x, x ⊕ 0i . (4.31)
Met andere woorden, dit is een bit voor bit kopie en we moeten opletten wanneer we de fanout-operator kunnen gebruiken en wanneer niet. We kunnen onmogelijk de volledige kwantumtoestand van een willekeurige superpositie dupliceren in een leeg register. Procedure voor het beperken van klad-qubits Om het aantal extra qubits, de j(x) in (4.28), te beperken volgen we volgende procedure:
• f˜(x, {0}j , {0}m , {0}m ) = (x, j(x), f (x), {0}m ) Implementeer de functie f door de reversibele functie f˜. We krijgen als resultaat: de invoer x, een aantal klad-qubits j(x) en het resultaat van de functie f (x). • fanout(x, j(x), f (x), {0}m ) = (x, j(x), f (x), f (x)) Het resultaat van de functie dupliceren we een extra keer. Dit doen we door middel van een fanout-operator (4.31), waarbij we moeten opletten voor het no-cloning principe. • f˜∗ (x, j(x), f (x), f (x)) = (x, {0}j , {0}m , f (x)) Voor de laatste stap zullen we f˜ achterstevoren uitvoeren, aangeduid met f˜∗ . Hierdoor zal het resultaat van de eerste stap terug ongedaan gemaakt worden en recupereren we m + j qubits. Of meer schematisch2 uitgevoerd op |x3 , x2 , x1 , x0 i: |x, 0, 0, 0i
F3,2,1
7→
C1,0
7→
∗ F3,2,1
7→
2
|x, j(x), f (x), 0i
|x, j(x), f (x), f (x)i |x, 0, 0, f (x)i .
We noteren de kwantumoperator voor f als F en de fanout-operator als C.
55
(4.32)
Samengestelde functies Bij een samenstelling van twee functies f (x) = h(g(x)), kunnen we op een gelijkaardige manier het tussenresultaat uitvegen, toegepast op |x 2 , x1 , x0 i: |x, 0, 0i
G2,1
7→
H1,0
7→
G∗2,1
7→
|x, g(x), 0i
|x, g(x), h(g(x))i
(4.33)
|x, 0, f (x)i .
We beschouwen nu een algemene samenstelling van d functies. f = f d ◦ · · · ◦ f 2 ◦ f1
(4.34)
Indien we de samengestelde functie f uit (4.34) toepassen zonder de klad-qubits te herstellen dan hebben we d operaties (van de deelfuncties f i ) en (d − 1) klad-registers nodig. (Een klad-register is een aantal qubits groot genoeg voor ´e´en resultaat van een functie. De functies in de samenstelling hebben uiteraard allemaal hetzelfde aantal ingangs- en uitgangsbits.) De (d − 1) klad-registers zijn niet meer bruikbaar voor verdere berekeningen omwille van twee redenen: • ze zijn niet meer 0 en dit is een vereiste om ze opnieuw als klad-qubit te kunnen gebruiken; • interactie met deze qubits kan het bekomen resultaat verstoren door verstrengeling met het bekomen resultaat. Bij het gebruik van (4.33) om alle klad-qubits terug te herstellen in de 0-toestand, hebben we (d − 1) klad-registers nodig en 2d operaties. Het grote voordeel is echter wel dat we nu deze (d − 1) klad-registers terug kunnen gebruiken, zonder het bekomen resultaat te verstoren. Voorbeeld 4.1. Om (i ◦ h ◦ g)(x) uit te rekenen met d = 3 op |x 2 , x1 , x0 i: |x, 0, 0i
G2,1
7→
|x, g(x), 0i
7→
|x, g(x), h(g(x))i
7→
|x, 0, h(g(x))i
7→
|x, i(h(g(x))), h(g(x))i
H1,0 G∗2,1 I0,1
♦
56
Voorbeeld 4.2. Om (l ◦ k ◦ j ◦ i ◦ h ◦ g)(x) uit te rekenen met d = 6 op |x 3 , x2 , x1 , x0 i: |x, 0, 0, 0i
G3,2
7→
|x, g(x), 0, 0i
7→
|x, g(x), h(g(x)), 0i
7→
|x, g(x), h(g(x)), i(h(g(x)))i
7→
|x, g(x), 0, i(h(g(x)))i
7→
|x, 0, 0, i(h(g(x)))i
7→
|x, j(i(h(g(x)))), 0, i(h(g(x)))i
7→
|x, j(i(h(g(x)))), k(j(i(h(g(x))))), i(h(g(x)))i
7→
|x, 0, k(j(i(h(g(x))))), i(h(g(x)))i
7→
|x, l(k(j(i(h(g(x)))))), k(j(i(h(g(x))))), i(h(g(x)))i
H2,1 I1,0 ∗ H2,1
G∗3,2 J0,2 K2,1 ∗ J0,2
L1,2
♦ Op deze manier kunnen we de benodigde ruimte verminderen met O(d −1/2 ) met een berekeningssurplus van O(2) [34]. Het is duidelijk dat op deze manier een deel van de klad-qubits niet te recupereren valt, maar we hebben niet zoveel extra qubits nodig om de berekening uit te voeren.
57
Hoofdstuk 5
Kwantumcircuits & kwantumcomputers In §3.1.2 werd reeds gemotiveerd waarom we kwantumcircuits verkiezen boven het model van de QTM. In dit hoofdstuk zullen we deze circuits van dichterbij bekijken.
5.1
Een voorbeeldcircuit
We stellen een kwantumcircuit voor door n horizontale lijnen die de n qubits van het systeem voorstellen. Door het no-cloning principe en de fanout-operator uit §4.3.2 weten we dat alle qubits, ook de klad-qubits, aan de ingang van het circuit reeds ge¨ınitialiseerd moeten zijn, willen we er iets nuttigs mee kunnen doen. We kunnen geen willekeurige qubits toevoegen in het midden van het circuit en we kunnen er ook geen weglaten doordat we een reversibele kwantumberekening maken. In Figuur 5.1 hebben we een 3-bit kwantumsysteem. Aan de linkerzijde van de figuur zien we de toestanden van de 3 bits afzonderlijk weergegeven als |x 2 i, |x1 i, |x0 i. Na het toepassen van het circuit geven we aan de rechterzijde een aanduiding voor de toestand waarin de 3 qubits zich bevinden: |x02 i, |x01 i, |x00 i. Het gevaar bestaat nu dat men dit interpreteert alsof de toestand van elke bit afzonderlijk beschreven kan worden. Dit is natuurlijk niet altijd waar! Dezelfde opmerking geldt in principe voor de ingang van het circuit, al zal het meestal zo zijn dat de ingangsqubits ge¨ınitialiseerd zijn op een basistoestand en zo individueel te beschrijven zijn. We komen echter ook kwantumsubroutines tegen als kwantumcircuit en in die gevallen |x2 i
|x02 i
|x1 i
|x01 i
|x0 i
U
U∗
U
Figuur 5.1: Een voorbeeldkwantumcircuit
58
|x00 i
√ X
H (a) Hadamard-poort
(b) not-poort
(c) wortel-van-not-poort
6 ? (d) cnot-poort
(e) swap-poort
(f) swap-poort (alt.)
√ S T (g) wortel-van-swap-poort
(h) Toffoli-poort
(i) ccnot-poort
Figuur 5.2: Kwantumcircuitsymbolen voor enkele elementaire kwantumpoorten kan de ingang zich in een willekeurige toestand bevinden (op de klad-qubits na, die ook hier op een bruikbare waarde ge¨ınitialiseerd moeten zijn). In het voorbeeld passen we achtereenvolgens vijf kwantumpoorten toe, te beginnen met de meest linkse. We passen eerst U 1 0 toe, dan X 2 1 (het gekke omcirkelde plusteken), vervolgens U ∗1 0 , nogmaals een X 2 1 en tenslotte U 2 0 . Met andere woorden: we laten de tijd van links naar rechts lopen. In de literatuur kom je soms ook een tijdsverloop van rechts naar links tegen. Men kiest er dan voor om in het circuit dezelfde volgorde aan te houden als met operatoren in de gelijkwaardige formule. De overeenkomstige formule voor het circuit uit Figuur 5.1 is:
U
2 0
·X
2 1
· U ∗1 0 · X
2 1
·U
1 0
· |x2 , x1 , x0 i = |x02 , x01 , x00 i .
(5.1)
We kiezen voor de meest gebruikte tijdsrichting: van links naar rechts.
5.2
Voorstelling van kwantumpoorten in een circuit
In het vorige hoofdstuk werden in §4.2 enkele elementaire kwantumpoorten gedefinieerd. In Figuur 5.2 tonen we voor elk van deze poorten het overeenkomstige symbool. De meest voorkomende aanduiding is gewoon de letter van de operator of de benaming van de poort in een kadertje zoals voor de Hadamard-poort in Figuur 5.2(a). De not-poort-familie (not, cnot, ccnot, ...) komt zo vaak voor dat men ze een speciaal symbool gegeven heeft, te zien in Figuur 5.2(b), Figuur 5.2(d) en Figuur 5.2(i). De controlebits worden met de poort verbonden door een verticaal lijntje en aangeduid met een bolletje. 59
De swap-poort wordt meestal aangeduid als in Figuur 5.2(e), maar soms duidt men ze aan als in Figuur 5.2(f) om duidelijk te maken dat dit niet noodzakelijkerwijs een echte kwantumpoort hoeft te zijn. We kunnen de swap-poort even goed implementeren door te onthouden dat de twee qubits verwisseld zijn. Dat is natuurlijk niet zo voor de wortel-van-swap-poort. Voor de Toffoli-poort vinden we ook twee gangbare symbolen: Figuur 5.2(h) en Figuur 5.2(i). Dit komt omdat een Toffoli-poort eigenlijk een dubbelconditionele not-poort (ccnot) is. Maar omdat de Toffoli-poort zo’n belangrijke poort is voor reversibele berekeningen duidt men ze soms expliciet aan.
5.3
Universele sets van kwantumpoorten
Niet alle kwantumpoorten zijn fysisch implementeerbaar op een bepaald type van kwantumcomputer. En omdat er nog geen echt bruikbare kwantumcomputers bestaan kunnen we ons ook niet houden aan een echte set van implementeerbare kwantumpoorten. Ook voor kwantumcomputers zijn er universele sets van kwantumpoorten waarmee alle mogelijke kwantumpoorten te simuleren zijn. Bij klassieke computers hebben we bijvoorbeeld als mogelijke universele sets {and, or, not} of eenvoudigweg {nand}, ... Voor reversibele computers volstaat bijvoorbeeld alleen de Toffoli-poort. We bekijken eerst enkele eigenschappen van unitaire matrices waarvan we er verderop nog enkele nodig zullen hebben.
5.3.1
Algemene eigenschappen van unitaire matrices
Een 1-bit kwantumpoort U(1) is een 2 × 2 unitaire operator zoals we reeds enkele voorbeelden gezien hebben in §4.2. In de literatuur schrijft men dat U (1) ∈ U(2). Voor een m-bit kwantumpoort schrijven we U(2m ) ∈ U(2m ). Hierbij is U(n) gedefinieerd als U(n) = {A : A ∈ Cn×n , det(A) 6= 0, A∗ A = I}. Elke unitaire 2 × 2 matrix kunnen we schrijven als iβ/2 iα/2 iδ e 0 cos θ/2 sin θ/2 e 0 e 0 , · · · − sin θ/2 cos θ/2 0 eiδ 0 e−iβ/2 0 e−iα/2
(5.2)
(5.3)
met δ, α, θ, β ∈ R [3]. Dit volgt rechtstreeks uit de algemene vorm van een unitaire 2 × 2 matrix, waarbij de rijvectoren en kolomvectoren orthonormaal zijn: ei(δ+α/2+β/2) cos θ/2 ei(δ+α/2−β/2) sin θ/2 U= . (5.4) −ei(δ−α/2+β/2) sin θ/2 ei(δ−α/2−β/2) cos θ/2 Door de ontbinding uit (5.3) kunnen we een willekeurige unitaire matrix schrijven als een product van enkele vaste basismatrices. Enkele veelgebruikte basismatrices zijn [3]: • Ry (θ) =
cos θ/2 sin θ/2 − sin θ/2 cos θ/2
, een rotatie θ rond de y-as; 60
xm xm−1 .. . x0
U
Figuur 5.3: Een m-conditionele 1-bit poort G ∈ ∧ m (U ) • • • •
eiα/2 0 , een rotatie α rond de z-as; Rz (α) = 0 e−iα/2 iδ e 0 , een fase-draaiing δ; P h(δ) = 0 eiδ 0 1 σx = , negatie- of Pauli-matrix; 1 0 1 0 I= , de 2 × 2 eenheidsmatrix. 0 1
De ontbinding van een willekeurige unitaire 2 × 2 matrix U is ge¨ınspireerd op groepentheorie en we kunnen (5.3) nu verkort schrijven als U
= P h(δ) · Rz (α) · Ry (θ) · Rz (β).
(5.5)
Men gebruikt ook operatoren uit SU(n), de zogenaamde speciale unitaire matrices, gedefinieerd als SU(n) = {A : A ∈ U(n), det(A) = 1}. (5.6) We kunnen U ∈ SU(n) ook schrijven als in (5.5). De meest linkse term valt dan weg (δ = 0) en we krijgen U
= Rz (α) · Ry (θ) · Rz (β).
(5.7)
Doorgaans tracht men aan de hand van deze verzameling basismatrices, die in feite een set van basiskwantumpoorten voorstellen, grotere kwantumpoorten op te breken in kleinere poorten met extra controlebits. De grotere kwantumpoorten die men wenst te ontbinden zijn meestal conditionele poorten: men heeft een n-bit kwantumpoort U en past die enkel toe als de m controlebits 1 zijn (opgelet: klassieke interpretatie!). We nemen hier de notatie over uit [3] en schrijven voor een (m + 1)-bit kwantumpoort G met m controlebits aan een 1-bit poort U (Figuur 5.3) G ∈ ∧m (U ).
61
(5.8)
5.3.2
De universele set
We defini¨eren een universele set van kwantumpoorten [22]: Definitie 5.1 (Universele set). De verzameling G ex = {G1(n1 ) , G2(n2 ) , ..., Gr(nr ) } van ni qubit kwantumpoorten Gi(ni ) is een universele set als een samenstelling van deze kwantumpoorten een willekeurige N -qubit unitaire operator U (N ) kan vervangen. We kunnen een willekeurige unitaire matrix van dimensie k = 2 n , een operator op n qubits, ontbinden via “kwantum Givens-rotaties” als een product van k(k − 1)/2 unitaire matrices die opereren op 2 qubits [12, 22]. Dit is een exponenti¨ele ontbinding in het aantal qubits! De ontbinding is standaard lineaire algebra en het product is een exacte ontbinding in elementaire 2-bit kwantumpoorten.
5.3.3
Benaderingen
Het is helemaal niet nodig dat een bepaalde operatie exact wordt uitgevoerd. Een kwantumcomputer werkt, in tegenstelling tot een digitale klassieke computer, met continue geheugenelementen (met co¨effici¨enten ci ∈ C). Daarom zullen we niet eisen dat een unitaire matrix U exact wordt ontbonden, maar zijn we tevreden als U benaderd wordt door U 0 = G1 G2 · · · Gn met een bepaalde , waarvoor geldt: kU − U 0 k ≤ .
(5.9)
De norm in (5.9) is de ge¨ınduceerde matrixnorm. We kunnen een unitaire transformatie op een toestandsvector voorstellen als een rotatie in de Hilbert-ruimte van deze vector. Als we U 0 gebruiken in plaats van U zal de uiteindelijke toestandsvector een hoekafwijking hebben van O() die niet groeit tijdens verdere bewerkingen. We kunnen stellen dat de fout additief is [1]. Als een kwantumcircuit N kwantumpoorten gebruikt, dan is het voldoende dat elke kwantumpoort benaderd wordt met een van O(N −1 ), opdat de berekening correct zou zijn met een constante waarschijnlijkheid [5]. Hierdoor zullen we dikwijls operaties benaderen in plaats van ze exact uit te voeren, zonder het uiteindelijke resultaat echt te schaden. We komen zo tot een minder strenge definitie van de universele set [1], waarbij we de benadering hebben toegevoegd: Definitie 5.2 (Benaderende universele set). Een set van kwantumpoorten G ap is universeel als voor elke > 0, elke unitaire matrix U , kan -benaderd worden door een samenstelling van kwantumpoorten uit G ap . Met andere woorden: de deelgroep gegenereerd door G ap is dicht in de groep van unitaire operatoren U (n) voor alle n.
5.3.4
Enkele voorbeelden van universele sets
De Deutsch-poort De eerste universele set staat op naam van David Deutsch en bestaat uit ´e´en (type) kwantumpoort: de Deutsch-poort Dθ (zie Figuur 5.4): G1ex = {Dθ }. 62
(5.10)
|x2 i
θ
Rθ = −i ei 2 σx = −i I cos 2θ + i σx sin 2θ " # cos 2θ i sin 2θ = −i cos 2θ i sin θ2
|x1 i |x0 i
Rθ
Figuur 5.4: De Deutsch-poort is op zich een universele set |x2 i |x1 i |x0 i
= U
V
V∗
V
Figuur 5.5: Ontbinding van een ∧2 (U )-poort (Barenco et al.) Deze kwantumpoort roteert de qubit onder een bepaalde hoek θ rond de x-as (met σ x de Pauli-spin-matrix van de x-as voor een elektron). Met de Deutsch-poort(en) kan men eender welke unitaire matrix exact samenstellen. Hierbij is θ een parameter. Deze set bestaat in feite uit een oneindige verzameling van kwantumpoorten en is dus niet realistisch. E´en van de eisen die we aan een Turing-machine stellen is dat ze met een eindig aantal middelen werkt. Indien men ´e´en Deutsch-poort neemt met voor deze parameter θ van R θ een irrationeel ˆ dan is die poort op zich wel een universele set, zij het een veelvoud van π, voorgesteld door θ, benaderende universele set [22]: G2ap = {Dθˆ} met θˆ een irrationeel veelvoud van π.
(5.11)
Voor elke waarde van λ kunnen we eiλσx -benaderen door Rθˆ een eindig aantal keer uit te voeren: de machten van Rθˆ zijn dus dicht in eiλσx [22, 33]. Reductie naar 2-bit kwantumpoorten Een andere exacte universele set is de verzameling die bestaat uit de verzameling van 1-bit poorten en de cnot-poort: G3ex = {U(1) ∈ U(2), ∧1 (X)}. (5.12) Dit werd aangetoond in een belangrijk artikel uit 1995, ‘Elementary gates for quantum computation’ [3], van grote namen in de kwantumwereld, o.a. A. Barenco, C. Bennett, D. DiVincenzo en P. Shor. De ontbinding van een conditionele 3-bit poort G ∈ ∧ 2 (U ) naar een combinatie van 2-bit poorten is te zien in Figuur 5.5. Het bewijs is af te lezen op de figuur. Bewijs. Men construeert een 1-bit poort V waarbij V 2 = U . We kunnen dan de situaties van de tekening aflezen voor een invoer |ψi = |x 2 , x1 , x0 i: 63
|x1 i |x0 i
= W
A
B
C
Figuur 5.6: Ontbinding van een ∧1 (W )-poort • |0, 0, x0 i 7→ |0, 0, I · x0 i; • |0, x1 , x0 i 7→ |0, x1 , (V ∗ V = I) · x0 i; • |x2 , 0, x0 i 7→ |x2 , 0, (V V ∗ = I) · x0 i en • |1, 1, x0 i 7→ |1, 1, (V V = V 2 = U ) · x0 i. Door lineariteit weten we dat het circuit uit Figuur 5.5 ook voor een willekeurige input het gewenste resultaat bereikt. Ook transformaties van 2-bit naar 1-bit poorten en de cnot-poort zijn mogelijk. Zo kunnen we een willekeurige ∧1 (W )-poort met W
= Rz (α) · Ry (θ) · Rz (β) ∈ SU(2),
(5.13)
vervangen door het schema in Figuur 5.6 met A, B, C ∈ SU(2) [3]. Bewijs. Men neemt matrices A, B, C ∈ SU(2) zodanig dat A · B · C = I, A · σx · B · σx · C = W.
(5.14) (5.15) Ry ( θ2 ),
B = Uit (5.3) weten we dat we α, β, θ ∈ R kunnen kiezen zodanig dat A = R z (α) · α+β β−α θ Ry (− 2 ) · Rz (− 2 ) en C = Rz ( 2 ). Door invullen in (5.14) en (5.15) zien we dat aan de voorwaarden voldaan is. De equivalentie tussen de twee kwantumcircuits kunnen we nu aflezen van de figuur: • |0, x0 i 7→ |0, (ABC = I) · x0 i en • |1, x0 i 7→ |1, (Aσx Bσx C = W ) · x0 i. Door lineariteit geldt het netwerk ook in het algemene geval. We kunnen stellen dat 1-bit poorten samen met de cnot-poort een universele set G 3ex zijn: de (conditionele) fasedraaiing is namelijk eenvoudig toe te voegen zoals te zien in Figuur 5.7. Bewijs. De transformaties voor beide netwerken zijn identiek als we 1 0 E = Rz (−δ) · P h(δ/2) = 0 eiδ 64
(5.16)
|x1 i
E =
|x0 i
P hδ
Figuur 5.7: Ontbinding van een ∧1 (P h(δ))-poort naar een niet-conditionele 1-bit poort kiezen. De totale transformatie voor beide netwerken 1 0 0 1 Ph 1 0 = E ⊗ I = 0 0 0 0
is dan: 0 0 0 0 . iδ e 0 0 eiδ
(5.17)
Eerder had DiVincenzo reeds aangetoond dat 2-bit kwantumpoorten universeel waren [17] door met 2-bit poorten een benadering te maken van een Deutsch-poort. Dit is belangrijk omdat het zeer moeilijk geacht wordt om 3 qubits met elkaar te laten interageren in een echte kwantumcomputer [1, 17, 53] (afhankelijk van de implementatie van de uiteindelijke kwantumcomputer). In [17] toont DiVincenzo hoe je een Deutsch-poort D λ (voor een fasedraaiing na), 1 1 1 1 Dλ = 1 1 cos λ i sin λ i sin λ cos λ
bepaalde λ = −2πα en op
,
(5.18)
kunt ontbinden in 2-bit kwantumpoorten. Hij gebruikt hiervoor twee 2-bit poorten, die hij X en V noemt, en ´e´en 1-bit poort N . Omdat we X al gebruikt hebben voor de not-poort, die DiVincenzo N noemt, veranderen we de poorten van naam: X wordt Y en N wordt X: iφ e 1 0 1 1 1 en V = . ,Y = X= (5.19) 1 0 1 cos φ sin φ 1 − sin φ cos φ DiVincenzo toonde aan dat de poort D λ equivalent is met het schema in Figuur 5.8 door het uitrekenen van [17]: D(λ = γ 2 ) ≈ X1 V
2 0 (φ
= −γ) Y1,0 (φ = −γ) V
2 0 (φ
= γ) Y1,0 (φ = γ) X1 .
(5.20)
De oplossing van Barenco et al. (waaraan ook DiVincenzo meewerkte) is echter eleganter en belangrijker voor het maken van een kwantumcomputersimulator omdat de poorten eenvoudiger zijn. 65
|x2 i |x1 i |x0 i
=
X
X Yγ Vγ
Rλ
Y−γ
V−γ
Figuur 5.8: De ontbinding van ∧2 (Rλ ) volgens DiVincenzo De bovengrens1 voor het implementeren van ∧m -poorten met G3ex is Θ(m2 ) en kan nog verlaagd worden naar Θ(m) indien er ´e´en enkele klad-qubit gebruikt mag worden [3]. Het resultaat dat 2-bit kwantumpoorten universeel zijn is overigens zeer verrassend! Voor klassieke reversibele computers was er namelijk al aangetoond dat 2-bit poorten niet universeel waren en had men de 3-bit Toffoli poort als minimale universele set. Eindige sets van 2-bit poorten Twee andere eindige benaderende sets zijn [22]: G3ap = {H, ∧1 (P h(π/2))},
G4ap
= {H, W, ∧1 (X)} met W = diag(1, e
(5.21) iπ/4
).
(5.22)
De universele set van Kitaev (5.21) gebruikt de Hadamard-poort en een conditionele fasedraaiing over π/2. De set van Cleve (5.22) gebruikt de Hadamard-poort, een speciale W poort in de stijl van de Y poort van Deutsch en een conditionele not-poort. We merken op dat ´e´en ∧1 (U(1) ) poort (een 2-bit poort) en een aantal 1-bit poorten voldoende blijken te zijn om alle mogelijke interacties tussen de verschillende qubits te modelleren. Dit is natuurlijk zeer goed nieuws voor de onderzoekers die experimentele kwantumcomputers trachten te bouwen. Deze eigenschap zullen we ook gebruiken bij het bespreken van een simulator, waarbij het hierdoor voldoende is om een 1-bit poort en een 1-bit conditionele 1-bit poort toe te kunnen passen.
5.4
Toepassen van een 1-bit kwantumpoort
Indien we een 1-bit kwantumpoort V willen toepassen op bit k van een n-bit kwantumregister |ψi, genoteerd als Vk , dan hebben we een 2n × 2n evolutie-operator U nodig. |ψi 7→ |U ψi
7→ |Vk ψi
(5.23)
Deze evolutie-operator U zal alle 2 n co¨effici¨enten van de toestandsvector aanpassen! Er is niet ´e´en co¨effici¨ent die deze bit vertegenwoordigt: deze bit zit namelijk in elke basistoestand en neemt dus deel in elke amplitude c i . 1
We defini¨eren Θ(f ) als g ∈ Θ(f ) ⇔ g ∈ O(f ) ∧ f ∈ O(g).
66
Wanneer we poort V toepassen op bit k dan heeft de evolutie-operator de volgende vorm: ! ! n −1 2O k−1 O I2 ⊗ V ⊗ I2 U = Vk = (5.24) i=0
i=k+1
met I2 de 2 × 2 eenheidsmatrix en V de 2 × 2 operator van de kwantumpoort. Of anders geschreven: U
⊗(2n −1−k)
= I2
⊗ V ⊗ I2⊗k
= I2(2n −1−k) ⊗ V ⊗ I2k met I2⊗k de k-de tensormacht van I2 .
We lezen (5.24) als de samenstelling van het toepassen van de eenheidstransformatie op alle bits, uitgezonder bit k, en het toepassen van de transformatie V op bit k. We noteren de toepassing van poort V op bit k als Vk .
5.5
Toepassen van een ∧1(V(1) )-poort
Voor het toepassen van een 1-bit kwantumpoort V op bit k, conditioneel afhankelijk van bit c op een n-bit kwantumregister |ψi krijgen we volgende evolutie: |ψi 7→ |U ψi
c k ψi |Pc(0) ψi +
7→ |V
7→
|(Vk Pc(1) ) ψi
(5.25)
met α en β de co¨effici¨enten van |ci = α |0i + β |1i over de hele toestand en twee projectieoperatoren P (0) en P (1) gedefinieerd als2 1 0 0 0 (0) (1) P = |0i h0| = , P = |1i h1| = met P (0) + P (1) = I. (5.26) 0 0 0 1 Deze projectie-operatoren zijn geen kwantumpoorten, ze zijn niet unitair en voldoen dus niet aan Definitie 4.1. We kunnen (5.25) vergelijken met (4.20) waar we een conditionele poort toepasten op een 2 qubit toestand. We splitsen als het ware bit c in twee stukken zodat we de superpositie van het wel en niet toepassen van de kwantumpoort V kunnen uitdrukken. We volgen voor een willekeurige controlebit |ci = α |0i+β |1i (beschouwd over de hele toestand |ψi), met α, β > 0, beide paden tegelijk en krijgen een superpositie met een kans |α| 2 voor de niet toegepaste versie waar |ci = |0i en een kans |β| 2 voor de toestand waar de poort V wel is toegepast en |ci = |1i. De operatoren P (0) en P (1) dienen enkel als formalisme om de ontbinding van |ci in (5.25) te kunnen schrijven als |ci = P (0) |ci + P (1) |ci 2
Het gebruik van de projectie-operatoren als formalisme voor een conditionele poort is een eigen uitbreiding, 0 1 0 0 en c = a∗ = , met in de literatuur definieert men wel de annihilatie- en creatie-operatoren a = 0 0 1 0 a + c = X, bijvoorbeeld in [53] voor het Feynmann-kwantumcomputermodel.
67
1 0 α 0 0 α = + 0 0 β 0 1 β α 0 = + 0 β 1 0 =α +β 0 1 = α |0i + β |1i .
Bij het toepassen van een ∧1 (V(1) )-poort moeten we maar de helft van de co¨effici¨enten, 2n−1 , van de toestandsvector aanpassen, namelijk diegene waarvoor de controlebit c op 1 staat in de binaire representatie van de basistoestand. Voorbeeld 5.1. We passen een kwantumpoort V toe met als matrix α β V = γ δ op de middelste bit (k = 1) van een 3-bit register |ψi = |x 2 , x1 , x0 i. Zonder controlebit is de evolutie-operator U 0 voor het hele register α β α β γ δ γ δ 0 . U = V1 = I ⊗ V ⊗ I = α β α β γ δ γ δ
De stippelijntjes duiden aan hoe matrix V verspreid wordt in U 0 . Ze duiden geen continuaties van elementen aan. Er zijn maximaal 16 niet-nul elementen in deze matrix.
Met controlebit laat de evolutie-operator U de amplitudes ω i van de toestandsvector waarbij de controlebit c niet gezet is ongemoeid. Nemen we bijvoorbeeld c = 2 als controlebit, dus U = V 2 1 , dan krijgen we volgende situatie: ω000 1 ω001 1 ω010 1 ω011 1 (5.27) U |ψi = V 2 1 |ψi = ω100 . α β α β ω101 ω110 γ δ
γ
δ
ω111
Alleen de amplitudes die bij basistoestanden {|100i , |101i , |110i , |111i} horen worden aangepast. We kunnen dit ook schrijven volgens het net ingevoerde formalisme van (5.25): V
(0)
2 1
(1)
|ψi = |P2 ψi + |(V1 P2 ) ψi 68
met (0)
P2
We krijgen
= P (0) ⊗ I ⊗ I 1 1 1 1 = 0 0 0
(1)
P2
0
en
= P (1) ⊗ I ⊗ I 0 0 0 0 = 1 1 1
ω000 ω001 ω010 ω011 (0) (1) |P2 ψi = 0 en |V1 P2 ψi = V1 0 0 0
0 0 0 0
1
.
ω100 . ω101 ω110
(5.28)
ω111
Indien we de twee termen in (5.28) optellen dan merken we dat (5.27) en (5.28) equivalent zijn, wat de bedoeling was van de hele constructie. Alleen de ω i waarvoor bit c in de binaire voorstelling van i op 1 staat worden getransformeerd. ♦
5.6
Kwantumcomputers
Aan de hand van kwantumcircuits zijn we nu in staat om een universele kwantumcomputer te bouwen. Veel onderzoek gaat momenteel uit naar realiseerbare implementaties van kwantumbits. Er zijn verschillende experimentele idee¨en. Momenteel zijn de twee belangrijkste: • NMR: nuclear magnetic resonance, waarbij de nucleaire spins van bepaalde atomen in een molecule gebruikt worden als kwantumbit. Het indrukwekkendste resultaat is de 7-bit NMR-kwantumcomputer van IBM [46] waarmee men, in een vereenvoudigd geval van het algoritme van Shor, het getal 15 heeft gefactoriseerd. De molecule die speciaal hiervoor ontwikkeld werd door IBM is te zien in Figuur 5.9(a). Deze methode is helaas niet goed schaalbaar en men is dan ook druk op zoek naar andere methoden. • Quantum dots: een kwantumbit wordt hierbij voorgesteld door de spin van ´e´en elektron die gevangen zitten in een dot array, zie Figuur 5.9(b). Interactie tussen de kwantumbits gebeurt door de elektrostatische barri`ere tussen de twee bits te vari¨eren. Hier zijn nog geen indrukwekkende prototypes van verschenen. Het grootste probleem is momenteel het aantal bruikbare kwantumbits. Vandaar dat het momenteel niet erg realistisch geacht wordt dat we een volledige kwantumcomputer zullen bouwen naar het evenbeeld van een klassieke computer. Ook al kan een kwantumcomputer 69
(a) Molecule met 7 spin-1/2 nuclei (IBM)
(b) Quantum dots (IBM)
Figuur 5.9: Implementaties voor kwantumbits
kwantumoperaties klassieke hardware en software
kwantummodule meetresultaten
Figuur 5.10: Vereenvoudigd schema van het QRAM-model alle klassieke berekeningen uitvoeren, het systeem is er veel te complex en te duur voor. Daarom stelt men een kwantumcomputer meestal voor als een kwantummodule die aan een klassieke computer gekoppeld wordt, als een co-processor.
5.6.1
Een kwantummodule – het QRAM-model
Een model waarbij we gebruik maken van een soort kwantummodule is het QRAM-model, waarbij QRAM staat voor quantum random access machine [7]. Dit is een uitbreiding van een gewone random access machine die gebruik kan maken van kwantumbronnen. Het klassieke gedeelte van het QRAM-model kunnen we ons voorstellen als een klassieke computer die commando’s geeft aan een kwantummodule en eventueel meetresulaten terugkrijgt, zie Figuur 5.10.
70
Kwantumtaken. De kwantumtaken omvatten uiteraard het aanbieden van een kwantumgeheugen van n kwantumbits en het manipuleren van dit kwantumgeheugen door een universele set van kwantumpoorten. Het kwantumgeheugen kan, zoals bij een klassieke computer, geadresseerd worden via logische adressen in een lineaire structuur. De vergelijking met een klassieke computer gaat verder echter niet op (er zijn geen registers, geen laad- en bewaaroperaties, ...). De logische adressen zullen gebruikt worden om individuele kwantumbits aan te duiden en niet, zoals bij een klassieke computer, om een groepje van bits aan te duiden. Klassieke taken. De duidelijke klassieke taken zijn het aansturen van de module en het uitlezen van het resultaat. Voor het aansturen van de module zullen er commando’s gebruikt worden die aangeven welke kwantumpoort er op welke kwantumbits moet toegepast worden. Dat wil dus zeggen dat als men een QFT (kwantum-Fourier-transformatie) wil berekenen van een aantal bits, de klassieke computer eerst deze QFT zal herwerken naar een samenstelling van basiskwantumpoorten die ondersteund zijn door de module en dan stap voor stap deze samenstelling laat uitvoeren. De laatste stap van het QFT-algoritme bestaat uit het verwisselen van de bits zodat het resultaat terug in de goede volgorde komt te staan. Dit is een taak die de klassieke computer op zichzelf kan uitvoeren door de afbeelding van logische adressen naar fysieke adressen aan te passen. De taak van de klassieke computer bestaat dus grotendeels uit voor- en naverwerking.
5.6.2
Vereisten voor de realisatie van een kwantumcomputer
DiVincenzo heeft in [18] een lijstje gepubliceerd met de vereisten die nodig zijn voor het realiseren van een bruikbare kwantumcomputer. De 5 eisen zijn als volgt: 1. Een schaalbaar fysisch systeem met goed te onderscheiden kwantumbits. 2. De mogelijkheid om de kwantumbits te initialiseren op een bruikbare begintoestand zoals |0 · · · 00i, het zogenaamde ‘afkoelen’ van de kwantumtoestand. 3. Lange decoherentietijden die veel langer zijn dan de tijd nodig om een kwantumpoort toe te passen. Dit is nodig opdat de machine de tijd zou krijgen om iets te berekenen zonder dat de kwantumtoestand verstoord wordt. 4. De beschikking over een universele set van kwantumpoorten. 5. De mogelijkheid om specifieke kwantumbits van de machine op te meten zodat het berekende resultaat uitgelezen kan worden. De interface van een kwantumcomputersimulator moet natuurlijk aan dezelfde vereisten voldoen. De eerste eis is natuurlijk niet haalbaar: we hebben exponentieel veel bronnen nodig. Dit is juist de reden waarom we een echte kwantumcomputer willen bouwen. Van eis 3 hebben we bij een simulator geen last, wel zullen we decoherentie moeten simuleren als we hier rekening mee willen houden in de simulator. Met de eisen 2, 4 en 5 zullen we wel rekening moeten houden.
71
Source code
Quantum Machine model dependence
Standard classical code
Quantum primitives for operators
Quantum library
Quantum primitives for registers
Quantum device
Error correction tools
Quantum device controller
Software-hardware primitives translator and optimiser Standard compiler
Execute on a classical machine
Standard CPU instructions from the non-quantum core of the language
Classical Machine abstractions
Bytecode generator
Unitary operations
Instructions for quantum operators
Operator objects
Instructions for quantum registers
Register objects
Initialisations Measurements
Measurement collector Results
Address manager
Figuur 5.11: Architectuurontwerp voor Q-taal [7]
5.6.3
Een kwantumprogrammeertaal
De laatste schakel bij het bouwen van een kwantumcomputer is het programmeren van het toestel zodat het nuttige taken kan verrichten. Er zijn enkele idee¨en voor kwantumprogrammeertalen, waarvan de voornaamste twee QCL [34, 35] en Q-taal [7] zijn. In beide gevallen gaat men uit van een klassieke programmeertaal die uitgebreid wordt met kwantumregisters en -operatoren. QCL is een volledig ‘nieuwe’ ge¨ınterpreteerde programmeertaal met een ingebouwde kwantumcomputersimulator (omdat er geen bruikbare kwantumcomputers zijn). Q-taal daarentegen is een C++ bibliotheek die bytecode genereert en doorgeeft aan een back end. In feite is QCL bedoelt als simulator en experiment voor een kwantumtaal, terwijl Q-taal reeds een bruikbaar pakket wil zijn voor een echte kwantumcomputer en de mogelijkheid wil bieden om de kwantumoperaties te optimaliseren.
72
Deel II
Kwantumcomputersimulators
73
Hoofdstuk 6
Representatie van een kwantumtoestand Centraal in het ontwerp van een kwantumcomputersimulator staat de datarepresentatie van de kwantumtoestand die het geheugen van de kwantumcomputer voorstelt. Uit §2.2 weten we dat er twee belangrijke categorie¨en van kwantumtoestanden zijn vanuit het perspectief van een simulator: • pure toestanden, voorgesteld door een toestandsvector |ψi ∈ C m en • gemengde toestanden, voorgesteld door een densiteitsmatrix ρ ∈ C m×m . In dit hoofdstuk zullen we bekijken hoe deze voorstellingen omgezet kunnen worden naar zo effici¨ent mogelijke datastructuren. In het volgende hoofdstuk zullen we uitwerken hoe deze kwantumtoestanden gemanipuleerd kunnen worden.
6.1
Pure toestanden en gemengde toestanden
In §2.2 hebben we gezien dat we om de werkelijkheid te beschrijven in feite nood hebben aan gemengde toestanden. De vraag is nu of we voor een kwantumcomputersimulator ook gemengde toestanden moeten gebruiken.
6.1.1
Pure toestanden
We beginnen met het eenvoudigste geval: de toestandsvector voor het beschrijven van een pure kwantumtoestand. Voor een n-bit kwantumregister |ψi hebben we een toestandsvector met 2n complexe amplitudes: c0···00 c0···01 X n (6.1) |ψi = ck |ki = . ∈ C2 . .. k
c1···11
74
qubits 22 23 24 25 26 .. . 29 30
geheugen 64 MB 128 MB 256 MB 512 MB 1024 MB .. .
qubits 9 10 11 12 13 .. .
8 GB 16 GB
16 17
(a) puur |ψi
geheugen 4 MB 16 MB 64 MB 256 MB 1024 MB .. . 64 GB 256 GB
(b) gemengd ρ
Tabel 6.1: Benodigd geheugen in functie van het aantal te simuleren qubits We hebben dus 2n complexe getallen nodig om zo een toestandsvector in een klassieke computer voor te stellen. Een complex getal bestaat uit 2 re¨ele getallen: z = a + i b. Als datatype voor de re¨ele getallen verkiezen we het type double omdat dit het snelste verwerkt wordt door de huidige generatie van computers en we, vanwege de verwachte exponenti¨ele tijdscomplexiteit, de simulatie zo snel mogelijk willen laten uitvoeren. Een double neemt 8 bytes geheugen in (IEEE 754), een complex getal heeft dus in principe 16 bytes geheugen nodig (tenzij we werken op een exotische architectuur met vreemde aligneringseisen). In Tabel 6.1(a) zijn de geheugeneisen te zien om een bescheiden kwantumcomputer te kunnen simuleren. Bescheiden, want met een 30-bit geheugen kan je niet veel doen, zelfs niet op een kwantumcomputer: een kwantumbit kan immers maar evenveel informatie bevatten als een klassieke bit. Op een hedendaagse desktop computer zal 24 qubit ongeveer de limiet zijn.
6.1.2
Gemengde toestanden
Het zal geen verrassing zijn dat de geheugenvereisten voor een densiteitsmatrix enorm zwaar zijn. In Tabel 6.1(b) is het benodigde geheugen te zien in functie van het aantal qubits. De densiteitsmatrix heeft dimensies 2 n × 2n : ρ ∈ C2
n ×2n
.
(6.2)
Indien we een kwantumregister van 22 qubits zouden nemen, dan hebben we voor een toestandsvector 64 MB nodig, maar voor een densiteitsmatrix wordt dat 222 · 222 · 16 B = 28 · 240 B = 256 TB.
De limiet voor een hedendaagse desktop computer ligt voor densiteitsmatrices bij 12 qubits. Om het getal 15 te factoriseren met het kwantumalgoritme van Shor hebben we 21 qubits nodig, 12 is dus nogal weinig.
75
kwantumsysteem Au-elektronen In-iontrap elektron spin kwantumdot nucleaire spin
tG (sec) 10−14 10−14 10−7 10−6 10−3
tφ (sec) 10−8 10−1 10−3 10−3 104
N 106 1013 104 103 107
Tabel 6.2: Bovengrens van het aantal kwantumbewerkingen door decoherentie [17]
6.1.3
Pure of gemengde toestanden?
Of we in een kwantumcomputersimulator nu voor de toestandsvectorvoorstelling kiezen of voor de densiteitsmatrices, hangt af van het beoogde doel. Simuleren van realiseerbare kwantumcomputers Indien we een echte kwantumcomputer willen simuleren, moeten we uiteraard de aspecten decoherentie en niet-ideale kwantumpoorten modelleren. De logische manier om dat te doen is de kwantumtoestand van de machine voor te stellen door een densiteitsmatrix. Deze densiteitsmatrix kan dan aangepast worden met een decoherentiemodel dat de experimenteel vastgestelde decoherentie van superposities in de kwantumtoestand modelleert. In Tabel 6.2 zijn gegevens te zien voor enkele mogelijke kwantumcomputerimplementaties. In de tabel geeft tG de minimale tijd aan om een kwantumpoort toe te passen, t φ is de experimenteel vastgestelde maximale coherentietijd van een superpositie en N is de verhouding van de twee en geeft het maximum aantal kwantumpoorten dat uitgevoerd kan worden zonder decoherentie. Het is duidelijk dat men een heleboel experimentele gegevens nodig heeft om decoherentie te simuleren. Een ander aspect dat gemodelleerd moet worden is het niet-ideale gedrag van de kwantumpoorten die men gebruikt. Een P h(δ)-poort zal misschien de toestand te ver verdraaien en misschien zelfs meer doen dan alleen de fasedraaiing van de toestand wijzigen. Ook hier hebben we in principe experimentele gegevens nodig. Niet-ideale kwantumpoorten kunnen we wel eenvoudig simuleren zonder dat we beroep moeten doen op densiteitsmatrices. In §5.3.1 hebben we gezien hoe een unitaire matrix ontbonden kan worden in enkele basisbewerkingen, zie (5.3). We kunnen dus relatief eenvoudig een extra kleine fasedraaiing of een extra kleine x-rotatie geven aan een kwantumpoort door de poort voor te stellen door een geperturbeerde matrix. Simuleren van kwantumalgoritmen Voor het zuiver simuleren van kwantumalgoritmen hebben we echter geen nood aan de effecten van decoherentie en ook de gebruikte kwantumpoorten kunnen we hier ideaal veronderstellen. De bedoeling is om de werking van een kwantumalgoritme te simuleren en het exacte resultaat te kunnen bestuderen. Het goede nieuws is dat we in dit geval voldoende hebben aan pure toestanden en dus gebruik kunnen maken van een toestandsvector in plaats van een 76
densiteitsmatrix. Bijna alle kwantumcomputersimulatoren die terug te vinden zijn op het internet kiezen voor ideale simulaties met pure toestanden (voor een overzicht zie [50]). De simulatoren die toch een werkelijk model van een kwantumcomputer trachten te simuleren, zijn ofwel specifieke implementaties om theoretische modellen met de werkelijkheid te vergelijken ofwel implementaties met een toestandsvector waarop men perturbaties uitvoert. De belangrijkste reden voor die keuze is uiteraard de hoeveelheid geheugen die een densiteitsmatrix nodig heeft, waardoor het bijna noodzakelijk is om de simulator op een verspreid geheugen architectuur te draaien.
6.2
Datastructuren voor pure toestanden
We kiezen er hier voor om enkel met pure toestanden te werken en zoeken datastructuren om de toestandsvector van de amplitudevoorstelling te implementeren. In het theoretische gedeelte hebben we steeds over een toestandsvector |ψi gesproken, we zullen deze (vector) x noemen wanneer we het over de implementatie hebben.
6.2.1
Datastructuren en talen
De logische omzetting voor een vector is natuurlijk een ´e´endimensionale rij. Bijna alle datarepresentaties die we bespreken zijn dan ook van die vorm. Verder is er op te merken dat de uiteindelijke datarepresentatie sterk afhangt van de programmeertaal en simulatieomgeving. Zo is het in Matlab evident om de ingebouwde vectorvoorstelling te gebruiken. De datastructuren in Matlab zijn allen gebaseerd op het type struct mxArray en kunnen we vereenvoudigd voorstellen (voor numerieke data die in Matlab zelf aangemaakt is) als: struct mxArray { char *name; int m; int n; double *data; double *imag_data; };
Een matrix met complexe getallen wordt in Matlab voorgesteld door twee re¨ele matrices, indien er alleen re¨ele getallen in de matrix zitten dan is imag_data een null-pointer. Voor C en C++ is er echter zeer veel keuze. Zo zit er in de recente C99 standaard [24], ISO/IEC 9899:1999, een uitbreiding voor complexe getallen om de mogelijkheden gelijk te trekken met Fortran. Zo kunnen we in C99 eenvoudig een lijst van complexe double’s defini¨eren en er standaardbewerkingen op uitvoeren: #include
#include double complex v[] = { 1+2*I, -3-5*I, 4 }; double complex z; z = cos(v[0]) + 2. * v[1] / v[2];
77
De ondersteuning voor C99 in gcc 3.0 is echter nog onvolledig, zie hhttp://gcc.gnu.org/gcc-3.0/ c99status.htmli. Zo zijn er onder andere problemen op 64-bit platformen met de uitbreiding van de complexe getallen. Ook de implementatie van type generic math (tgmath.h) om gewoon cos te kunnen schrijven in plaats van ccos blijkt nog niet goed te werken op nietIntel architecturen. Een andere mogelijkheid in C is het gebruik van de Gnu Scientific Library [41] (GSL), die ondersteuning biedt voor het werken met matrices en vectoren. In GSL is platformonafhankelijke ondersteuning voor complexe getallen ingebouwd (zodat het re¨eel gedeelte en het imaginair gedeelte opeenvolgend in het geheugen zitten). GSL biedt een hele bibliotheek met numerieke routines aan, o.a. FFT, BLAS, Monte-Carlo, eigenwaarden, ... en heeft interessante datastructuren voor matrices en vectoren. Bijvoorbeeld voor een vector: typedef struct { size_t size; size_t stride; double *data; gsl_block *block; int owner; } gsl_vector;
Er is rechtstreekse ondersteuning om met een bepaalde stride door een vector te stappen of deelvectoren uit een vector te halen door alternatieve zichten aan te maken. Een gelijkaardige werkwijze wordt gebruikt voor matrices. Voor deze alternatieve zichten moet er uiteraard geen data gekopieerd worden (vandaar het owner veld in struct gsl_vector.) Voor C++ zijn er ook verschillende keuzemogelijkheden om met complexe getallen te werken. Zo zit er in de STL een type std::complex. In gcc 3.0 worden de nieuwe standaard C99types reeds gebruikt en wordt std::complex<double> vervangen door complex double. De keuze voor de experimentele kwantumcomputersimulator die we hier stukje voor stukje zullen bespreken, focust zich op Matlab omdat dit een interactieve omgeving is met heel wat extra functionaliteit. Zo kunnen de klassieke stukken uit de kwantumalgoritmen op een eenvoudige manier door de gebruiker geprogrammeerd worden (zonder gebruik te maken van een compiler). Om snelheidswinst te boeken, zullen we gebruik maken van de C-interface van Matlab, mex, en zo de kritieke stukken code in C (of C++) schrijven. We bouwen ook nog aan een andere kwantumcomputersimulator in de functionele taal Haskell omdat we zo een volledig andere kijk krijgen op de toestandvoorstelling. Haskell biedt op een natuurlijke manier een mooie representatie aan voor het voorstellen van een kwantumtoestand en geeft in zijn natuurlijke vorm reeds enkele (beperkte) optimalisaties. In Haskell zullen we gebruik maken van een recursieve boomstructuur.
6.2.2
Universums
Wanneer we in een kwantumalgoritme twee registers beschouwen, dan kunnen we die twee registers in het algemeen niet voorstellen als twee afzonderlijke toestandsvectoren aangezien deze twee registers met elkaar verstrengeld kunnen zijn. We zullen de registers die met elkaar verstrengeld kunnen raken hierdoor moeten voorstellen als ´e´en toestandsvector. Dit zal bijna steeds het geval zijn, want verstrengeling is juist de krachtige eigenschap die ons een 78
O x1 ∈ O 1 x = x1 ⊗ x2 ⊗ x3 ∈ O ⇔ x ∈ O2 2 x3 ∈ O 3
O1
O2
O3
Figuur 6.1: Gescheiden universums bij niet-verstrengelde deelsystemen exponenti¨ele versnelling moet geven ten opzichte van klassieke algoritmen en een exponenti¨ele vertraging bij het simuleren. Indien we een kwantumalgoritme beschouwen met 12 ingangsbits en 6 uitgangsbits die willekeurig verstrengeld kunnen raken, dan zullen we een toestandsvector x van 18 qubits moeten beschouwen in ´e´en kwantumuniversum O: x = |i11 , i10 , . . . , i0 ; o5 , o4 , . . . , o0 i
c000000000000;000000 c000000000000;000001 18 .. = ∈ C2 = C262144 . . c111111111111;111110 c111111111111;111111
(6.3)
In §2.1.3 hebben we gezien dat toestanden in de Π en Λ partities te ontbinden zijn als een tensorproduct over de deelruimten H i van de Hilbert-ruimte H van de totale toestand N |ψi ∈ H(Π ∪ Λ) ⇔ i |ψi i , |ψi i ∈ Hi . (6.4)
Dat wil ook zeggen dat we de totale kwantumtoestand van de kwantumcomputer x kunnen voorstellen als (zie Figuur 6.1) N x= xi ∈ O i . (6.5) i xi ,
Deze xi kunnen afzonderlijke variabelen of registers zijn, maar ze kunnen even goed collecties van willekeurige bits zijn. Dat we ze in aparte universums kunnen voorstellen wil niet zeggen dat er geen interactie tussen ‘variabelen’ in deze verschillende ruimten mogelijk is.
Zolang we geen verstrengeling tussen twee toestanden x i ∈ Oi en xj ∈ Oj met Oi 6= Oj cre¨eren, kunnen we xi en xj blijven gebruiken. Wanneer er verstrengeling zal ontstaan door een bepaalde operatie, dan moeten we de toestand eerst voorstellen in een gezamenlijke toestandsvector xi,j ∈ Oi,j . Die vector stellen we samen als alle mogelijke combinaties tussen xi en xj door het tensorproduct te nemen: xi,j = xi ⊗ xj .
We bekomen op deze manier een belangrijk idee: 79
(6.6)
• Zonder verstrengeling hebben we voldoende aan twee afzonderlijke toestandsvectoren. x1 ∈ C n → x = [x1 , x2 ] ∈ Cn+m (6.7) x2 ∈ C m • Met verstrengeling moeten we alles samenvoegen in ´e´en toestandsvector om de kwantumcorrelaties te kunnen modelleren. x ˜ 1 ∈ Cn → x ∈ (Cn ⊗ Cm ) ∼ (6.8) = Cnm x ˜ 2 ∈ Cm De aparte vectoren x1 en x2 bestaan niet. We kunnen hun toestand alleen beschrijven door middel van de gezamenlijke toestand x. De vectoren x ˜ 1 en x ˜2 zijn een soort gereduceerde toestandsvectoren om aan te geven in welke ruimte de deelsystemen schijnbaar leven. Voorbeeld 6.1. Een kwantumregister van 12 bit waarbij geen enkele verstrengeling aanwezig is, kan worden voorgesteld door een complexe vector met lengte 12 · 21 = 24. Met twee keer twee bits verstrengeld, zijn dit 3 vectoren met totale lengte 8 · 21 + 22 + 22 = 24. Met ´e´enmaal 6 bit verstrengeld en ´e´enmaal 4 bit verstrengeld 2 · 21 + 26 + 24 = 84. Met alle bits verstrengeld 212 = 4096. ♦
6.2.3
Aanpassingen ter plaatse voor manipulaties
Omdat de toestandsvector zoveel geheugen nodig heeft, zullen we trachten te zorgen dat aanpassingen aan de toestandsvector ter plaatse gebeuren. Uit Voorbeeld 5.1 weten we dat het toepassen van een 1-bit poort en het toepassen van een conditionele 1-bit poort in feite neerkomt op het toepassen van een unitaire 2 × 2 matrix α β , (6.9) V = γ δ behorende bij de poort, op twee bij elkaar horende co¨effici¨enten van de toestandsvector. De afstand tussen die twee elementen (de stride) kunnen we berekenen uit k (zie verder in §7.3). Voor een 1-bit poort zullen we 2 n /2 matrixvectorvermenigvuldigingen (2 × 2 ) moeten uitvoeren. Voor een conditionele poort moet de vermenigvuldiging alleen maar uitgevoerd worden wanneer de controlebit c gezet is, in het totaal 2 n /4 matrixvectorvermenigvuldigingen (2 × 2). 80
We kunnen dus tijdens de bewerking de originele toestandsvector overschrijven. .. .. .0 . a a .. . = V . k .. 0 b b .. .. . .
(6.10)
Indien dit niet het geval zou zijn, dan zouden we dubbel zoveel geheugen nodig hebben: voor de huidige toestandsvector en voor de nieuwe toestandsvector. In cijfers: 512 MB in plaats van 256 MB voor de simulatie van een 24-bit kwantumcomputer.
6.2.4
Volle en ijle vectorvoorstelling
Volle vectorvoorstelling De eenvoudigste voorstellingswijze is uiteraard een complexe vector x met 2 n co¨effici¨enten. Zoals reeds in Tabel 6.1(a) te zien was, zijn we hierdoor zeer beperkt wat betreft het aantal qubits n dat we kunnen voorstellen. De tijd nodig om ´e´en elementaire bewerking (een kwantumpoort) uit te voeren op het voorgestelde kwantumgeheugen is recht evenredig met zijn grootte en heeft dus ook een exponenti¨ele complexiteit. Bij het starten van de kwantummachine wordt de toestand ‘afgekoeld’ (eerste punt van DiVicenzo’s lijstje, §5.6.2) zodat alle qubits in de zuivere positie |0i terechtkomen. Indien we bijvoorbeeld een systeem simuleren met 24 qubits dan is deze eenvoudige voorstelling een blok van 256 MB geheugen, gevuld met 16 777 215 nullen en ´e´en ´e´en (op de eerste positie). Het toepassen van ´e´en 1-bit kwantumpoort op deze vector resulteert in een nieuwe toestand waarin elk element een lineaire combinatie is van zijn oude toestand en een ander element uit de oude vector. We zullen met andere woorden hoogstens ´e´en ander element niet-nul maken in 14 · 2n bewerkingen, kortom O(2n ). Er zijn dus twee punten waar we aandacht aan moeten schenken: • de indrukwekkende kwantumalgoritmen maken veelvuldig gebruik van verstrengeling om een (liefst) exponenti¨ele versnelling te krijgen ten opzichte van klassieke algoritmen en • deze verstrengeling is niet continu aanwezig en op die momenten met geen of weinig verstrengeling kunnen we veel effici¨entere datastructuren gebruiken. Ijle vectorvoorstelling Uit de vorige paragraaf kunnen we dus besluiten dat we voordeel kunnen halen uit een ijle voorstelling van de toestandsvector. Hoe we dit het beste doen is natuurlijk afhankelijk van de operaties die we op deze vector zullen uitvoeren. In Matlab zouden we kunnen proberen om gewoon de standaard ijle (sparse) vectorvoorstelling te gebruiken. Maar zo een formaat is onbruikbaar wanneer de ijle vector zelf telkens aangepast moet worden. 81
=
320 MB · (16 + 4) B
224
Figuur 6.2: Hashtabel voor een 25-bit kwantumregister Het eenvoudigste ijle formaat voor een vector is een voorstelling met een extra indexeringsvector: struct sparseVector { int m; // int nzmax; // int nnz; // int *idx; // double *data; // double *imag_data; };
lengte van de vector maximum (gealloceerde) lengte aantal niet-nul elementen posities van de niet-nul elementen de data zelf
Het is duidelijk dat zo een gegevensstructuur onbruikbaar is voor het beoogde doel: de nieuw gecre¨eerde elementen kunnen alleen maar achteraan toegevoegd worden terwijl we ze geordend nodig hebben voor het (effici¨ent) toepassen van de volgende kwantumpoort. Het ijle vectorformaat van Matlab heeft hetzelfde probleem. De enige gegevensstructuur in Matlab is een matrix en voor een ijle matrix ziet dat er (vereenvoudigd) als volgt uit: struct { char *name; int m; // int n; // int nzmax; // int *ir; // int *jc; // double *data; // double *imag_data;
aantal rijen aantal kolommen maximum (gealloceerde) lengte rijindexering kolomteller de data zelf
};
De jc vector geeft aan hoeveel niet-nul elementen er zich bevinden in een bepaalde kolom (Matlab is kolomgeori¨enteerd). Bijvoorbeeld het aantal niet-nul elementen in kolom 3 is jc[4]-jc[3]. De vector ir geeft voor elke niet-nul element de rij waarin het zich bevindt. Deze gegevensstructuur is enkel aanpasbaar als we elementen vervangen die verschillend van nul zijn of die toegevoegd worden achter het tot hiertoe laatste niet-nul element. De Matlab ijle voorstelling is hierdoor niet geschikt voor ons doel. We kunnen wel een geschikte ijle voorstelling uitdenken wanneer we een hashtabel met overloop zouden gebruiken. We kunnen dan vertrekken met een tabel die bijvoorbeeld maar half zo groot is. Wanneer er weinig verstrengeling is zal een eerste niveau van buckets grotendeels volstaan. Bij een botsing genereren we dan een overloop-bucket op niveau twee. Indien we met twee niveaus werken dan kunnen we met de helft van het geheugen een 50% verstrengelde toestandsvector beschrijven. Een voorbeeld voor een 25-bit kwantumregister is te zien in Figuur 6.2. We hebben nu 20 bytes per element nodig in plaats van 16 bytes, wat een 82
totaal geeft van 640 MB in plaats van 512 MB voor 25 bit. Een kleine verhoging voor een snellere rekentijd. Het probleem met deze oplossing is de grote spreiding voor opeenvolgende elementen. In een aantal kwantumcomputersimulators, o.a. QCL en jaQuzzi, die te vinden zijn in [50], worden hashtabellen gebruikt om de toestandsvector bij te houden, echter zonder rekening te houden met de consequenties. QCL maakt een nieuwe hashtabel van dubbele grootte aan wanneer er overloop is en jaQuzzi gebruikt de standaard java.util.HashTable klasse.
6.2.5
Algebra¨ısche voorstelling
Een zeer interessante kwantumcomputersimulator uit het overzicht van Wallace [50] leek die van Jan Skibinski [44], in de functionele taal Haskell. Het internetdomein hnumeric-quest.comi waar de simulator op te downloaden was, was op het moment dat ik de simulator wou testen spijtig genoeg offline en is op het moment van schrijven nog steeds offline. Gelukkig heb ik twee belangrijke delen van de simulator kunnen recupereren uit de cache van Google. Doordat het emailadres van de auteur echter gekoppeld was aan dezelfde domeinnaam, heeft het lange tijd geduurd voor ik de auteur eindelijk kon contacteren. De uiteindelijke communicatie was een teleurstelling: Sorry Dirk, due to the hard disk failure I can not immediately retrieve the files I promissed. I was planning to look into this problem last weekend, but unfortunately the plans had to be postponed due to other unexpected yet important matters. This might seem like a lame excuse, but believe me – it is not. The host that used to act as a numeric quest server seriously failed recently and I cannot access it as is – unless I undertake some serious repair of the filesystems. Unfortunately, due to my move from Huntsville to Toronto I misplaced and, so it seems, lost my backups as well. I still hope to recover the data soon and if and when it is done I’ll send the promissed files to you. Sincerely, Jan Skibinski Ik heb dan ook getracht om deze simulator opnieuw te vervolledigen, vertrekkende van ´e´en Haskell-module QuantumVector.lhs en de documentatie uit QuantumComputer.html die ik nog had kunnen redden. (Ook op hhttp://web.archive.orgi is de Haskell-module met de simulatorcode niet terug te vinden.) De keuze van Haskell voor het modelleren van kwantummechanica is relatief makkelijk te verantwoorden. Het is namelijk niet zo moeilijk om in Haskell een bepaalde algebra te modelleren. Voor een inleiding en een voorbeeld voor het voorstellen van een Hilbert-ruimte zie [28]. De mogelijkheid van Haskell om symbolische manipulaties met numerieke manipulaties op een mooie manier te combineren, biedt hier de mogelijkheid om een elegante beschrijving van het probleem te geven. Jan Skibinski heeft in zijn QuantumVector.lhs module dan ook getracht het volledige kwantummechanische Dirac-formalisme te modelleren, met succes. Voor de voorstelling van de kwantumtoestand gebruiken we nog steeds de amplitudebeschrijving. Ditmaal echter niet in een vector, maar op een pen-en-papier manier, bijvoorbeeld: 83
0.577 |1>|1> + 0.577 |1>|0> + 0.577 |0>|0>
voor de toestand x=
√1 3
(|11i + |10i + |00i).
(6.11)
We gebruiken dus een expliciete voorstelling van complexe amplitudes en hun bijhorende basisvector. Het is duidelijk dat deze voorstelling ook 2 n co¨effici¨enten heeft indien alle basisvectoren in superpositie komen te staan. Maar voor een toestand met weinig co¨effici¨enten kunnen we dit vergelijken met een ijle vectorvoorstelling omdat we expliciet tensorproducten kunnen noteren: |0> <*> (0.707 |0> + 0.707 |1>) <*> [0.707 |0>|1> + 0.707 |1>|0>]
voor de toestand x = |0i ⊗
√1 (|0i 2
+ |1i) ⊗
h
√1 2
|01i +
√1 2
i |10i ,
(6.12)
wat in feite een ontbinding is over drie Hilbert-ruimten: H 1 ⊗ H2 ⊗ H3 . De volledige Haskell-datastructuur is recursief als volgt gedefinieerd: data Register = Single Qubit | Product Register Register | Sum (Scalar, Register) (Scalar, Register) data Bit = Zero | One type Qubit = Ket Bit
Een belangrijk probleem dat zich voordoet bij deze datastructuur is dat ´e´en kwantumtoestand op verschillende manieren kan worden voorgesteld. We kunnen de vorige kwantumtoestand evengoed voorstellen als 0.5 |0>|0>|0>|1> + 0.5 |0>|0>|1>|0> + 0.5 |0>|1>|0>|1> + 0.5 |0>|1>|1>|0>
wat een letterlijke omzetting is van de toestandsvector, maar helemaal niet meer effici¨ent: want dit is een toestand in C16 in plaats van in C8 (dit verschil stijgt exponentieel voor grotere waarden). Het is de bedoeling dat we de toestand zo gefactoriseerd mogelijk trachten te houden. Dat dit een probleem was, werd door Jan Skibinski ook al onderkend: in een post op de GHC-mailinglijst zoekt hij een goeroe in functionele datastructuren om het een en ander op te helderen. Dat er geen oplossing is voor dit probleem zou duidelijk moeten zijn na het lezen van §2.3. Alleen voor 2×2 en 2×3 zijn er mogelijke oplossingen, maar in een kwantumcomputersimulator gaat het natuurlijk steeds over grotere deelsystemen. Ondanks het bovenvermeld probleem geeft deze voorstellingswijze experimenteel zeer goede resultaten. Veel hangt natuurlijk af van de manier waarop de datamanipulaties ge¨ımplementeerd zijn. Een probleem dat niet al te eenvoudig opgelost kan worden, is verstrengeling van niet naast elkaar liggende bits. Beschouwen we een 12-bit kwantumregister waarvan alleen x 0 en x11 verstrengeld zijn. Dan zal, door de definitie van de datastructuur, het niet-verstrengelde gedeelte van 10 qubits twee keer bijgehouden worden: i i h N h N 1 1 B . A + β xB ⊗ x ⊗ x (6.13) x ⊗ x x = α xA ⊗ i i 0 0 11 11 i=10 i=10 84
Hierdoor hebben we het equivalent van een complexe vector met 44 co¨effici¨enten in plaats van 24 co¨effici¨enten wanneer de twee verstrengelde bits naast elkaar gelegen hadden. Een mogelijke uitbreiding om dit probleem op te lossen bestaat erin om expliciet de positie van een bit bij te houden; in de huidige datastructuur gebeurt dit impliciet door zijn positie in de datastructuur. Bijvoorbeeld door gebruik van een hashtabel, maar dit verzwaart de manipulatie van de kwantumtoestand nogal sterk. Deze datastructuur is dan ook niet uitgewerkt.
6.2.6
Geblokte voorstelling
Naar aanleiding van communicatie over verstrengeling en het ontbinden van toestandsvectoren in tensorproducten met Koenraad Audenaert, stootte ik op een artikel van Jozsa en Linden [27] dat een gelijkaardig effect beoogde als de Haskell-implementatie per toeval had. Het artikel handelt over de rol van verstrengeling in kwantumalgoritmen met betrekking tot een mogelijke exponenti¨ele versnelling ten opzichte van klassieke algoritmen. E´en van de resultaten in het artikel is ondermeer het in §2.1.4 reeds aangeraakte vermoeden dat verstrengeling een noodzakelijk element is om een exponenti¨ele versnelling te kunnen bekomen. In [27] presenteert men een klasse van kwantumalgoritmen die te simuleren zijn in een polynomiale tijd. Men noemt deze algoritmen p-geblokt (p-blocked) als de toestandsvector waarop ze werken p-geblokt is. Definitie 6.1 (p-geblokte toestand). De toestandsvector |ψi van een n-bit kwantumregister is p-geblokt als de verzameling bits, B = {1, 2, . . . , n}, kan opgedeeld worden in partities Bi die maximaal p kwantumbits bevatten: B = B 1 ∪ B2 ∪ · · · ∪ B k
met |Bi | ≤ p
(6.14)
en de toestandsvector |ψi kan voorgesteld worden als een tensorproduct |ψi = |ψ1 i ⊗ |ψ2 i ⊗ · · · ⊗ |ψk i ,
(6.15)
met alleen maar kwantumbits uit partitie B i in toestand |ψi i.
Het artikel van Jozsa en Linden spreekt (als ´e´en van de enige van de geraadpleegde literatuur) effectief over simulatietechnieken voor simulatie van een kwantumcomputer door een klassieke computer en definieert een datastructuur waarmee een p-geblokt algoritme met een polynomiale complexiteit gesimuleerd kan worden. Een p-geblokte toestandsvector voor n qubits kan voorgesteld worden door een datastructuur die bestaat uit twee delen: 1. bloklocaties: een lijst van n getallen die aanduiden in welk toestandsblok de overeenkomstige kwantumbit terug te vinden is; 2. toestandsblokken: voor elk blok van maximaal p qubits wordt er een toestandsvector met 2p complexe co¨effici¨enten bijgehouden in de berekeningsbasis van die p qubits. Indien we p vast beschouwen en n laten vari¨eren dan bekomen we een polynomiale complexiteit in plaats van een exponenti¨ele complexiteit bij onbegrensde p. We kunnen nu twee gevallen onderscheiden tijdens simulatie van het toepassen van een 2-bit kwantumpoort: 85
1. de twee kwantumbits bevinden zich in dezelfde toestandsblok B i : enkel de co¨effici¨enten in deze blok wijzigen; 2. de twee kwantumbits bevinden zich in verschillende toestandsblokken B i en Bj van groottes pi en pj : de poort wordt toegepast nadat de twee blokken samengevoegd zijn. Twee gevallen kunnen zich voordoen: • Het aantal bits van de samengevoegde toestand is kleiner dan of gelijk aan het maximum toegestane, pi + pj ≤ p: het nieuwe blok wordt toegevoegd, de twee oude blokken worden verwijderd en de referenties in de bloklocatielijst worden aangepast. • Het aantal bits van de samengevoegde toestand is groter dan het maximum toegestane, pi + pj > p: we moeten uit dit grote blok twee nieuwe blokken maken die de samengestelde toestand volledig beschrijven. Men suggereert om alle mogelijke opdelingen te proberen en een geschikte opdeling te gebruiken. Door te eisen dat het algoritme p-geblokt is, weet men zeker dat zo een opdeling bestaat en voor een vaste p in polynomiale tijd te vinden is. Men gaat nog iets verder en bewijst dat men voor een bepaalde en η een kwantumalgoritme kan η-benaderen met voor elke stap i een p-geblokte toestand β i die de echte toestand αi -benadert kαi − βi k ≤ , (6.16) zodat de waarschijnlijkheidsdichtheidsdistributies van het originele algoritme P en van de benadering P 0 voldoen aan kP − P 0 k ≤ η. (6.17) Dit is in principe de veralgemening van wat men toepast bij het aangepaste QFT-algoritme, waar men gecontroleerde fasedraaiingen P h(δ) over zeer kleine hoeken – dit zijn diegene die tussen verafgelegen kwantumbits gebeuren – simpelweg niet uitvoert. Stabiliteit van de simulatie. We moeten ons in feite nog afvragen of een simulatie van een kwantumsysteem wel haalbaar is. Hoe sterk wegen de onvermijdelijke afrondingsfouten in de voorstelling van de toestandsvector door? Uit (6.16) en §5.3.3 (benaderingen voor kwantumpoorten) kunnen we vaststellen dat kleine perturbaties de algoritmen niet danig in de war zullen sturen. Verder hebben we ook steeds te maken met unitaire transformaties van de toestandsvector. We kunnen hieruit besluiten dat een kwantumcomputersimulator volgens dit model numeriek stabiel zal zijn. Buiten de exponenti¨ele complexiteit is een kwantumcomputer perfect simuleerbaar op een klassieke computer. Door de afrondingsfouten hebben we nood aan een functie die de toestandsvector kan opkuisen op het einde van een algoritme. Hierbij zullen we dan gewoon alle waarden kleiner dan een bepaalde gelijk aan 0 stellen.
86
Hoofdstuk 7
Simulatoralgoritmen In dit hoofdstuk worden de algoritmen besproken die deel uitmaken van een kwantumcomputersimulator. De simulator wordt hier beschouwd als een aantal functies op hoog niveau die op de juiste manier aan elkaar gekoppeld kunnen worden om eender welk kwantumalgoritme te simuleren.
7.1
Benodigde functionaliteiten
Volgende manipulaties van de kwantumtoestand zijn vereist in een kwantumcomputersimulator: 1. initialiseren van de kwantumtoestand op |0 · · · 00i; 2. toepassen van een 1-bit kwantumpoort op bit k; 3. toepassen van een conditionele 1-bit kwantumpoort op bit k, afhankelijk van bit c; 4. opmeten van het register of een aantal kwantumbits en 5. de kans berekenen dat we bij observatie een bepaalde toestand waarnemen. Het laatste punt betreft in feite een interne functie: bij een echte kwantumcomputer is zoiets niet mogelijk. In een simulator is het echter nuttig om de waarschijnlijkheden van de verschillende basistoestanden te plotten om zo het gedrag van een kwantumalgoritme te kunnen bestuderen. We maken gebruik van de resultaten van Barenco et al. [3] die aantoonden dat we voldoende hebben aan 1-bit poorten en conditionele 1-bit poorten. De universele set die we gebruiken is: G = {U(1) , ∧1 (U(1) )} met U(1) ∈ U(2). (7.1) Voor elke 1-bit kwantumpoort die de gebruiker wenst te gebruiken, moet de transformatie opgegeven worden door middel van de 2 × 2 matrix die bij die poort hoort en waarvan we enkele typische voorbeelden hebben gezien in §4.2. 87
We bespreken de algoritmen voor twee mogelijke datastructuren: • een Matlab-vector x van grootte 2n voor een n-bit kwantumregister n
x ∈ C2 ,
(7.2)
en • de Haskell-datastructuur uit het vorige hoofdstuk, die we hier nogmaals herhalen: data Register = Single Qubit | Product Register Register | Sum (Scalar, Register) (Scalar, Register) data Bit = Zero | One type Qubit = Ket Bit
7.2
Initialiseren van de kwantumtoestand
In Matlab Het initialiseren van de kwantumtoestand is zeer eenvoudig. Voor de Matlab vectorvoorstelling volstaat het een vector aan te maken waarvan het eerste element een 1 is. x = zeros(pow2(n), 1); x(1) = 1;
Op dezelfde manier kan men makkelijk willekeurige toestandsvectoren defini¨eren door gebruik te maken van de ingebouwde functies van Matlab. Men moet er wel op letten dat de vector genormaliseerd is. In Haskell In Haskell is het initialiseren op |0 · · · 00i al even makkelijk: x = initialize n
initialize :: Int -> Register initialize 1 = Single (Ket Zero) initialize n = Product (Single (Ket Zero)) (initialize (n-1))
Een willekeurige toestand kan opgebouwd worden aan de hand van de binaire voorstelling van de basistoestand.
7.3
Toepassen van 1-bit kwantumpoorten
In Matlab Het toepassen van een 1-bit kwantumpoort V op bit k, genoteerd als V k hebben we besproken in §5.4. x ← Vk x (7.3) 88
We passen de evolutie-operator U = V k toe op de toestandsvector x, die gedefinieerd is als ⊗(2n −1−k)
U = I2
⊗ V ⊗ I2⊗k .
(7.4)
Voor een n-bit kwantumtoestand is deze evolutie-operator een 2 n × 2n complexe matrix. Deze matrix is uiteraard veel te groot om in het geheugen bewaard te worden. We zullen gebruik maken van zijn speciale structuur om de berekening veel effici¨enter uit te voeren. Voorbeeld 7.1. We bekijken de structuur van de evolutie-operator U voor een 3-bit kwantumregister |x2 , x1 , x0 i waar we een 1-bit poort V op toepassen met α β . (7.5) V = δ γ • V toegepast op k = 0:
• V toegepast op k = 1:
• V toegepast op k = 2:
U = V0 = I ⊗ I ⊗ V α β γ δ α β γ δ ; = α β γ δ α β γ δ U = V1 = I ⊗ V ⊗ I α β α β γ δ γ δ ; = α β α β γ δ γ δ U = V2 = V ⊗ I ⊗ I α β α β α β α β . = γ δ γ δ γ δ γ δ
89
(7.6)
(7.7)
(7.8)
♦
d = 20 = 1 000
d = 21 = 2
000 001
111
111
001 111
010
010
110
110
010
011 101
100
(a) V0 , k = 0
d = 22 = 4
110
011 101
000
001
100
(b) V1 , k = 1
011 101
100
(c) V2 , k = 2
Figuur 7.1: De aanpassing gebeurt in blokken van d = 2 k elementen Na het bestuderen van het voorbeeld is het duidelijk dat we 2 n /2 keer een matrixvectorvermenigvuldiging van 2 × 2 moeten uitvoeren. Deze optimalisatie wordt in de helft van de simulatoren toegepast, maar sommige simulatoren, voornamelijk in Mathematica, stellen de volledige 2n × 2n matrix op en doen dan een matrixvector vermenigvuldiging. In o.a. de jaQuzzi-simulator [50] maakt men wel gebruik van deze reductie in geheugengebruik, maar men gebruikt er een bitvector van 2n elementen om dan lineair door de vector x te lopen en element per element aan te duiden welke men reeds gehad heeft. We kunnen het aanpassen van de elementen echter makkelijk in blokken opdelen waardoor zo een extra bitvector helemaal niet nodig is. De afstand tussen twee elementen die we hercombineren tot nieuwe waarden is d = 2 k en we doen dit in blokken van d elementen achter elkaar. Figuur 7.1 zou dit moeten verduidelijken voor de toepassingen van V k uit Voorbeeld 7.1. Het Matlab-algoritme voor het toepassen van een 1-bit kwantumpoort wordt hierdoor zeer eenvoudig: Algoritme 7.1: Matlab apply function [x] = apply(G, k, x) dim = length(x); d = pow2(k);
% the number of basis states % projected distance for k in x
for i = 0:2*d:dim-1 for j = i:i+d-1 % update j and j+d p = G * [x(j+1); x(j+d+1)]; % apply gate x(j+1) = p(1); x(j+d+1) = p(2); % update x end; end;
De twee for-lussen zouden we natuurlijk liever laten verdwijnen en vervangen door BLAS3routines. De binnenste for-lus kunnen we vervangen door een matrixmatrixproduct door het gebruik van de reshape-functie.
90
Algoritme 7.2: Matlab apply geoptimaliseerd for i = 0:2*d:dim-1 x(i+1:i+2*d) = reshape(reshape(x(i+1:i+2*d), d, 2) * G.’, 2*d, 1); end;
Ik heb zelf geen oplossing gevonden om de buitenste lus om te vormen zonder gebruik te maken van grotere datastructuren. In C Om de uitvoering van een 1-bit kwantumpoort nog te versnellen kunnen we het algoritme in C implementeren. Dit is een triviale omzetting van het Matlab-algoritme naar C99/C++, waarbij Complex staat voor respectievelijk double complex en std::complex<double>. Algoritme 7.3: C apply /** * G the 2x2 quantum gate * x the quantum state vector with dimension 2ˆn * m number of basisstates in x, m = 2ˆn * sd projected distance for k in x * y resulting quantum state (can be the same as x) */ void apply(Complex * G, Complex * x, size_t m, size_t sd, Complex * y) { register size_t i, j; size_t dd = sd << 1;
// dd = 2*sd;
for(i = 0; i < m; i += dd) { for(j = i; j < i+sd; j++) { Complex a = x[j]; Complex b = x[j+sd]; y[j] = G[0] * a + G[2] * b; y[j+sd] = G[1] * a + G[3] * b; } } }
Om gebruik te kunnen maken van de taalondersteuning voor complexe getallen moeten we in Matlab de toestandsvector voorstellen als een vector met lengte 2·2 n , met afwisselend de re¨ele en imaginaire componenten van de co¨effici¨enten. Dit maakt het bewerken van de toestandsvector in Matlab zelf wel iets lastiger. Ook de matrixvoorstellingen voor de kwantumpoorten moeten hiervoor aangepast worden:
<(α) =(α) α β → V = γ δ <(γ) =(γ)
91
<(β) =(β) . <(δ) =(δ)
(7.9)
Deze afwisseling van re¨eel en imaginair deel heeft natuurlijk ook invloed op de snelheid waarmee een bepaalde processor de matrixvectorvermenigvuldigingen kan uitvoeren. In het zuiver Matlab-geval worden er vier blokken van getallen in de processorcache geladen en wordt er voor elk paar (complexe) vermenigvuldigingen en de daaropvolgende optelling uit elk blok ´e´en element gebruikt. In de C/C++-oplossing hebben we maar twee blokken en komen er telkens twee opeenvolgende elementen uit ´e´en blok. Dit onderscheid zal per architectuur uiteindelijk zijn weerslag hebben in de uitvoeringssnelheid. Indien we bijvoorbeeld een berekening moeten doen op de elementen van een vector, dan is een stride van 1 element zelden optimaal. De aanpak van Matlab lijkt in dit opzicht voordeliger, al moeten we mee in overweging nemen dat er redelijk wat rekenwerk is per iteratie. Een probleem met de zuivere Matlab-versie is dat het aanpassen van de elementen van x niet ter plaatse kan gebeuren, doordat Matlab vastlegt dat de parameters van een methode niet gewijzigd kunnen worden. Hierdoor heeft de zuivere Matlab-versie twee keer zoveel geheugen nodig. Het algoritme in C kan wel ter plaatse werken door de x en y parameters naar dezelfde datastructuur te laten wijzen. In de mex-file kan deze aanpassing geforceerd worden door de als const doorgegeven argumenten expliciet te casten. Dit geeft echter onverwachte resultaten in Matlab doordat er gebruik gemaakt wordt van een lazy copy mechanisme bij toekenningen. De gebruiker van de functie moet op de hoogte zijn van deze speciale situatie en weten dat na het uitvoeren van y = apply(G, k, x); x en y beiden naar dezelfde datastructuur wijzen. Het is daarom beter om apply(G, k, x);
te schrijven – en te weten dat x impliciet is aangepast – om alle verwarring te vermijden. De bovenvermelde C-code rekent steeds met complexe getallen. Wanneer de co¨effici¨enten allemaal re¨eel zijn, is dit natuurlijk overbodig werk. We kunnen de routine dan ook expliciet herschrijven voor alle mogelijke situaties die zich kunnen voordoen:
a) b) c) d)
y R C C C
← ← ← ← ←
G R R C C
x R C R C
Dit kan redelijk wat rekenwerk uitsparen voor kwantumalgoritmen waarin geen complexe co¨effici¨enten tevoorschijn komen, bijvoorbeeld het zoekalgoritme van Grover. In deze implementatie maken we opnieuw gebruik van de voorstelling voor complexe vectoren van Matlab (re¨eel en imaginair deel gescheiden). Een laatste eigenschap die we kunnen gebruiken om de berekeningen te versnellen, is de structuur van de unitaire matrix V van de kwantumpoort. Op hhttp://gams.nist.govi zijn er redelijk wat routines te vinden voor complexe rotaties. Hiervoor is het wel noodzakelijk dat de matrices van de kwantumpoorten gemarkeerd worden, zodat een bepaalde optimalisatie kan uitgevoerd worden. Deze optimalisatie heb ik niet uitgetest.
92
Volgende resultaten werden experimenteel vastgesteld voor k = 4 en n = 16 en n = 20, met t1 de tijd voor Algoritme 7.1, t2 de tijd voor Algoritme 7.2 en t3 via een mex-functie voor Algoritme 7.3 (tijden in seconden): n 16 20
t1 14.8577 270.1300
t2 1.1558 46.0834
t3 0.0510 0.8067
Het verschil tussen ´e´en C-functie met allemaal complexe co¨effici¨enten of een opdeling in 4 aparte routines maakt zoals verwacht nog een heel verschil. Voor een n = 20 bit register met k = 4 duurt het uitvoeren van een zuivere re¨ele versie 0.1421 seconden, bij een complexe invoertoestand, met re¨ele matrix, wordt dit 0.5052 seconden. Alle tijdsmetingen werden gedaan op snoopy (SunOS snoopy 5.8 Generic 108528-13 sun4u sparc) met Matlab 6. Het C-algoritme werd gecompileerd met het commando CC -c -xO4 apply.c
met de Sun Workbench C++-compiler en in een bibliotheek libqc.a gearchiveerd. In Matlab werd er gecompileerd met mex -O -inline -L. -lqc apply.c
In Haskell De Haskell-routines kunnen er misschien iets ingewikkelder uitzien dan de Matlab en C/C++ versies, maar dat ligt dan waarschijnlijk aan de vertrouwdheid met imperatieve talen en mijn minimale ervaring met functionele talen. De datastructuur die we in de Haskell-versie gebruiken is een letterlijke vertaling van hoe we zelf algebra¨ısche toestanden noteren. Het toepassen van een 1-bit poort V kunnen we als volgt uitdrukken: V0 |x0 i → |V0 x0 i ( |xi ⊗ (Vk |yi) voor k ∈ Bx Vk (|xi ⊗ |yi) → (Vk |xi) ⊗ |yi voor k ∈ By Vk (α |xi + β |yi) → α Vk |xi + β Vk |yi Dit kunnen we ongeveer letterlijk vertalen naar Haskell: Algoritme 7.4: Haskell apply apply :: (Qubit -> Qubit) -> Int -> Register -> Register apply u 0 (Single q) = Single $ u q apply u k (Product a b) | k < nb = Product a (apply u k b) | otherwise = Product (apply u k’ a) b where nb = registerSize b k’ = k - nb apply u k (Sum (sa,a) (sb,b)) = Sum (sa, a’) (sb, b’) where a’ = apply u k a b’ = apply u k b
93
(7.10) (7.11) (7.12)
In de Haskell-code is duidelijk te zien dat een superpositie, Sum (sa,a) (sb,b), aanleiding geeft tot het meermaals toepassen van kwantumpoort u :: (Qubit -> Qubit). In het geval van een tensorproduct Product a b, moeten we u gewoon op de juiste term toepassen. Uiteindelijk komen we steeds uit op een blad van de datastructuur met ´e´en enkele kwantumbit, Single q, en kunnen we u rechtstreeks toepassen.
7.4
Toepassen van conditionele 1-bit kwantumpoorten
In Matlab Voor het toepassen van een conditionele 1-bit kwantumpoort kunnen we op bijna identieke wijze te werk gaan als voor een gewone 1-bit kwantumpoort. We moeten alleen telkens testen of de controlebit c wel degelijk gezet is. We doen dit via een bitmask en kunnen op deze manier met hetzelfde algoritme eender welke ∧ m (V ) poort toepassen. Voor elke controlebit die we toevoegen, halveert het aantal matrixvectorproducten. Algoritme 7.5: Matlab c apply function [x] = c_apply(G, c, k, x) dim = length(x); % the number of basis states d = pow2(k); % projected distance for k in x mask = bitshift(1, c); % controlbitmask for i = 0:2*d:dim-1 for j = i:i+d-1 % update j and j+d if bitand(j, mask) % if control bit set p = G * [x(j+1); x(j+d+1)]; % apply gate x(j+1) = p(1); x(j+d+1) = p(2);% update x end; end; end;
We moeten de bitmask maar op ´e´en van de twee posities, x j en xj+d , testen: de twee co¨effici¨enten die we veranderen verschillen namelijk maar ´e´en bit van elkaar en dat is bit k. Alle andere bits zijn gelijk. Een preconditie die we hierdoor moeten stellen is dat de controlebit c en de toepassingsbit k verschillend zijn, maar het heeft sowieso geen zin om c = k te nemen. Misschien is het mogelijk om de if-operatie in de binnenste lus te verwijderen. Voor het toepassen van een niet-conditionele 1-bit kwantumpoort kunnen we in Figuur 7.1 zien dat we in feite door de ring stappen en telkenmale stoppen op een plaats waar bit k nul is. Voor een conditionele poort moeten we dezelfde ring doorlopen waarbij we alleen maar mogen stoppen wanneer bit c ´e´en is. We zouden de if-operatie uit de lus kunnen verwijderen als we een mogelijkheid vinden om enkel op die punten te stoppen waar aan beide voorwaarden voldaan is.
94
In C De C-versie is weerom een letterlijke vertaling van het Matlab-algoritme. Algoritme 7.6: C c apply /** * G the 2x2 quantum gate * x the quantum state vector with dimension 2ˆn * m number of basisstates in x, m = 2ˆn * sd projected distance for k in x * mask the bitmask for where to apply the gate * y resulting quantum state (can be the same as x) */ void c_apply(Complex * G, Complex * x, size_t m, size_t sd, size_t mask, Complex * y) { register size_t i, j; size_t dd = sd << 1;
// dd = 2*sd;
for(i = 0; i < m; i += dd) { for(j = i; j < i+sd; j++) { if(j & mask) { Complex a = x[j]; Complex b = x[j+sd]; y[j] = G[0] * a + G[2] * b; y[j+sd] = G[1] * a + G[3] * b; } } } }
Volgende resultaten werden experimenteel vastgesteld voor k = 4, c = 2 en n = 16 en n = 20, met t1 de tijd voor Algoritme 7.5 en t2 via een mex-functie voor Algoritme 7.6 (tijden in seconden): n 16 20
t1 9.2078 147.7769
t2 0.0306 0.4614
In Haskell Het Haskell-algoritme is ditmaal een heel stuk langer. De algemene formule voor het toepassen van een ∧1 (V(1) )-poort hebben we afgeleid in §5.5: |ψi 7→ |V 7→
c k ψi (0) |Pc ψi +
95
|(Vk Pc(1) ) ψi
(7.13)
Het algemene geval genereert een superpositie met co¨effici¨enten die worden berekend voor de controlebit c over de hele toestand |ψi. In de Haskell-code maken we onderscheid tussen twee gevallen: 1. toepassing op een superpositie Sum (sa,a) (sb,b): we passen de conditionele poort op elke tak toe; 2. toepassing op een producttoestand Product a b: hier trachten we om de toestand zo gefactoriseerd mogelijk te houden • de controlebit c en de toepassingsbit k zitten beiden in dezelfde term: pas de conditionele poort toe op die term; • indien c en k elk in een andere term zitten, moeten we de controlebit opmeten over de hele tensortoestand, afhankelijk van de gemeten waarde krijgen we een superpositie of een triviale toepassing voor |ci = |0i of |ci = |1i. De berekening van de co¨effici¨enten van bit c wordt hierdoor zo laat mogelijk uitgevoerd. De twee functies apply en c_apply lijken de optimale kandidaten om optimalisaties toe te passen: hier worden superposities bij aangemaakt. We herinneren ons uit §2.1.3 en §6.2.2 dat het belangrijk is om superposities die niet verstrengeld zijn in gefactoriseerde vorm te houden. Maar we hebben ook al opgemerkt dat er momenteel geen echt bruikbare methoden zijn om zo een meerledige superpositie uit elkaar te trekken tot een tensorproduct. Op het einde van §6.2.5 hebben we een opmerking gemaakt over niet naast elkaar liggende bits die verstrengeld zijn. Doordat de datastructuur de volgorde van de bits aangeeft, kunnen we zo een toestand niet effici¨ent voorstellen in de voorgestelde Haskell-implementatie. Erger nog, doordat de volgorde van de bits vastligt, kunnen we onmogelijk verstrengelingen Γ en scheidbare superposities Π – moesten we ze kunnen detecteren – op een andere manier behandelen. Met een datastructuur waarbij de bits zich op willekeurige plaatsen kunnen bevinden, zouden we de implementatie mogelijk een pak effici¨enter kunnen maken. We bekomen dan zoiets als beschreven in §6.2.6. Het punt waarop we moeten ingrijpen is duidelijk de toepassing van c_apply’ op een producttoestand. Buiten de ingreep in de datastructuur zijn er nog enkele andere problemen die hiervoor opgelost moeten worden: • We moeten die toestanden herkennen die we op een effici¨entere manier kunnen voorstellen. Dit is momenteel nog een wiskundig probleem dat (waarschijnlijk) niet opgelost zal raken voor algemene toestanden, maar indien we dit in een beperkt aantal gevallen kunnen, levert dit een grote winst op. • En we zullen op regelmatige tijdstippen in de toestandsmanipulatie de gehele toestand, of deelstructuren hiervan, moeten bekijken en eventueel vereenvoudigen door het toepassen van een simplify-functie. De exponenti¨ele versnelling van een kwantumalgoritme komt juist van het verstrengeld zijn van alle toestanden. Dit wil zeggen dat we steeds het maximale geheugengebruik moeten voorzien. Wat we trachten te verwezelijken is om superposities zo laat mogelijk door te voeren in de gegevensstructuur en zo snel mogelijk weer af te breken. Voor het afbreken hebben we nood aan een simplify-functie die we op strategische plaatsen moeten oproepen. 96
Algoritme 7.7: Haskell c apply
97
c_apply :: (Qubit -> Qubit) -> Int -> Int -> Register -> Register c_apply u c k (Single q) = error "Can’t apply a controlled gate to a single qubit" c_apply u c k (Sum (sa,a) (sb,b)) = Sum (sa, a’) (sb, b’) where a’ = c_apply u c k a b’ = c_apply u c k b c_apply u c k r@(Product a b) | (k < nb) && (c < nb) = Product a (c_apply u c k b) | (k >= nb) && (c >= nb) = Product (c_apply u c’ k’ a) b | otherwise = c_apply’ u cb k r where nb = registerSize b k’ = k - nb c’ = c - nb c_apply’ :: (Qubit -> Qubit) -> Qubit -> Int -> Register -> Register c_apply’ u (Ket Zero) k r = r c_apply’ u (Ket One ) k r = apply u k r c_apply’ u cb k r@(Product a b) | k < nb = Sum (alpha, a0 <*> b ) (beta , a1 <*> b’) | k >= nb = Sum (alpha, a’ <*> b1) (beta , a <*> b0) cb = qubitAt c r alpha = (Bra Zero) <> cb beta = (Bra One ) <> cb a’ = apply u k’ a a0 = change c’ (Ket Zero) a a1 = change c’ (Ket One) a b’ = apply u k b b0 = change c (Ket Zero) b b1 = change c (Ket One) b
Notaties: • De functie c_apply’ bekijkt een producttoestand verder en onderscheidt de triviale gevallen wanneer |ci = |0i of |ci = |1i. • De functie qubitAt :: Int -> Register -> Qubit geeft een uitdrukking van de vorm α |0i + β |1i voor een bepaalde bit gemeten over heel de toestand. We komen deze functie verder nog tegen. • De functie change :: Int -> Qubit -> Register -> Register verandert een bit naar de opgegeven vorm in een register. • a <*> b is een verkorte notatie voor Product a b. • x <> y wordt gebruikt om het inwendig product tussen x en y aan te geven.
7.5
Berekenen van kansen
Het berekenen van de kans die we hebben om een bepaalde basistoestand te meten of de kans om een 1 of een 0 te meten voor een bepaalde bit is een belangrijke routine voor een simulator. In de Haskell-functie c_apply hebben we er al rechtstreeks gebruik van gemaakt om te weten te komen met wat voor toestand bit c overeenkwam (bekeken over de hele toestand). We zullen niet zoeken naar optimalisaties voor deze algoritmen in Matlab omdat ze relatief weinig gebruikt worden, namelijk op het einde van een kwantumalgoritme of op verzoek van een gebruiker. In Matlab Om de kans te berekenen voor een bepaalde basistoestand k = 0 . . . 2 n hebben we in Matlab geen extra methode nodig: dit is simpelweg de absolute waarde in het kwadraat van de overeenkomstige co¨effici¨ent uit de toestandsvector. p = abs(x(k))ˆ2
We hebben wel een routine nodig die de kans p 0 aangeeft om voor een bepaalde bit k, 0 te meten. De kans om voor diezelfde bit k een 1 te meten is uiteraard p 1 = 1 − p0 . Om de kans op een 0 te weten te komen moeten we de basistoestanden doorlopen die een 0 hebben in binaire vorm voor bit k en al deze kansen optellen. Algoritme 7.8: Matlab probability function p = probability_0(x, k) dim = length(x); d = pow2(k);
% the number of basis states % projected distance for k in x
p = 0; for i = 0:2*d:dim-1 p = p + sum(abs(x(i+1:i+d)).ˆ2); end;
In Haskell In Haskell maken we een routine die een globale toestand aangeeft van een kwantumbit op een bepaalde positie. Deze routine hebben we reeds gebruikt in de functie c_apply. We doorlopen de datastructuur en stellen de co¨effici¨enten samen. Algoritme 7.9: Haskell qubitAt qubitAt :: Int -> Register -> Qubit qubitAt 0 (Single q) = q qubitAt i (Product a b) | i < nb = qubitAt i b | otherwise = qubitAt i’ a where nb = registerSize b i’ = i - nb qubitAt i (Sum (sa,a) (sb,b)) = sa |> (qubitAt i a) +> sb |> (qubitAt i b)
98
De operatoren |> en +> zijn respectievelijk de vermenigvuldiging van een kwantumbit met een scalar en het optellen van twee ketvectoren. Voor het bereken van de kans van een volledige basistoestand kunnen we qubitAt toepassen voor elke bit en de kansen vermenigvuldigen.
7.6
Metingen
Bij een meting moeten we dezelfde procedure doorlopen als bij het berekenen van de kans met als extra stap het projecteren van de bits op een toevallig gekozen mogelijkheid. We maken hiervoor gebruik van een willekeurige getallengenerator. Deze beperkt in feite de mogelijkheden van een simulator, omdat het met een echte kwantumcomputer mogelijk is om perfecte willekeurige getallen te genereren. We zouden een kwantumbit in een gelijke superpositie van 0 en 1 kunnen zetten, |ψi =
√1 2
|0i +
√1 2
|1i ,
(7.14)
bijvoorbeeld door het toepassen van de Hadamard-poort op een afgekoelde toestand |0i. De observatie van deze kwantumbit geeft ons een perfect willekeurige bit. Als we dit echter met een klassieke computer simuleren, zijn we afhankelijk van de gebruikte pseudo-generator en zien we dus niet wat er in werkelijkheid gebeurt. In Matlab In Matlab implementeren we letterlijk formule (2.15), |ψ 0 i =
Pk |ψi
(hψ|Pk |ψi)1/2
,
aan de hand van de net gedefinieerde probability_0-functie. Algoritme 7.10: Matlab measure function x = measure(x, k) dim = length(x); n = log2(dim);
% the number of basis states % number of bits in the register
if nargin == 1, k = [0:n-1]; end; for i = 1:length(k) prob_0 = probability_0(x, k(i)); if prob_0 > rand % observed a ’0’ x = apply([1/sqrt(prob_0) 0; 0 0], k(i), x); else % observed a ’1’ x = apply([0 0; 0 1/sqrt(1-prob_0)], k(i), x); end; end;
De parameter k is een vector met de bits die men wil observeren. 99
(7.15)
In Haskell In Haskell komt er een mooie taalabstractie naar boven. Een meting van een kwantumtoestand houdt een probabilistische projectie in van deze toestand en dat is geen puur functionele operatie. We kunnen in de Haskell-simulator dus twee types van functies onderscheiden: • de puur functionele bewerkingen, zonder neveneffecten, die we gebruiken voor het toepassen van kwantumpoorten; • en de probabilistische meting, die niet als een puur functionele operatie kan geschreven worden. Deze laatste zullen we moeten schrijven als een IO-functie, gebruik makend van IO-monads. Hoe mooi de Haskell-abstractie ook is, door tijdgebrek heb ik niet de mogelijkheid gehad om dit op een degelijke manier te implementeren. Ik heb de Haskell-simulator voornamelijk gebruikt om verstrengeling en superpositie aan het werk te zien, hiervoor is het opmeten van een register niet nodig.
7.7
Optimalisaties van de simulatoren
Optimaliseren van de Matlab-simulator Bij het optimaliseren van de Matlab-simulator heb ik mij voornamelijk geconcentreerd op het herschikken van de toestandsvector. Een eerste punt dat opviel bij het implementeren van de apply en c_apply functies, was de grote afstand d = 2 k die mogelijk was tussen twee elementen die gecombineerd moesten worden. De maximale afstand is 2 n−1 , wat bijvoorbeeld voor een 25 bit register 256 MB bedraagt. Men kan natuurlijk de componenten van de toestandsvector herschikken en zo de afstand minimaal maken voor elementen die met elkaar gecombineerd moeten worden. Indien we bijvoorbeeld k = n − 1 nemen (d is dan maximaal) dan moeten we a met x combineren en zo verder tot w met z. a b .. 2n−1 . w (7.16) x .. . z
We zouden hieruit kunnen besluiten dat voor deze k we best a en x zo dicht mogelijk bijeen brengen en a en z zover mogelijk uiteen. Dit geeft de volgende 2 × 2 n−1 matrix (kolomgeori¨enteerd): a b ··· w . (7.17) x y ··· z 100
1
350
0.9 300 0.8 250
0.7
0.6 200 0.5 150 0.4
0.3
100
0.2 50 0.1
0
0
2
4
6
8
10
12
14
16
18
20
(a) 20 bit register
0
0
5
10
15
20
25
(b) 25 bit register
Figuur 7.2: Uitvoertijd van apply voor verschillende k-waarden Deze herschikking levert ons echter niets op, want de maximale afstand wordt nu gewoon bij een andere k gehaald. Bij k = n − 2 moeten we het eerste element van de bovenste rij combineren met het 2n−2 -de element van die rij, maar doordat de datastructuur kolomgeori¨enteerd is, blijft de afstand 2n−1 . Dit is dus identiek aan het 2n × 1 geval. Het volgende idee dat hierop verdergaat is het gedeeltelijk kopi¨eren van vectorelementen naar voordeligere plaatsen. Om de vector in de optimale volgorde te krijgen moeten er telkens S = 2n−2 elementen verwisseld worden. Dat is duidelijk niet haalbaar. Een poging om een schema te verzinnen dat dit op bepaalde kritische punten doet, en zo suboptimaal zou zijn in de overige gevallen, is op niets uitgedraaid. We kunnen echter opmerken dat bij kleine k de nodige elementen ongeveer sequentieel achter elkaar zitten. Hierdoor zal de processorcache de twee opeenvolgende elementen automatisch bevatten. Bij grote k zal de geblokte structuur er voor zorgen dat er twee blokken in de cache geladen worden, in de ene zitten de a’s, in de andere de x’n en we zullen elke blok op zich sequentieel overlopen. De uitvoersnelheid van apply en c_apply zijn dus voornamelijk afhankelijk van de geheugentoegangstijden. Dit is duidelijk ge¨ıllustreerd in Figuur 7.2. De enige mogelijke optimalisatie is dan ook lokalisatie van de data door het herschikken van de kwantumpoorten in het circuit. Indien we achtereenvolgens twee kwantumpoorten kunnen toepassen die ongeveer dezelfde twee co¨effici¨enten moeten aanpassen, dan kunnen we die aanpassingen combineren in ´e´en iteratie. Het probleem dat hierbij dan weer opduikt is dat dit voor de meeste kwantumcircuits zelden of nooit gebeurt. Ook is de bedoeling van een simulator om te laten zien wat er op elk moment in het circuit gebeurt, dat is natuurlijk onmogelijk als het circuit aangepast werd voor de simulatie. Optimaliseren van de Haskell-simulator Over de optimalisatie van de Haskell-simulator hebben we het al gedeeltelijk gehad in §7.4. De simulatiesnelheid is sterk afhankelijk van hoe de apply en c_apply functies de toestands-
101
voorstelling transformeren. Kleine details in de implementatie kunnen voor een groot verschil zorgen tijdens een simulatie. Zo valt er bijvoorbeeld op te merken dat een toestand Product a (Product b (Product c (Product d e)))
waarschijnlijk anders zal behandeld worden dan de gelijkwaardige toestand Product (Product (Product (Product a b) c) d) e
of nog algebra¨ısch: a ⊗ b ⊗ c ⊗ d ⊗ e.
(7.18)
In dit opzicht zou het misschien handiger zijn om de structuur bij een tensorproduct en een som rechtstreeks voor te stellen als een lijst van toestanden: data Register = Single Qubit | Product [Register] | Sum [(Scalar, Register)]
op die manier zijn manipulaties op de toestand automatisch commutatief. In Haskell kunnen we ook geen aanpassingen ter plaatse doen. Een term die wordt aangepast door het toepassen van een kwantumpoort, levert een nieuwe term op: functionele talen kennen geen toekenningen. Of dit inderdaad een negatieve eigenschap zou zijn, is moeilijk in te schatten. Dit hangt voor een groot deel af van de geheugenmanager die gebruikt wordt. In [44] wordt het simplistische argument gegeven dat ter plaatse aanpassen niet veel kan uitmaken omdat de toestand, na toepassing van een kwantumpoort, te hard zou verschillen van de oude toestand. Waarschijnlijk ging de auteur iets te hard op in zijn ‘killer application’ voor Haskell. In Bijlage C is een Matlab- en Haskell-implementatie terug te vinden voor de veel gebruikte kwantum-Fourier-transformatie als voorbeeld van de simulatie van een kwantumcircuit.
102
Besluit De reeds bestaande simulatoren schenken geen aandacht aan de uitwerking van de simulatiealgoritmen. Er wordt veel aandacht besteed aan het ontwikkelen van een mooie grafische interface waarmee men dan beperkte kwantumcircuits kan simuleren. QCL [35] is daarentegen wel een goede experimenteeromgeving, maar is ontwikkeld rond een volledig nieuwe taal en dus onvolledig. De keuze voor Matlab als simulatieomgeving voor de algoritmen en de concentratie op de algoritmen zelf, biedt daarom duidelijke voordelen in deze tekst. De Haskell-algoritmen die parallel werden besproken bieden een heel andere kijk op het manipuleren van de kwantumtoestand van een machine. Hier zijn echter nog vele experimenten nodig om met behulp van patroonherkenning en een op kritische punten toegevoegde simplify-functie de benodigde superposities te minimaliseren. Het is spijtig dat de originele code, geschreven door een professional, van [44] niet meer terug te vinden is. Wellicht werden daar betere functionele technieken in gebruikt bij het toepassen van kwantumpoorten, al moeten we er bij vermelden dat deze volgens het ontwerpdocument ‘nog verre van optimaal’ waren (en gedeeltelijk onmogelijk). Het schrijven van een simulator geeft een zeer goed beeld van wat verstrengeling van kwantumsystemen nu eigenlijk inhoudt. Aan de hand van een simulator kan men verstrengeling beter leren begrijpen en dit maakt een simulator, ondanks de exponenti¨ele complexiteit, een heel stuk minder zinloos. Met behulp van de Haskell-simulator zouden experimenteel veel voorkomende structuren in kwantumtoestanden vastgesteld kunnen worden en kan men dus gericht gaan optimaliseren. Het grootste probleem bij deze thesis was het tijdsbestek waarin de opdracht moest volbracht worden: het kwantumcomputerdomein is zeer uitgebreid en niet zo gemakkelijk om te leren kennen. De twee simulatoren zijn bruikbaar als leermiddel, maar alleen de Matlab-simulator kan reeds gebruikt worden om echte kwantumalgoritmen uit te testen. De simulatoralgoritmen bieden de mogelijkheid om eender welk kwantumcircuit te simuleren. In combinatie met Matlab hebben we een heuse kwantumcomputer volgens het QRAM-model. Bij de Haskell-versie ontbreekt de observatiefunctie, maar de simulator is ten zeerste geschikt voor het bestuderen van verstrengeling. Het belang van een simulator is voornamelijk nieuwe onderzoekers vertrouwd maken met het domein van kwantumalgoritmen, wat in mijn geval zeker gelukt is.
103
Bijlage A
Tensorproducten A.1
Definitie van tensorproduct-vectorruimten
De definitie van tensorproducten komt (letterlijk) uit [51]. Het tensorproduct van twee matrices is in Matlab gedefinieerd als kron(A, B). Het (rechtstreeks) tensorproduct of Kronecker-product van twee vectorruimtes V en W , geschreven als V ⊗ W geeft een nieuwe vectorruimte analoog met de vermenigvuldiging van gehele getallen, bijvoorbeeld: Rn ⊗ R m ∼ = Rnm . Het tensorproduct is distributief ten opzichte van de rechtstreekse som: U ⊗ (V ⊕ W ) ∼ = (U ⊗ V ) ⊕ (U ⊗ W ). Voor twee vectoren v ∈ V en w ∈ W , en een scalar α ∈ F (met F een willekeurig veld), in een vectorruimte opgespannen door elementen (v ⊗ w) ∈ (V ⊗ W ) gelden volgende regels: • (v1 + v2 ) ⊗ w = v1 ⊗ w + v2 ⊗ w; • v ⊗ (w1 + w2 ) = v ⊗ w1 + v ⊗ w2 en • α(v ⊗ w) = (αv) ⊗ w = v ⊗ (αw). Als rechtstreeks gevolg hebben we dat 0 ⊗ w = v ⊗ 0 = 0. Een basis {vi } voor V en een basis {wj } voor W geven een basis {vi ⊗ wj } voor V ⊗ W voor alle mogelijke combinaties (i, j). Een willekeurig element u ∈ V ⊗ W kan geschreven worden als X u= αi,j vi ⊗ wj , met scalars αi,j ∈ F .
Als V n-dimensionaal is en W is m-dimensionaal dan is V ⊗ W nm-dimensionaal. 104
A.2
Voorbeelden
Voor kwantumtheorie is het veld F van scalars gelijk aan C. De vectorruimten V en W zijn de vectorruimten waarin de ket-vectoren van de kwantumdeelsystemen leven en hebben dus steeds een aantal elementen dat een macht van 2 is.
A.2.1
Vectortensorproduct
Indien we twee toestandsvectoren |ai en |bi hebben, a b |ai = 0 ∈ C2 en |bi = 0 ∈ C2 , a1 b1
dan is hun tensorproduct
b a |ci = |ai ⊗ |bi = 0 ⊗ 0 b1 a1 b0 a0 · b1 = b a1 · 0 b1 a0 b0 c00 a0 b1 c01 4 = a1 b0 = c10 ∈ C . a1 b1 c11
De co¨effici¨enten van |ci staan in lexicografische volgorde: c 00 , c01 , c10 , c11 . Hierdoor zijn de toestandsvectoren van een kwantumregister makkelijk interpreteerbaar.
A.2.2
Matrixtensorproduct
Bij matrices gaan we in feite op dezelfde manier te werk als bij vectoren. We krijgen hier een soort van bloksgewijze vermenigvuldiging. Stel we hebben twee matrices A en B, b00 b01 a00 a01 2×2 ∈ C2×2 , ∈C en B = A= b10 b11 a10 a11 dan is hun tensorproduct
C =A⊗B b a00 a01 ⊗ 00 = b10 a10 a11 a00 · B a01 · B = a10 · B a11 · B a00 b00 a00 b01 a00 b10 a00 b11 = a10 b00 a10 b01 a10 b10 a10 b11
b01 b11
a01 b00 a01 b10 a11 b00 a11 b10
105
a01 b01 a01 b11 ∈ C4×4 . a11 b01 a11 b11
Bijlage B
Matrix exponentiatie De exponenti¨ele afbeelding ex voor een matrix A is gedefinieerd als [51]: exp(A) ≡ eA ∞ X An = n! n=0 = I +A+
AA AAA + + ··· 2! 3!
en convergeert voor elke vierkante matrix. Voor een diagonale matrix
A =
a1,1 0 · · · 0 a2,2 .. .. . . 0
0
volstaat het om elementsgewijs eai,i te nemen: a 0 e 1,1 a2,2 0 e eA = . .. 0
0
···
··· ..
. ···
0 0 .. . an,n
,
0 0 .. . ean,n
.
Als de matrix A diagonaliseerbaar is, A = XΛX −1 , dan is het eenvoudiger om A eerst te diagonaliseren en dan de exponent te nemen eA = XeΛ X −1 .
106
Bijlage C
Voorbeeldimplementatie van een kwantumroutine: de QFT De kwantum-Fourier-transformatie (QFT) is een van de belangrijkste kwantumsubroutines en wordt in bijna alle huidige kwantumalgoritmen gebruikt om voordeel te halen op de klassieke algoritmen. De QFT is een bijna rechtstreekse vertaling van het klassieke Cooley-Tukey-FFTalgoritme en heeft een tijdscomplexiteit van O(k 2 ) of, wanneer men gebruik maakt van een benadering, de AQFT, zelfs O(k log 2 k), met k het aantal ingangsbits. De discrete N -punts Fouriertransformatie (DFT), voor een rij x k van N punten, is gedefinieerd als [39, 47, 51]: N −1 X DF T : Xk = xn e2πikn/N k = 0 . . . N − 1 (C.1) n=0
Er zijn verschillende varianten te vinden voor de DFT en zijn inverse, de IDFT, waarbij men naar willekeur bij ´e´en van de twee transformaties een normalisatiefactor 1/N schrijft. De QFT is gedefinieerd als [38]: n
QF T :
2 −1 1 X 2πixy/2n e |yi . |xi 7→ √ 2n y=0
(C.2)
De normalisatiefactor wordt bij de QFT en de IQFT bij beide transformaties geschreven als 2−n/2 , hierdoor blijft de getransformeerde vector zijn lengte behouden. Het kwantumcircuit voor een QFT over 4 bit is te zien in Figuur C.1. We passen voor elke bit een Hadamard-poort H toe, gevolgd door een reeks conditionele fasedraaiingen Rd , afhankelijk van de minder beduidende bits. Deze zijn gedefinieerd als: 1 0 (C.3) Rd = d . 0 eiπ/2 Na het toepassen van de kwantumpoorten in het kwantumcircuit zal de uitvoer van de QFT in omgekeerde volgorde staan, vandaar de swap-poorten op het einde van het circuit. Deze bewerking voeren we normaalgezien niet echt uit. Dit is een taak voor de klassieke machine die de kwantumcomputer bestuurt. 107
|x3 i
H
R1
R2
|x2 i
R3
|y3 i
6
H
R1
R2
|x1 i
6
H
?
R1
|x0 i
H
?
|y2 i |y1 i |y0 i
Figuur C.1: Een 4-bit kwantum-Fourier-transformatie De QFT-subroutine implementeren in de de simulatoren is relatief eenvoudig. Voor Matlab krijgen we: Algoritme C.1: Matlab QFT-implementatie function x = qft(x, k) H = 1/sqrt(2) * [1 1; 0 0; -1 1; 0 0]; % H = 1/sqrt(2) * [1 1; -1 1];
% C/C++ version % Matlab version
dim = length(x) / 2;% the number of basis states (C/C++ version) % dim = length(x); % the number of basis states (Matlab version) n = log2(dim); % number of bits in the register if nargin == 1, k = [0:n-1]; end; m = length(k); % the number of bits to transform for i = m:-1:1 apply(H, k(i), x); for j = i-1:-1:1 c_apply(R(i-j), k(j), k(i), x); end; end;
In Haskell wordt dit [44] (voor een volledig register): Algoritme C.2: Haskell QFT-implementatie qft :: Register -> Register qft register = (foldl1 (.) [u k | k <- [0..n]]) register where u 0 = apply u_hadamard 0 u k = (foldl1 (.) [c j k | j <- [0..(k-1)]]) . (apply u_hadamard k) c j k = c_apply (u_phase (pi/(2.0ˆ(k-j)))) j k n = registerSize register - 1
De optimalisatie van de QFT waarover reeds sprake was in het verloop van de tekst, bestaat er in om Rd poorten met een kleine hoek, d.i. een grote d, niet uit te voeren. Men noemt dit de benaderende kwantum-Fourier-transformatie, AQFT. Men kiest dan een d max over welke afstand men Rd simpelweg niet uitvoert. Barenco et al toonden aan dat de AQFT zelfs beter 108
werkt dan de volledige QFT in het geval we rekening houden met decoherentie. Op een echte kwantumcomputer zal men hierdoor waarschijnlijk voor de goedkopere AQFT kiezen in plaats van de QFT.
109
Lijst van figuren 1.1
Meerdere werelden interpretatie van Everett . . . . . . . . . . . . . . . . . . .
3
1.2
De toestand van een kwantumbit op een Bloch-sfeer . . . . . . . . . . . . . .
6
1.3
De kat van Schr¨odinger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.1
Configuraties van een toestandsvector (pure toestanden) . . . . . . . . . . . .
22
2.2
Superpositie en gemengde toestanden bij de kat van Schr¨odinger (naar [45]) .
27
2.3
Verdeling van verstrengeling door LOCC (naar [37]) . . . . . . . . . . . . . .
31
2.4
Verstrengeling van gemengde toestanden . . . . . . . . . . . . . . . . . . . . .
35
3.1
De kwantum-Turing-machine (QTM) van Deutsch . . . . . . . . . . . . . . .
39
3.2
Een circuit met xor-poorten (cnot) . . . . . . . . . . . . . . . . . . . . . . . .
40
5.1
Een voorbeeldkwantumcircuit . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5.2
Kwantumcircuitsymbolen voor enkele elementaire kwantumpoorten . . . . . .
59
5.3
Een m-conditionele 1-bit poort G ∈ ∧ m (U ) . . . . . . . . . . . . . . . . . . .
61
5.4
De Deutsch-poort is op zich een universele set . . . . . . . . . . . . . . . . . .
63
5.5
Ontbinding van een ∧2 (U )-poort (Barenco et al.) . . . . . . . . . . . . . . . .
63
5.6
Ontbinding van een ∧1 (W )-poort . . . . . . . . . . . . . . . . . . . . . . . . .
64
5.7
Ontbinding van een ∧1 (P h(δ))-poort naar een niet-conditionele 1-bit poort .
65
5.8
De ontbinding van ∧2 (Rλ ) volgens DiVincenzo . . . . . . . . . . . . . . . . .
66
5.9
Implementaties voor kwantumbits
. . . . . . . . . . . . . . . . . . . . . . . .
70
5.10 Vereenvoudigd schema van het QRAM-model . . . . . . . . . . . . . . . . . .
70
5.11 Architectuurontwerp voor Q-taal [7] . . . . . . . . . . . . . . . . . . . . . . .
72
6.1
Gescheiden universums bij niet-verstrengelde deelsystemen . . . . . . . . . . .
79
6.2
Hashtabel voor een 25-bit kwantumregister . . . . . . . . . . . . . . . . . . .
82
110
7.1
De aanpassing gebeurt in blokken van d = 2 k elementen . . . . . . . . . . . .
90
7.2
Uitvoertijd van apply voor verschillende k-waarden . . . . . . . . . . . . . .
101
C.1 Een 4-bit kwantum-Fourier-transformatie . . . . . . . . . . . . . . . . . . . .
108
111
Algoritmen 7.1
Matlab apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
7.2
Matlab apply geoptimaliseerd . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
7.3
C apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
7.4
Haskell apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
7.5
Matlab c apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
7.6
C c apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
7.7
Haskell c apply . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
7.8
Matlab probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
7.9
Haskell qubitAt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
7.10 Matlab measure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
C.1 Matlab QFT-implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
C.2 Haskell QFT-implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . .
108
112
Bibliografie [1] Dorit Aharonov. ‘Quantum computation’. Annual Reviews of Computational Physics, VI, 1998. hhttp://arXiv.org/ps/quant-ph/9812037i [2] Koen Audenaert. ‘Quantum information theory: math and experimental realization – Calculation of the asymptotic relative entropy of entanglement’, Februari 2002. Informele workshop over kwantuminformatietheorie, ESAT-SCD, Katholieke Universiteit Leuven. [3] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman H. Margolus, Peter W. Shor, Tycho Sleator, John A. Smolin en Harald Weinfurter. ‘Elementary gates for quantum computation’. Physical Review A, 52(5):3457–3467, 1995. hhttp://citeseer.nj.nec.com/adriano95elementary.htmli [4] David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni en John Preskill. ‘Efficient networks for quantum factoring’. Februari 1996. hhttp://arXiv.org/ps/quant-ph/9602016i [5] E. Bernstein en U. Vazirani. ‘Quantum complexity theory’. SIAM Journal of Computation, 26(5):1411–1473, 1997. hhttp://citeseer.nj.nec.com/bernstein97quantum.htmli [6] Stefano Betelli. ‘A collection of papers on quantum computing’, December 2001. hhttp://meitner.tn.infn.it/∼bettelli/qcomp/digest/i [7] Stefano Betelli, Tommaso Calarco en Luciano Serafini. ‘Toward an architecture for quantum programming’. Maart 2001. Ontwerp artikel voor ‘The Q language – a C++ extension for programming quantum machines’. hhttp://arXiv.org/ps/quant-ph/0103009i [8] Samuel L. Braunstein. ‘Quantum computation’, 1996(?). hhttp://www.sees.bangor.ac.uk/ ∼ schmuel/i [9] V. Buzek en M. Hillery. ‘Quantum copying: Beyond the no-cloning theorem’. Physical Review A, 54(3):1844–1848, Februari 1996. hhttp://www.fi.muni.cz/usr/buzek/mypapers/96pra1844.pdfi [10] Mirko Cinchetti. Quantum entanglement. Masters thesis, National University of Ireland, Maynooth, November 2000. hhttp://planck.thphys.may.ie/jtwamley/thesis/mcinchetti/thesis/i 113
[11] Michael Clive. ‘The Everett FAQ’, Februari 1995. hhttp://www.hedweb.com/everett/i [12] George Cybenko. ‘Reducing quantum computations to elementary unitary operations’. Computing in science & engineering, (March/April):27–32, 2001. [13] David Deutsch. ‘Quantum theory, the Church-Turing principle and the universal quantum computer’. Proceedings of the Royal Society of London Ser. A, A400:97–117, 1985. hhttp://citeseer.nj.nec.com/deutsch85quantum.htmli [14] David Deutsch. ‘Quantum computational networks’. Proceedings of the Royal Society of London Ser. A, A439:553–558, 1989. X. [15] David Deutsch. ‘Comment on many minds interpretations of quantum mechanics’. British Journal for the Philosophy of Science, 47(2):222–232, Juni 1996. hhttp://www.qubit.org/people/david/Articles/CommentOnLockwood.htmli [16] David Deutsch. ‘An interview with David Deutsch’. Philosophy Now , December 2000. hhttp://www.qubit.org/people/david/Articles/PhilosophyNow.htmli [17] David P. DiVincenzo. ‘Two-bit gates are universal for quantum computation’. Physical Review A, 51(2):1015–1022, 1995. hhttp://citeseer.nj.nec.com/divincenzo95twobit.htmli [18] David P. DiVincenzo. ‘The physical implementation of quantum computation’. Fortschritte der Physik , 84(9–11):771–83, April 2000. hhttp://arXiv.org/ps/quant-ph/0002077i [19] David P. DiVincenzo, Barbara M. Terhal en Ashish V. Thapliyal. ‘Optimal decompositions of barely separable states’. September 1999. hhttp://arXiv.org/ps/quant-ph/9904005i [20] Andrew C. Doherty, Pablo A. Parrilo en Federico M. Spedalieri. ‘Distinguishing separable and entangled states’. December 2001. hhttp://arXiv.org/ps/quant-ph/0112007i [21] Rocco Duvenhage. ‘The nature of information in quantum mechanics’. Maart 2002. hhttp://arXiv.org/ps/quant-ph/0203070i [22] A. Galindo en M. A. Mart´ın-Delgado. ‘Information and computation: classical and quantum aspects’, Juni 2001. Lesnota’s, Departamento de F´ısica T´eorica, Facultad de Ciencias F´ısicas, te verschijnen in Modern Physics. hhttp://arxiv.org/abs/quant-ph/0112105i [23] Lucien Hardy. ‘Notes on measurement and nonlocality’. hhttp://www.qubit.orgi [24] ISO. ‘Programming languages - c’. JTC1/SC22/WG14 N794, C99 ISO standaard draft. hhttp://www.vmunix.com/∼gabor/c/draft.htmli [25] Daniel Jonathan en Martin B. Plenio. ‘Entanglement-assisted local manipulation of pure quantum states’. Februari 2002. hhttp://arXiv.org/pdf/quant-ph/9905071i 114
[26] Richard Jozsa. ‘Quantum factoring, discrete logarithms, and the hidden subgroup problem’. Computing in science & engineering, (March/April):34–43, 2001. [27] Richard Jozsa en Noah Linden. ‘On the role of entanglement in quantum computational speed-up’, 2002. hhttp://arXiv.org/ps/quant-ph/0201143i [28] Jerzy Karczmarczuk. ‘Scientific computation and functional programming’, Januari 1999. [29] Donald E. Knuth. Fundamental algorithms, volume 1 van The art of computer programming. Addison-Wesley, third edition uitgave, 1997. ISBN 0-201-89683-4. [30] Donald E. Knuth. Seminumerical algorithms, volume 2 van The art of computer programming. Addison-Wesley, third edition uitgave, 1997. ISBN 0-201-89684-2. [31] M. Lewenstein, D. Bruß, J.I. Cirac, B. Kraus, M. Ku´s, J. Samsonowicz, A. Sanpera en R. Tarrach. ‘Separability and distillability in composite quantum systems’. Januari 2000. Gepresenteerd op de ‘Quantum Optics’ conferentie, K¨ uhtai, Januari 2000. hhttp://arXiv.org/ps/quant-ph/0006064i [32] Samuel J. Lomonaco. ‘A lecture on Shor’s quantum factoring algorithm’. September 2000. hhttp://arXiv.org/ps/quant-ph/0010034i [33] Zdzis´law Meglicki. ‘Introduction to quantum computing’, Februari 2002. Lesnota’s M743, Indiana University. hhttp://beige.ucs.indiana.edu/B679/M743.htmli ¨ [34] Bernhard Omer. A procedural formalism for quantum computing. Masters thesis, Department of Theoretical Physics, Technical University of Vienna, Juli 1998. hhttp://tph.tuwien.ac.at/∼ oemer/doc/qcldoc/i ¨ [35] Bernhard Omer. Quantum programming in QCL. Masters thesis, Institute of Information Systems, Technical University of Vienna, Januari 2000. hhttp://tph.tuwien.ac.at/∼ oemer/doc/quprog/i [36] Arthur O. Pittenger. An Introduction to Quantum Computing Algorithms, volume 19 van Progress in Computer Science and Applied Logic. Birkh¨auser, Boston, Basel, Berlin, 1999. ISBN 0-8176-4127-0. [37] Martin B. Plenio en Vlatko Vedral. ‘Teleportation, entanglement and thermodynamics in the quantum world’. Contemporary Physics, 39:431–466, Mei 1998. hhttp://arXiv.org/ps/quant-ph/9804075i [38] John Preskill. ‘Quantum information and computation’, September 1998. Lesnota’s physics 229, California Institute of Technology. hhttp://theory.caltech.edu/∼ preskill/ph229i [39] William H. Press, Saul A. Teukolsky, William T. Vetterling en Brian P. Flannery. Numerical recipes in C: the art of scientific computing. Cambridge University Press, 1992. ISBN 0-521-43108-5. hhttp://www.nr.comi 115
[40] J.M. Raimond. ‘Schr¨odinger cat states of the cavity field’, Oktober 1998. hhttp://www.lkb.ens.fr/recherche/qedcav/english/rydberg/nonresonant/Cats.htmli [41] Redhat. ‘Gnu scientific library’. hhttp://sources.redhat.com/gsl/i [42] Peter W. Shor. ‘Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer’. SIAM Journal on Computing, 26(5):1484–1509, 1997. Ook verschenen in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20-22, 1994, IEEE Computer Society Press, paginas 124–134. hhttp://arXiv.org/ps/quant-ph/9508027i [43] Peter W. Shor. ‘Introduction to quantum algorithms’. 2000. hhttp://arXiv.org/ps/quant-ph/0005003i [44] Jan Skibinski. ‘Haskell simulator of a quantum computer’, Mei 2001. Gearchiveerd terug te vinden op hhttp://www.archive.orgi. hhttp://www.numeric-quest.com/haskell/QuantumComputer.htmli [45] Tom Tadfor. ‘Quantum weirdness’, 2001. hhttp://www.telp.com/philosophy/qw.htmi [46] Lieven M. K. Vandersypen, Matthias Steffen, Gergory Breyta, Costantino S. Yannoni, Mark H. Sherwood en Isaac L. Chuang. ‘Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance’. Nature, 414(20/27):883–887, December 2001. hhttp://arXiv.org/ps/quant-ph/i [47] Stefan Vandewalle. Numerieke benadering en geometrische modellering. Acco, Leuven, 1999. ISBN 90-334-4401-1. [48] Frank Verstraete, Jeroen Dehaene en Bart De Moor. ‘On the geometry of entangled states’. Juli 2001. hhttp://arXiv.org/ps/quant-ph/0107155i [49] C. S. Vinod. ‘Quantum computing poised to take a quantum leap’. C-DAC , Januari 2001. hhttp://www.cdacindia.com/html/connect/1q2001/art09.htmi [50] Jullia Wallace. ‘Quantum computer simulators – a review’, Oktober 1999. hhttp://www.dcs.ex.ac.uk/∼jwallacei [51] Eric Weisstein et al. ‘Eric Weisstein’s world of mathematics’, April 2002. Wolfram’s online mathematics resource. hhttp://mathworld.wolfram.com/i [52] Colin P. Williams. ‘Quantum search algorithms in science and engineering’. Computing in science & engineering, (March/April):44–51, 2001. [53] Coling P. Williams en Scott H. Clearwater. Explorations in Quantum Computing. Springer-Verlag, New York, Berlin, Heidelberg, 1998. ISBN 0-387-94768-X. 116
[54] A. Yao. ‘Quantum circuit complexity’. In ‘Proceedings of the 34th Annual Symposium on Foundations of Computer Science’, pagina’s 352–361. Institute of Electrical and Electronic Engineers Computer Society Press, Los Alamitos, CA, 1993. hhttp://citeseer.nj.nec.com/yao93quantum.htmli
117
