Kvantové počítání
Pavel Cejnar
ÚČJF MFF UK Praha
pavel.cejnar @ mff.cuni.cz
MFF UK, Praha, říjen 2013
02/24
Motivace
Serge Haroche
David J. Wineland
Zaprvé:
The Nobel Prize in Physics 2012 was awarded
jointly to Serge Haroche and David J. Wineland
"for ground-breaking experimental methods that
enable measuring and manipulation of individual
quantum systems"
Zadruhé:
Základ rodících se „kvantových technologií“ – „manybody“ kvantová fyzika
Zatřetí:
Je to prostě zajímavé
a zábavné!
Louis Emile Adan
(1839-1937)
An amusing story
03/24
Historie
Rolf Landauer (1927-1999)
1960-70s: Analýzy fyzikálních omezení klasických počítačů
„Vratné počítače“ (počítání založené na reverzibilních procesech)
1959:
1960:
1961:
1969:
1973:
1981:
Feynman pronesl řeč „There’s Plenty of Room at the Bottom”
První úvahy o fyzikálních mezích miniaturizace výpočetních procesů
Landauer ukázal, že každý ireverzibilní krok výpočtu produkuje entropii-teplo
První návrh „spinového počítače“ (kvantové vlastnosti chápány spíš jako omezení)
Benett předkládá koncept univerzálního reverzibilního počítače
Fredkin & Toffoli demonstrují výpočetní reverzibilitu na “billiard ball computer”
Edward Fredkin
Qmin=(ln2)kT
04/24
Historie
Richard Phillips Feynman (1918-1988)
1960-70s: Analýzy fyzikálních omezení klasických počítačů
1980-81: První úvahy o prospěšnosti QM pro teorii počítání
Richard Feynman, Jurij Manin, …
05/24
Richard Phillips Feynman (1918-1988)
Historie
1960-70s: Analýzy fyzikálních omezení klasických počítačů
1980-81: První úvahy o prospěšnosti QM pro teorii počítání
Richard Feynman, Jurij Manin, …
1985:
1989:
Kvantový Turingův stroj
Elementární kvantové operace
David Deutsch
1994:
Kvantový faktorizační algoritmus
Peter Shor
N = P1 ⋅ P2
{

N ⇒ P1 , P2 x
P1 , P2 ⇒ N
1992: Deutsch-Joszův algoritmus
1994: Simonův algoritmus
zjišťování vlastností neznámé funkce
pomocí konečného (co nejmenšího) počtu volání
1996: Groverův algoritmus
prohledávání nesetříděné databáze
06/24
Tři zdroje
David Hilbert (1862-1943)
 1) Linearita kvantové mechaniky
Stavy kvantových systémů = vektory v Hilbertově
prostoru H
„superpozice“
Ψ = α Ψ ′ + β Ψ ′′
Stavy částečně nerozlišitelné
=> kvantová neurčitost
míra nerozlišitelnosti daná skalárním součinem
Ψ
H
*
2
= Ψ′ Ψ
2
1
1



 

≤ Ψ′ Ψ′ Ψ Ψ
Ψ′
 2) Kvantová provázanost
*
Stavy složených systémů = vektory v součinovém prostoru H = H1 ⊗ H2
Např.
Ψ = α Ψ1′ ⊗ Ψ2′ + β Ψ1′′ ⊗ Ψ2′′
≠
Ψ1 ⊗ Ψ2
Provázaný stav => podsystémy nemají své vlastní stavové vektory
nedají se popsat odděleně, nýbrž vykazují kvantové korelace
(bez ohledu na vzdálenost)
 3) Vlastnosti kvantových měření
Výsledky měření mají pravděpodobnostní charakter PΨ (a ) = a Ψ
Měření mění stav systému
Ψ → a
2
07/24
Kvantový bit
= qubit, Q-bit, „kvabit“ …
1
ψ =α
 0 +β

θ
cos 2
e iφ sin θ2
Fyzikální realizace
• Spinové projekce fermionu s=½
(elektron, proton, liché jádro…)
• Lineární/kruhové polarizační stavy fotonu
• Dva vybrané energetické stavy atomu
• Proudové stavy supravodivého prstence….
08/24
Kvantový registr
Obecný stav n-tice Q-bitů = superpozice všech číselných hodnot
Ψ = α 0 0  00 + α1 0  01 + α 2 010 +  + α 2n −1 111










0
1
Příprava homogenní superpozice:
čas t
0
0
1
0
0
2
n
0
H
H
H
H
∝ 0 +1
∝ 0 +1
∝ 0 +1
∝ 0 +1
2
2 n −1
09/24
Kvantový výpočet
U
U=UnmUl���UkjUi
KVANTOVÝ
ALGORITMUS
(program)
10/24
„Kvantové programování“
Rozložení kvantového výpočtu na základní operace:
1) Operace na jednom Q-bitu
2) Operace na dvou Q-bitech
11/24
„Kvantové programování“
příklady
Kvantová
Fourierova
transformace
Polynomiálně rychlá realizace
existuje:
Výpočet hodnoty dané
diskrétní funkce
Operace musí být reverzibilní => pro
neprostou funkci f(x) je třeba na
výstupu uchovat hodnotu argumentu
Existence/neexistence
polynomiálně rychlé
realizace závisí na
funkci f(x)
12/24
Příklad
určení periody r diskrétní funkce f(x)
Tento výpočet
pro jistou funkci f (x )
je srdcem Shorova
algoritmu, který vede
k polynomiálně rychlé
v počtu cifer n rozkládaného čísla
faktorizaci zadaného
čísla N = P1·P2
Pr (y)
13/24
DEKOHERENCE !!!
Překážky
(a) koherentní superpozice
ψ =α 0 +β 1
(b) statistická směs
amplitudy
pravděpodobnosti
p0 = α
Pokud uskutečnění libovolné z alternativ
nelze principiálně zjistit měřením na
jiném objektu => interference
2
p1 = β
2
Pokud uskutečnění některé z alternativ
lze, byť i jen v principu, zjistit měřením
na jiném objektu => interference
► Interferenční experiment
Zánik interference při možnosti zjištění
dráhy částice:
► Interakce Q-bitu s prostředím
=> vznik provázanosti:
(0)
0 ⊗ Φi 
→
0
⊗
Φ
i (t )
t
(1)
1 ⊗ Φi 
→
1
⊗
Φ
i (t )
t
(α 0 + β 1 ) ⊗ Φ
i
(0)
(1)

→
α
0
⊗
Φ
(
t
)
+
β
1
⊗
Φ
(t )
i
i
t
Φ i( 0 ) (t ) Φ i(1) (t ) 
→
0
t
Pro
se obě
alternativy 0 a 1 stávají principiálně
stav prostředí
stav Q-bitu
rozlišitelné vhodným měřením na prostředí
⇒ koherentní superpozice → statistická směs => konec Q-výpočtu !!!
14/24
Překážky
DEKOHERENCE !!!
…….
15/24
DEKOHERENCE !!!
…a jejich
překonávání
Opravné procedury využívající
redundanci
Ne však prosté „namnožení“ Q-bitu – tomu brání kvantový no-cloning teorém:
P. Shor, Phys. Rev. A 52, R2493 (1995)
A. Steane, Proc. R. Soc. Lond. A, 452, 2551 (1996)
E. Knill and R. Laflamme, Phys. Rev. A 55, 900 (1997)
Ψ
Ψ
Ψ
Procedura opravuje chyby, pokud se objeví jen na 1 (libovolném) Q-bitu
(předpoklad potlačení pravděpodobnosti současné chyby na více Q-bitech)
Klasifikace chyb
ok
založená na obecném rozkladu evolučního operátoru v prostoru Q-bit � prostředí:
„flip“
q
U q +e
„flip + phase“
q
„phase“
q
q
1 0
0 1
 0 − 1
1 0 
 ⊗ O0e + 
 ⊗ O1e + 
 ⊗ O2e + 
 ⊗ O3e
= 
0 1
1 0
1 0
0 − 1











I
σ1
Notace:
σ3
iσ 2 = 12 [ σ 3 ,σ1 ]
α 
α 0 + β 1 ≡  
β 
Oprava obecné chyby:
1 Q-bit → 5 Q-bitů
minimálně
Byly navrženy i jiné metody prevence chyb…
16/24
Adiabatické kvantové počítání
Farhi, Goldstone, Gutmann, Lapa, Lundgren, Preda, Science 292, 472 (2001)
Aharonov, van Dam, Kempe, Landau, Lloyd, Regev, SIAM J.Comput. 37, 166 (2007)
Příklad: problém splnitelnosti pro N bitů zα ∈ {0,1} a m klauzulí typu
α =1, 2 ,... N
zα + z β + zγ = 1
Realizace pomocí spinových Q-bitů
α , β ,γ ∈{1, 2 ,... N }
…
……….
sαz = + 12
sβz = − 12
t =0   t =T
 
g 0 = 0  →  gT = 1
H (0) = H in   H (1) = H out
t=0
………………..
Předpokládejme, že problém má právě jedno řešení. Toto
řešení je zakódováno v základním stavu Hamiltoniánu:
(
)
H out = 12 ∑ sαz + sβz + sγz − 12 − m2
H
α , β ,γ )
(

in





H ( g t ) = (1 − g t )− ∑ sαx  + g t ∑ M αβ sαz sβz − 12 ∑ Nα sαz 
α
 α 
 αβ

0< t < T
t=T
počet klauzulí
týkajících se
bitů zα a z�
základní stav
→→  →
plně separabilní
⇒ „jednoduše“
připravitelný
2
počet klauzulí
týkajících se
bitu zα
základní stav
↑↓  ↑
splňující zadanou
soustavu klauzulí !!!
17/24
Adiabatické kvantové počítání
Farhi, Goldstone, Gutmann, Lapa, Lundgren, Preda, Science 292, 472 (2001)
Aharonov, van Dam, Kempe, Landau, Lloyd, Regev, SIAM J.Comput. 37, 166 (2007)
Příklad: problém splnitelnosti pro N bitů zα ∈ {0,1} a m klauzulí typu
α =1, 2 ,... N
zα + z β + zγ = 1
Realizace pomocí spinových Q-bitů
α , β ,γ ∈{1, 2 ,... N }
…
sαz = + 12
……….
………………..
(
sβz = − 12
t =0   t =T
 
g 0 = 0  →  gT = 1
H (0) = H in   H (1) = H out
Předpokládejme, že problém má právě jedno řešení. Toto
řešení je zakódováno v základním stavu Hamiltoniánu:
)
H out = 12 ∑ sαz + sβz + sγz − 12 − m2
H
α , β ,γ )
(

in





H ( g t ) = (1 − g t )− ∑ sαx  + g t ∑ M αβ sαz sβz − 12 ∑ Nα sαz 
α
 α 
 αβ

Adiabatický teorém QM
Hamiltonián H(g) závisející na externím parametru
g, který se explicitně mění s časem: g=gt
Počáteční stav systému = základní stav počátečního
Hamiltoniánu H(g0), tj.: Ψ (t = 0) = Ψ ( g )
0
t =0
Otázka: Jak se bude vyvíjet stav systému s časem?
Parciální odpověď: Bude kopírovat základní stav
Hamiltoniánu H(gt), ale jen pokud je splněna
−1
podmínka adiabaticity:
Ψ1 ( g ) dgd H ( g ) Ψ0 ( g )
dg
>>
dt
[E1 ( g ) − E0 ( g )]2
počet klauzulí
týkajících se
bitů zα a z�
základní stav
→→  →
plně separabilní
⇒ „jednoduše“
připravitelný
2
počet klauzulí
týkajících se
bitu zα
základní stav
↑↓  ↑
splňující zadanou
soustavu klauzulí !!!
18/24
Adiabatické kvantové počítání
Farhi, Goldstone, Gutmann, Lapa, Lundgren, Preda, Science 292, 472 (2001)
Aharonov, van Dam, Kempe, Landau, Lloyd, Regev, SIAM J.Comput. 37, 166 (2007)
Příklad: problém splnitelnosti pro N bitů zα ∈ {0,1} a m klauzulí typu
α =1, 2 ,... N
zα + z β + zγ = 1
Realizace pomocí spinových Q-bitů
α , β ,γ ∈{1, 2 ,... N }
…
……….
sαz = + 12
………………..
sβz = − 12
Schützhold, Schaller, Phys.Rev. A 74, 060304 (2006)
Průchod kvantovým fázovým přechodem
prvního řádu
druhého (vyššího) řádu
Mezera mezi základním
a prvním excitovaným
stavem:
∆E ≈ e − cN
∆E ≈ cN − k
… ale účastní se
velký počet hladin
19/24
Další algoritmy
• Prohledávání databází
• Problém splnitelnosti
• Úlohy optimalizace ?
Rozpoznávání obrazců ??
Umělá inteligence ???
• Simulace fyzikálních a chemických
(biologických) systémů
Mnohočásticový problém
Asparu-Guzik, Kassal… (2008)
(jaderná fyzika, chemie)
Cvičení: NF nerozlišitelných fermionů na Ω ≥ NF
jednočásticových stavech. Dimenze Hilbertova prostoru:

Ω

−1 
N F  ln
Ω(Ω − 1)  (Ω − N F + 1)  Ω 
N
d=
=   ≈ e  F 
N F!
 NF 
Např. pro jádro uhlíku 12C (6 p + 6 n) můžeme použít bázi
energetických vlastních stavů harmonického oscilátoru,
kterou shora omezíme slupkou
N·ħω. Uvažme N = 4:
2
 70 
d = dπ ⋅ dν =   = 17191401522520225 ≈ 1.7 ⋅1016
6
Důvtipnější ořezání báze (podle celkové energie NF-částicové
konfigurace) vede ke zmenšení dimenze na „pouhých“ d ≈ 109
Možné aplikace při navrhování nových materiálů,
chemicky/biologicky aktivních molekul, farmaceutik…
20/24
a) Uvězněné ionizované atomy (de)excitované laserem
Možné realizace
a)
b)
c)
d)
e)
c)
1
2
3
6
12
≈μm
Uvězněné ochlazené ionty
Kvantová elektrodynamika v dutině
Jaderná magnetická rezonance
Spinotronika v křemíku
…………..
NMR v kapalné fázi (manipulace se spiny pomocí
pulsů mag. pole s využitím
spin-spinových interakcí)
b)
d)
Molekula se 7 Q-bity
tvořenými jádry 13C,19F
(pracuje se se statistickým souborem těchto jader)
V roce 2001 proveden kvantový výpočet faktorizace
15 = 5 × 3
V roce 2011 pomocí NMR implementace adiabatického
kvantového výpočtu dosaženo:
143 = 13 ×11
Interakce atomů a záření v dutinovém rezonátoru
Manipulace se spiny elektronů (jader) v polovodičové mříži
21/24
Možné realizace
e)
Makroskopické proudy v supravodivých smyčkách
1911: Experimentální objev supravodivosti [Kamerlingh Onnes]
1957: Mikroskopická teorie => makroskopický kvantový jev
[Bardeen,Cooper,Schrieffer]
1962: předpovězen (1963 potvrzen) Josephsonův jev:
kvantové tunelování na spoji supravodič-izolátor-supravodič
1964: Sestaven první SQUID = Superconducting QUantum Interference Device
aplikace: měření slabých magnetických polí (~5×10−18 Tesla) např. v lékařství
1999: koncepce supravodivého Q-bitu [Mooij, Orlando, Levitov, Tian,van der Wal, Lloyd, Science 285, 1036]
Φi ≡ magnetický tok smyčkou, U ≡ celk. energie smyčky
Φ1x ,Φ2x ≡ externí magnetické toky – umožňují měnit
vzájemné uspořádání dvojice potenciálových jam v grafu
pro U. V blízkosti degenerace je základní a 1. exc. stav
vyjádřen jako superpozice
g = 12 ( ↑ + ↓ )
e = 12 ( ↑ − ↓ )
proudových stavů:
Při ochlazení na teploty T ~ 20 mK je počáteční stav
smyčky definovanou superpozicí proudových stavů.
Interakce mezi Q-bity => 2 Q-bitové operace
� D-Wave Systems
Johnson et al., Nature 473, 194 (2011)
?
23/24
Co na to Dilbert?
Vysvětlení:
Podle Everettovy mnohosvětové interpretace
QM jsou jednotlivé členy kvantové superpozice
„realizovány“ v různých „světech−vesmírech“.
Paralelní vesmíry jsou ve vzájemném kontaktu po
dobu udržení koherence kvantové superpozice.
Vyšší efektivita kvantové počítání = důsledek
paralelismu výpočtů probíhajících v takových
provázaných vesmírech.
24/24
MFF UK, laboratoře Troja, rok 3046
SHIFT HAPPENS.
Download

null