A tantárgy az alábbi témakörök ismeretére épít:
Alapvető determinisztikus és randomizált algoritmusok, lineáris algebra, a csoportelmélet alapjai.
A tantárgy szerepe a képzés céljának megvalósításában:
TTK Matematikus doktori képzés-kötelezően választható, TTK Fizikus MsC-szabadon választható
A tantárgy részletes tematikája magyarul és angolul:
A kvantumszámítógépek alapjai. Egy-két kvantum bites példák (teleportálás, kulccsere, a Deutsch-Jozsa-algoritmus). Keresés:Grover algoritmusa (alsó korláttal), permutáció-invertálás.
Simon algoritmusa, a feladat klasszikus bonyolultsága. Sajátértékbecslés és a kvantum Fourier-transzformáció.
Shor algoritmusai törzstényezős felbontásra és a diszkrét logaritmus számítására.
A rejtett részcsoport-probléma, algoritmus véges kommutatív csoportokban. Alkalmazások.
A rejtett részcsoport-probléma lekérdezési bonyolultsága. Kuperberg algoritmusa a diéder-csoportra. Kvantum-algoritmusok néhány vállogatott kombinatorikus feladatra. Technikák alsó becslésekre. Hallgren algoritmusa Pell-egyenletek megoldására.
Követelmények vizsgaidőszakban:
Szóbeli vizsga, beszámoló választott publikációról.
Konzultációs lehetőségek:
Az előadóval megbeszélt formában.
Jegyzet, tankönyv, felhasználható irodalom:
M. Hirvensalo: Quantum Computing, Springer, 2004
A.M. Childs, W. van Dam: Quantum algorithms for algebraic problems, Reviews of Modern Physics 82, 1-52., 2010
Nyomtatóbarát változat
