Quantum computing. Dirk Nuyens. dept. computerwetenschappen KULeuven

Quantum computing Dirk Nuyens [[email protected]]

dept. computerwetenschappen KULeuven

qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.1

Mijn thesis plannen • Proberen een zo goed mogelijk beeld te vormen van alles

wat te maken heeft met quantum computing.

• Een degelijke simulator bouwen (bijna alle bestaande

simulatoren zijn geschreven door fysici): dit lijkt niet zo moeilijk.

• Trachten om de quantum toestand van de machine zo

optimaal mogelijk bij te houden: de meeste implementaties gebruiken sparse vectoren, sommige gebruiken bomen...

• Indien er keuze is tussen verschillende algoritmen: trachten

het meest optimale te vinden.


– 18/12/2001 – 21:25 – p.2

deel I:

Quantum computing spoedcursus


– 18/12/2001 – 21:25 – p.3

De ingrediënten van QC • Gebruik van een quantum systeem als informatiedrager

⇒ qubit.

• Wat magische eigenschappen van quantum mechanica. • Gebruik van superpositie, entanglement en interferentie als

voordeel op klassieke algoritmen. α |0i + β |1i superpositie

√1 2

|11i + √12 |00i entanglement

−1 |1i + 1 |1i + · · · interferentie

• Een snuifje genialiteit om de correcte toestand uit een

berekende superpositie te halen.


– 18/12/2001 – 21:25 – p.4

Overzichtje Quantum Mechanics Measurement Observation Superposition/Entanglement Quantum Parallelism/Interference Hilbert space Schrodinger eq

Decoherence QECC

Quantum Algorithms

Complexity Theory

(Q)Cryptography Quantum TM Quantum computer

ECC

Probabilistic TM

Coding Compression

Shannon

Turing Machine

Information Theory


– 18/12/2001 – 21:25 – p.5

Superpositie [1] • De quantum toestand van één qubit:

|ψi = α " |0i #+ β |1i α = β

met α,β ∈

en |α|2 +|β|2 ≡1

⇒ algemeen k|ψik2 ≡1

Dit is een punt op een 4 dimensionale hypersfeer in Hilbert ruimte, |ψi ∈ C2 = H = span{|0i , |1i}.

• Door quantum mechanica kan deze 2D golffunctie in

ontelbaar veel configuraties zijn, met |α|2 de kans om ‘0’ te observeren, en |β|2 de kans om ‘1’ te observeren. qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.6

Superpositie [2] • Na observatie zal de qubit ineengestort zijn tot ‘0’ of ‘1’. De

geobserveerde toestand zal consistent zijn met verdere observaties (en manipulaties). De toestand is dus ineengestort tot |ψit1 = |0i of |ψit1 = |1i.

• Indien we het quantum systeem niet observeren, dan kunnen

we berekeningen doen op beide toestanden tegelijk (↔ probabilistische algoritmen, maar in QC volgen we beide paden!).


– 18/12/2001 – 21:25 – p.7

Superpositie [2] • Na observatie zal de qubit ineengestort zijn tot ‘0’ of ‘1’. De

geobserveerde toestand zal consistent zijn met verdere observaties (en manipulaties). De toestand is dus ineengestort tot |ψit1 = |0i of |ψit1 = |1i.

• Indien we het quantum systeem niet observeren, dan kunnen

we berekeningen doen op beide toestanden tegelijk (↔ probabilistische algoritmen, maar in QC volgen we beide paden!).

• Historische nota: Schrödinger’s kat:

1 1 |kati = √ |doodi + √ |levendi 2 2 qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.7

Een quantum register [1] • Een quantum register van n bits: 2

2

|ψi = |kn · · · k1 i ∈ H = C ⊗ · · · ⊗ C = C

2n

Genormaliseerd op een 2 · 2n dimensionale hypersfeer, dus k |ψi k2 ≡ 1. Een 8 bit quantum register is dus een golffunctie in een 28 = 256 dimensionale golfruimte. • We kunnen het register in een superpositie van deze 2n

toestanden zetten en berekeningen uitvoeren op alle toestanden tegelijk voor de prijs van één berekening, m.a.w. een exponentiële versnelling of quantum parallellisme!!


– 18/12/2001 – 21:25 – p.8

Een quantum register [2] • Notatie voor het getal 4 in een 3 bit register:

|ψi = |410 i = |1002 i = |1i ⊗ |0i ⊗ |0i   → 000 0    0  → 001    0  → 010    0  → 011   =    1  → 100    0  → 101      0  → 110 → 111 0 qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.9

Een quantum register [3] • Superpositie in een quantum register:

√

√ |ψi = 1/ 2 |3i + 1/ 2 |7i   0    0     0     → 011 1  1   = √   0  2    0       0  → 111 1 qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.10

Entanglement [1] • Wanneer er meer dan één qubit in het spel is, kan het

systeem verstrengeld of entangled geraken.

• Bijvoorbeeld het entangled register:

|ψit0

√ = 1/2 |000i + 1/ 2 |110i + 1/2 |111i


– 18/12/2001 – 21:25 – p.11

Entanglement [1] • Wanneer er meer dan één qubit in het spel is, kan het

systeem verstrengeld of entangled geraken.

• Bijvoorbeeld het entangled register:

|ψit0

√ = 1/2 |000i + 1/ 2 |110i + 1/2 |111i

• Als we de msb bit observeren als ‘1’ dan valt de toestand

ineen tot:

|ψit1

p √ = 2/3 |110i + 1/ 3 |111i

• Hierdoor is de uitkomst van de 2de bit beïnvloed! Er is nu

100% kans om ‘1’ te meten inplaats van de 75% van voor de observatie. qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.11

Entanglement [2] • Met behulp van entanglement kunnen we bijvoorbeeld

volgende toestand maken (EPR paar): √ √ |ψi = 1/ 2 |00i + 1/ 2 |11i

Met 50% kans om ‘00’ te zien en 50% kans om ‘11’ te zien. Zelfs indien we deze 2 qubits lichtjaren van elkaar zouden verwijderen (bv als 2 verstrengelde fotonen) dan nog beïnvloedt een meting op de ene qubit de toestand van de andere! • Dit kan gebruikt worden door Alice en Bob voor het

uitwisselen van een geheime sleutel.

• Of aan boord van de Voyager voor teleportatie... qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.12

Quantum poorten • Quantum poorten zijn het quantum equivalent van logische

poorten (bv. NOT, XOR, ...) . Een voorbeeldje van een quantum circuit voor het verwisselen van 2 qubits (SWAP): |k1 i |k0 i

k

t

k

t

k

t

• Quantum mechanica + thermodynamica ⇒ reversibele

poorten die geen energie verbruiken! Enkel het wissen van informatie verbruikt energie.

• Ook al passen we een quantum poort bijvoorbeeld enkel toe

op bit k, alle 2n golffuncties in de toestandsvector worden hierdoor beïnvloed. qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.13

Universele quantum Turing machine • We kunnen een universele QTM definiëren die elk quantum

systeem en elke klassieke TM en PTM efficiënt kan emuleren in O(poly(n)).


– 18/12/2001 – 21:25 – p.14



• Een quantum algoritme kan een exponentiële versnelling

bereiken tegenover zijn klassieke tegenhanger. Maar er is maar één praktisch algoritme met deze eigenschap bekend: Shor’s factorisatie algoritme.


– 18/12/2001 – 21:25 – p.14



• Een quantum algoritme kan een exponentiële versnelling

bereiken tegenover zijn klassieke tegenhanger. Maar er is maar één praktisch algoritme met deze eigenschap bekend: Shor’s factorisatie algoritme.

• ⇒ Quantum computers kunnen meer problemen aan dan

klassieke computers en kunnen elk klassiek algoritme simuleren in polynomiale tijd. Echter:

Een klassieke computer heeft exponentieel veel tijd en geheugen nodig om een quantum algoritme te simuleren. qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.14

deel II:

Simulatie van een quantum computer


– 18/12/2001 – 21:25 – p.15

Beschrijving in lineaire algebra • De toestand van een n bit quantum computer wordt

voorgesteld door een complexe vector van dimensie 2n .

• Er is enkel nood aan 1 bit poorten met eventueel een

controle bit. Zo een 1 bit poort wordt voorgesteld door een 2 × 2 unitaire matrix. De poort naïef toepassen, expandeert deze matrix naar een 2n × 2n matrix, dit kan gelukkig efficiënter geïmplementeerd worden...

• Bij observatie moet er willekeurig één mogelijke toestand

uitgepikt worden, rekening houdend met de waarschijnlijkheden, en moet de vector consistent gemaakt worden met deze observatie. qc-sim-intro.tex – Quantum computing – Dirk Nuyens

– 18/12/2001 – 21:25 – p.16

Haalbaarheid van QC simulatie • Doordat het geheugen voor de toestandsvector exponentieel

is in het aantal bits O(2n ), kunnen enkel speelgoed probleempjes gesimuleerd worden.

• Eén uitvoering van een quantum operator heeft O(2n )

stappen nodig op een klassieke computer omdat elke vectorcomponent moet aangepast worden.

• De bestaande quantum computer simulators beweren dat ze

tot 20 qubits kunnen simuleren. Ze zijn echter heel traag en gebruiken veel geheugen...

• Zware optimalisaties zijn echter niet te verwachten voor een

simulator, want dan zou er iets niet kloppen met de theorie.


– 18/12/2001 – 21:25 – p.17

Einde Vragen?


– 18/12/2001 – 21:25 – p.18

Quantum computing. Dirk Nuyens. dept. computerwetenschappen KULeuven

Recommend Documents