Bejelentkezés
 Fórum
 
 
Témakiírás
 
Friedl Katalin
Kvantumalgoritmusok

TÉMAKIÍRÁS

Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

témavezető: Friedl Katalin
helyszín (magyar oldal): Számítástudományi és Információelméleti Tanszék
helyszín rövidítés: SZIT


A kutatási téma leírása:

A 70-es évek végén fizikusok vetették fel, hogy mivel a kvantummechanikai jelenségeket nem sikerült számítógéppel hatékonyan szimulálniuk, talán egy kvantumhatásokra is építő géppel gyorsabban lehetne bizonyos problémákat megoldani. Ebből az ötletből született a számítás egy újabb matematikai modellje, a kvantum Turing-gép
.
A kvantum Turing-gép egyik legszembeötlőbb képessége, hogy egyszerre exponenciálisan sok számítási ágat tud követni, de az a nehézség, hogy a modell (és a fizika) szabályai szerint, ezekből nem egyszerű az eredményt (pl. van-e elfogadó számítási ág) kinyerni. Az új modell a szokásos algoritmikus megoldásoktól eltérő ötleteket, technikákat igényel. Az erejét mutatja, hogy pl. kvantum Turing-géppel egy szám prímtényezői polinom időben megtalálhatók (klasszikus Turing-géppel nem ismert ilyen algoritmus), illetve, hogy n rendezetlen elem közötti keresés Θ(√n) időben megvalósítható. A témakör nagy kérdése, hogy milyen feladatokra lehet a klasszikus megoldásnál lényegesen hatékonyabb kvantumaloritmusokat adni, és melyek azok a feladatok, ahol ez a technika nem segít.

A kutatás célja a meglevő algoritmikus módszerek vizsgálata, továbbfejlesztése, alkalmazhatósági körük vizsgálata. Például gráfokban a klasszikus párosítási, feszítőfa vagy folyamalgoritmusok kvantumosítása, a gyorsíthatóság mértékének meghatározása..

Irodalom:
- M. Nielsen, I. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000.
- újabb algoritmikus eredmények az arxiv.org/archive/quant-ph címről

felvehető hallgatók száma: 1

Jelentkezési határidő: 2015-06-26


2019. IX. 13.
ODT ülés
Az ODT következő ülésére 2019. november 22-én 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 2.2358 ( 2017. X. 31. )