IBM Brings Quantum Computing to the Cloud
• https://www.youtube.com/watch?v=DZ2DcILZAbM&feature=y outu.be
2016.05.05.
1
Ismétlés
The problem • Each unitary transform having eigenvector eigenvalues in the form of . • Phase ratio:
has
Quantum Phase Estimator
• How to initialize
?
Prob. amplitudes
2016.05.05.
6
Brutális!
• A H kapuk kapuval kigészítve
2016.05.05.
feletti Fourier-trafók. Néhány R feletti Fourier-trafók lesznek
9
IQFT
Searching in an Unsorted Database "Man - a being in search of meaning." Plato
History of data base searching v1
2016.05.05.
12
History of data base searching v2
2016.05.05.
13
History of data base searching v3
2016.05.05.
14
History of data base searching v4 Grover algorithm
2016.05.05.
15
Objectives • • • • •
Finding a certain entry in a database N items of size. The DB is unsorted. The DB contains M copy of the requested entry. Best classical solution: N question. How can be exploited quantum phenomena ?
x=?
General model of quantum algorithms Classical input
Initialization
Parallelization
Quantum input
Quantum output
Amplitude ampl.
Measurement
Classical output
Grover operator
Grover operator
T=H
Grover operator
Geometrical interpretation
Required number of iterations
Error analysis
Questions • • • •
What will happen if M=N/2 ? What shall we do if M>N/2 ? Is it possible to find the marked item with a single step? How to decrease the error probability? – Idea No. 1. – Idea No. 2.
2016.05.05.
24
Quantum counting – special phase estimation • Calculation of M can be traced back to phase estimation on the Grover operator.
Quantum counting – special phase estimation
Brutális!
Multiuser detection based on Grover algorithm
Direct sequence spread spectrum DS SS 3G mobile • Gyorsan változó kód (chip) komponensek
nagyfrekis
Φj(f )
~ Φ( f )
Φs ( f )
Kóder
c(t) Álvéletlen zaj vagy álvéletlen kód
Φt ( f )
Φr ( f )
Szinkronizálás
Dekóder
c(t)
(f) Φ
Szûrõ
Keskenysávú interferencia elnyomása Φt ( f )
Φs ( f )
St 0 =
S s0
S j 0 Bs
f
Bs
Φj(f )
Bt
S j0
f
f Bj
Bt ~ Φ( f )
Φr ( f )
Bs
Bj
S j0
S j0 St 0
Bj
S j0
S s0
Bt
Bj Bt
S s0
f
f
Bt
(f) Φ
Bt
f
Bs
Feldolgozási nyereség • • • • •
PG: Processing Gain Tulajdonképpen a kiterjesztés mértéke PG=kiterjesztett sávszélesség/eredeti sávszélesség A gyakorlatban SF=chipsebesség/bitsebesség SF: spreading factor
Kódosztás • CDMA: Code Division Multiple Access • A spektrumkiterjesztés a felhasználókhoz rendelt ortogonális kódokkal – Kombinált PHY + MAC – Kódok ortogonalitása korlátozott
Detektálás
Detektálás
Detektálás
Kvantum többfelhasználós detekció • Feladat: DS-CDMA rendszerben együttes detekció a bázisállomáson. • Vett komplex alapsávi jel:
Egyfelhasználós detekció • A detektor kimenete:
Kvantum többfelhasználós detekció
• MLS, Maximum Likelihod Sequence (jointly optimum) detekció:
• MBER, Minimum Bit Error Ratio (individually optimum) detekció:
Kvantum többfelhasználós detekció • Csatorna mátrix:
Kvantum többfelhasználós detekció • Komplexitás:
Kvantum egzisztencia tesztelés
Kvantum egzisztencia tesztelés • Cél: annak eldöntése, hogy a keresett elem egyáltalán előfordul-e az adatbázisban? • Klasszikus bonyolultság:
O(N).
• Speciális fázisbecslés a Grover-operátoron. • Fázisbecslés: – Unitér operátor sajátértéke: – Fázis: – Fázistényező közelítése:
Kvantum fázisbecslés
p qbit
• komplexitás: Klasszikus bizonytalanság
Kvantum bizonytalanság
Kvantum bizonytalanság
Kvantum egzisztencia tesztelés • Klasszikus bizonytalanság
• Komplexitás:
Kvantum egzisztencia tesztelés
• Hiba, ha az
MSB biten 0-tól eltérő érték van.
Kvantum egzisztencia tesztelés • Kvantum bizonytalanság:
• Komplexitás:
p
Kvantum szélsőérték keresés • Klasszikus rendezetlen adatbázis • Rendezés + Logaritmusos keresés • A rendezés nem mindig tehető meg! • A klasszikus logaritmusos keresés kombinálása kvantum egzisztencia teszteléssel
Kvantum szélsőérték keresés • Adatbázis (függvény!): • Feladat: • A kereső algoritmus:
• Grover kereséssel: • Komplexitás:
Alap Grover-algoritmus
• A Grover-algoritmus hiányosságai: – Az index regiszter bemeneti állapota rögzített (valós, egyenletes amplitúdó eloszlás). – Nem biztosított az 1 valószínűségű találat.
Általánosított Grover-algoritmus 1.1. tézis • 2-dimenziós bázis a V térben: Egyes speciális állapotok nem képezhetők le.
• Általánosított Grover-operátor:
Meghatározandó paraméterek és nem ismert!
Általánosított Grover-operátor • Feltétel:
legyen az
• Q megőrzi a teret. • Q alakja a V 2-dimenziós térben
• Q sajátértékei:
,
térben.
Lépésszám
Illesztési feltétel:
lépésszám
Optimális lépésszám • Az 1 valószínűségű találathoz szükséges lépésszám:
Beállítások
Fázisbecslés O(ld3(N))
:= a létrehozásához szükséges kapuk összessége := a felhasználó indító klasszikus állapota
