De Kwantumcomputer Patrick De Causmaecker Katholieke Universiteit Leuven Campus Kortrijk
Mezelf • Licentiaat Wiskunde (Gent) • Doctor in de Fysica (Leuven) • Professor Informatica (Leuven-Kortrijk) Richtingen Wiskunde, Fysica, Informatica
Mijn Groep • ~20 onderzoekers • Artificiele intelligentie voor complexe combinatorische optimalisatie Optimalisatie in gedistribueerde systemen/Planning en Scheduling/Roosters voor personeel/bioinformatica/e-learning/digitale beeldverwerking/
De professor en zijn doctoraatsstudenten
I am currently Professor of Chemistry and I am also Associate Vice President for Research at UNT. I therefore maintain two offices on campus Chemistry Department (office hours only)
VP for Research Office (most times)
Mail ‘s ochtends: Doe het volgende experiment Laad de shaker Start de machine Start de analyse Zend me het rapport
De doctoraatsstudenten van de professor Hij komt toch nooit in het labo. Kunnen we het niet zonder ons laten gebeuren?
We kunnen het experiment simuleren. Maar dan hebben we wel een kwantumcomputer nodig
De student van de professor Ik wil wel een mooie zonnige dag. Kunnen we het weer exact en met zekerheid voorspellen?
Misschien wel. Maar dan heb ik een kwantumcomputer nodig.
De Kwantumcomputer doet aan Quantum Computing
• De kwantumcomputer is nog in een vroeg stadium • Maar wat is Quantum Computing
Gewone computers doen aan computing
• Wat is het verschil met het ‘gewone’ computeren • Wat is Computing
‘Gewoon’ computeren 1936 : Alan Turing “On Computable Numbers” “Turing Machine” Kan elk getal berekend worden? Wat is dat eigenlijk, ‘berekenen’?
Een machine van Turing. • Hypothetisch, wiskundig model • Afhankelijk van de toestand en de waarde onder de leeskop: – Schrijf 0/1/spatie – Schuif Kop rechts/links – Ga naar toestand X
Toestand Leeskop
1
01101
x 0
y
Aandrijfwiel band
0 1
0
Oneindige band
1
Bijvoorbeeld: vermenigvuldig met 2
• Input: een band met het getal in het binair stelsel • Een verzameling 0 # -> 0 L 2; regels 0 0 -> 0 L 0; 0 1 -> 0 L 1; 1 # -> 1 R 2; 1 0 -> 1 L 0; 1 1 -> 1 L 1; 2 # -> # L h; 2 * -> * R 2;
•
0
1 1
0
x
0
1
1 0
0
http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
x
Een ander voorbeeld: spring • Input: een band met willekeurige tekens • Verplaats de kop over een aaneensluitende rij tekens (L of R) 0 * -> * L 1; 1 # -> # R 2; 1 * -> * L 3; 2 # -> # R 4; 2 * -> * R 2; 3 # -> # L 5; 3 * -> * L 3; 4 # -> # L 5; 4 * -> * R 4; 5 * -> * R h;
0
y
1 1
0
y z x
1
0
y
1 1
0
y z x
1
Nog een ander voorbeeld • Een machine die niet stopt
0
y z x
1
0 # -> 1 L 0; 0 * -> * R h; 0
1
1 1
1
y z x
1
Een algemene machine? • Bestaan er Turing machines die alle andere Turing machines kunnen simuleren? • Turing bewees dat dergelijke machines bestaan. • We noemen ze ‘universele Turing machines’ • Hun ‘eindige’ versies zijn doorgedrongen in ons dagelijks leven.
Input voor de machine
Beschrijving van de machine
Vraag van Turing • Kunnen we zeker zijn dat een Turing machine stopt voor een bepaalde input? (de toestand h bereikt) • Kunnen we voor elke machine bepalen of ze ooit stopt op een bepaalde input?
Even nadenken • Als we dat konden, dan zouden we een machine kunnen maken die een functie h berekent. • We kunnen de beschrijving van p op een band schrijven en als invoer gebruiken.
Wat is de waarde van h(p,p)?
Machine p Met invoer i
– h(p,i) = 0 • als machine p niet stopt op invoer i
– h(p,i) = 1 • als machine p stopt op invoer i 0: machine stopt niet 1: machine stopt
Even nadenken • Gegeven een willekeurige machine die een functie van twee argumenten berekent: f(x,y) • Maak een machine voor het algoritme g(x,y) • Deze machine stopt enkel als f(x,y) = 0
Zolang (f(x,y) <> 0) doe niks g(x,y) = 1
Wat is de waarde van h(g,g)?
Even nadenken • We tonen aan dat • f(e,e) = 0 => g(e,e) stopt, h(e,e) = 1 h(e,e) <> f(e,e). • f(e,e) <> 0 => g(e,e) • Maar f was een stopt niet, h(e,e) = 0 WILLEKEURIGE h(e,e) <> f(e,e)!!! machine • h verschilt dus van Een Turing machine alle mogelijke kan dus niet alle machines!!! mogelijke functies berekenen!
These van Turing en Church Voor elke functie die we natuurlijkerwijs beschouwen als berekenbaar bestaat er een Turing machine om ze te berekenen. There exists or can be built a universal computer that can be programmed to perform any computational task that can be performed by any physical object" http://math.hws.edu/TMCM/java/labs/xTuringMachineLab.html
Is alles gezegd? • Gegeven een lijst met steden. Je moet alle steden juist 1 keer bezoeken, terugkeren waar je begon en een ZO KORT MOGELIJKE AFSTAND AFLEGGEN
Traveling Salesman • Bestaat er een Turing machine voor het probleem van de reizende koopman? • Ja, er zijn immers slechts een eindig aantal mogelijkheden. • (Zij het zeer veel!)
Traveling Salesman • Bestaat er een Turing machine die de beste oplossing vindt in een aanvaardbare tijd? • Dat weten we niet. Alle bekende methodes hebben een tijd nodig die exponentieel toeneemt met het aantal steden.
effect van het aantal steden 160 140 120 100 80 60 40 20 0
n n^2 log(n) exp(n) n!
1
2
3
4 n
5
6
Kunnen we beter doen? Noteer de steden a,b,c,d,e,f,… abcdef… bacdef… acbdef… cabdef... bcadef… cbadef… abdcef… …
• Kunnen we alle mogelijkheden tegelijkertijd onderzoeken? • Parallelle computers zijn geen optie: het aantal benodigde processoren neemt toe met de exponent van het aantal steden.
Bestaat er dan een manier om verschillende waarden tegelijk voor te stellen?
• Ja
KwantumTOESTANDEN
Twee spleten experiment
http://www.youtube.com/watch?v=DfPeprQ7oGc
Kwantumtoestanden • Op het ogenblik van de passage bevindt het electron zich in een soort mengtoestand: superpositie • Deze wordt verbroken door de waarneming
Laten we eenvoudig beginnen • Een ‘beam splitter’ is een halfdoorlatende spiegel • De ‘helft’ van het inkomende licht kaatst terug (Reflectie) • De andere helft gaat door (Transmissie)
• Dit gebeurt ook met één foton…
Beam splitters : de reflectie of de transmissie van 1 foton kan niet deterministisch zijn.
Beam splitters : interferentie
Intensiteit afhankelijk van stand van de spiegel
Constructieve/destructieve interferentie
Beam splitters : hoe kan dit gebeuren met 1 foton
TT RR R
T TR RT
Wat is de waarschijnlijkheid van TT,RR,RT,TR? • Laplace: indien we niets weten over de waarheid van een uitspraak, dan is de waarschijnlijkheid ervan ½. • Bayes: – A en B (onafhankelijke) gebeurtenissen, – PA en PB de waarschijnlijkheden, – waarschijnlijkheid PA of B = PA + PB
Toegepast op de Beam Splitter U TT RR R
T L
PTT = PRR = PRT = PTR = ¼ PU = P TT of RR = PTT + PRR PL = P TR of RT = PTR + PRT EN KAN DUS NOOIT NUL ZIJN
TR RT
Waarschijnlijkheidsamplitudes • Feynman: als de gebeurtenissen fysisch niet te onderscheiden zijn, gebruik dan waarschijnlijkheidsamplitudes! • ATT=(½, ½), A RR =(-½, ½) • ATR=(½, -½), A RT =(-½, ½) • ATT of RR= (½ - ½, ½+½) = (0,1) • PTT of RR= (½ - ½) 2 + (½+½) 2 = 1
Waarschijnlijkheden en hun amplitudes
½
½
-½
-½
L en U dectector amplitudes R T
U-detector TR RT
RT
TR
L-detector Alles naar U
Gedeeld U en L
TT
RR
TT
RR
TT RR TR RT
Zien in het donker U TT RR R
PRT = PRR = ½ PTT = PTR = 0 T L
Hoewel de bom afgaat bij één foton is er een kans dat we hem ‘zien’!
TR RT
Een ander voorbeeld: Polarisatie
• Licht is gepolariseerd • Loodrecht op de richting kunnen we de polarisatie meten • Dit gebeurt ten opzichte van twee assen (V en H)
V
H
Een ander voorbeeld: Polarisatie • Een polarisatiefilter laat licht van een bepaalde polarisatie door • Als deze polarisatie geroteerd is t.o.v. die van de invallende lichtbundel wordt slechts een deel doorgelaten
V
H V’ H’
Een ander voorbeeld: Polarisatie
• Dit gebeurt (klassiek) door projectie… • Wat in het geval van 1 foton? • -> amplitudes!
Een ander voorbeeld: Polarisatie • Bij opeenvolgende polarisatieschermen wordt de kans van transmissie telkens bepaald door de grootte van de amplitude na projectie • Het foton heeft na transmissie de juiste polarisatie.
1982: Richard Feynman • Elk eindig fysisch object kan door een ‘universele simulator’ nagebootst worden
Bits en Qubits 10101101001010010111011100011101010110010000110101011
• Computers : 1 en 0 • Natuur (dna) : AGCT – (Adenine, Guanine, Cytosine, Thymine)
• Hoeveel informatie bevat 1 bit?
Shannon’s informatietheorie • Informatie is Munt : complementair aan P(kop) = ½ willekeur P(letter) = ½ • Eens we weten wat de uitkomst is hebben informatie gewonnen
Na de opworp kennen we 1 bit meer
Hoe zit dat in de Kwantumwereld? • Het foton beslist niet op voorhand • Het ‘kiest’ bij elke spiegel • Het bevat een oneindige hoeveelheid informatie! • Een qubit
Rekenen met qubits gebeurt met amplitudes U TT RR R
T L
TR RT
U TR RT
RT
TR
L Alles U U en L
TT
RR
TT
RR
In het geval van polarisatie • Na passage door een P. filter heeft het foton een polarisatie volgens de as van het filter • Bij het volgende filter zal het passeren of niet passeren op basis van de amplitude
Kwantum poorten • Klassieke computers zijn opgebouwd uit logische poorten • Bestaat er iets dergelijks voor Kwantumcomputers ?
Principe van Landauer • Waarom warmen computers op? • Landauer (196*): Wanneer er een bit informatie wordt vernietigd moet warmte afgegeven worden
Belang voor de Kwantum computer
• Warmte vertelt iets over wat er in de computer gebeurt, dit is een observatie
Kwantum poorten mogen geen informatie verloren laten gaan. Ze moeten ‘reversibel’ zijn
Kwantum poorten: Toffoli poorten • Poorten worden gekarakteriseerd door waarheidstabellen And Input 1 1 0 0
1 0 1 0
Output 1 0 0 0
Toffoli input A B C 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 1 1 1 1
Toffoli output A B C 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0
Not en And met Toffoli poorten 1
1
1
1
C
NOT C
Ga
rba ge (ro mm el) bit s
A
A
B
B
0
A AND B
• Bennet: reversibele Turing machines
Kwantum geheugen U
D
P = ½=(√½)2
A = (√½, √ ½ ) (T,R)
D U
P = ½=(√½)2 One QUBIT
Superpositie
Effect van een beam splitter D
D
(√ ½ , √ ½ )
(0,1)
U
(1,0)
(√ ½ , -√ ½ )
U D
D 45 U
U 45
Kwantum geheugen D
U
(√ ½ , √ ½ )
(0,1)
(1, 0) D 45
D
D
45 U U
U
Waar zit de computer? 1 D
0
0 U
1
1 D
0 U
1 D
0 U
Kwantum computer: parallel reversibel rekenen
0
1
1
0
Poorten • Een Beam Splitter roteert de amplitueds 45 graden • We noemen dit een Hadamard poort • Klassiek hebben twee H’s het effect van een NOT
D
U
(0,1)
(1, 0) D
U
H
H
NA METING!
Universele Kwantum poorten • Wat we nodig • Het is niet moeilijk hebben zijn om Toffoli of Kwantum poorten analoge poorten te (bijv. Hadamard) maken • Universele • Deze laten toe om poorten laten toe alle KLASSIEKE alle reversibele poorten te bouwen berekeningen te doen. • Maar…
Aangepaste these van Turing en Church
There exists or can be built a universal quantum computer that can be programmed to perform any computational task that can be performed by any physical object"
Controlled Not poorten • CN poort • inverteer target a.s.a control = 1 • Implementatie met behulp van beam splitters en gepolariseerd licht is mogelijk.
target
control
Tar Con Tar Con 0
0
0
0
1
0
1
0
0
1
1
1
1
1
0
1
Een eenvoudige kwantumcomputer • Onze computer zal kunnen vermenigvuldigen met 2! • Hij wordt wel reversibel gedefinieerd : een bit extra voor de overdracht
Input
Output
O
0
0
1
1
0
Input
Output
CY
One
CY
One
0
O
0
0
0
1
1
0
Realisatie met CN poorten Input
Output
CY One CY One 0 O 0 0 0 1 1 0
control http://jquantum.sourceforge.net/jQuantumApplet.html
control
Nog geen Quantum computing !
target
target
Een Kwantum CN poort De Hadamard poort maakt een superpositie van 1 en 0! De computer berekent nu ZOWEL 1x2 als 0x2 De uitkomst is natuurlijk ook een superpositie Probeer die te lezen en Je krijgt 00 of 10 SO WHAT?!
target
control
H
Het probleem van David Deutsch
• Gegeven een ja/nee vraag (voorbeelden genoeg!) die misschien afhangt van een ja/nee beslissing (ook voorbeelden). Kan ik uitmaken of de beslissing inderdaad invloed heeft? De berekening zal lang duren… ik kan ze geen twee keer doen.
Het algoritme van Deutsch • David Deutsch bedacht het schema hiernaast. • De rode operator transformeert de amplitudes
1 H
0
? H
H
y(-1)f(x)
y
x
Het algoritme van Deutsch √½ (1,1) (1,0) H
y(-1)f(x)
y
x √½ (-1,1) (0,1)
H
? H
1 45
MAGIC CIRCLE
0
Het algoritme van Deutsch Product van de amplitudes
√½ (1,1) (1,0)
H
*√½
y=1
y=0
x=1
-1(-1) f(1)
-1(-1) f(1)
x=0
1(-1) f(0)
1(-1) f(0)
√½ (-1,1) (0,1)
H
H
?
Na de laatste Hadamard
MAGIC CIRCLE
*(-1)f(x)
y
1 45 0
x
*½ x=1
y=1
y=0
-(-1)f(1)-(-1)f(0)
-(-1)f(1)-(-1)f(0)
x=0
-(-1)f(1)+(-1)f(0) -(-1)f(1)+(-1)f(0)
Het algoritme van Deutsch √½ (1,1) (1,0)
Als f(1) = f(0) meten we x = 1
H
*½ x=1
y=1
y=0
1
1
x=0
0
0
√½ (-1,1) (0,1)
H
H
?
De Kwantumcomputer beslist f(1)=f(0) in één keer!
Als f(1) <> f(0) meten we x = 0 *½ x=1
y=1
y=0
0
0
x=0
1
1
Andere algoritmen • Uitbreiding van Deutsch algoritme tot functies van n bits • Factorisatie algoritme van Shor: vindt waarschijnlijk de priemfactoren van een getal • Zoekalgoritme van Grover: vindt met 50% zekerheid een willekeurig element in een verzameling van N elementen in een tijd evenredig met vierkantswortel N
Toestand • Veel theoretische vragen blijven open • Wat is Kwantuminformatie? • Welke problemen kunnen we (niet) oplossen met een QC? • …
• 2006 – cage a qubit in a buckyball – 12 qubit Kwantum computer – Seven atoms -> Kwantum gate, • 2007 – Single electron qubit memory. – D-Wave Systems 28-qubit qc • 2008 – quantum bit stored – Superior qc test developed – …
http://en.wikipedia.org/wiki/Timeline_of_quantum_computing
