A 70-es évek végén fizikusok vetették fel, hogy mivel a kvantummechanikai jelenségeket nem sikerült számítógépekkel hatékonyan szimulálniuk, talán egy kvantumhatásokra is épít? géppel hatékonyabban 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ó ág) kinyerni. Ehhez a szokásos algoritmikus megoldásoktól eltér? ötletek, technikák szükségesek. A modell 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^2 rendezetlen elem közötti keresés O(n) id?ben megvalósítható.

A kutatás célja a meglev? algoritmikus módszerek vizsgálata, továbbfejlesztése és alkalmazása. Ezen belül érdekes és fontos terület annak vizsgálata, hogy olyan alapvet? gráfalgoritmusok mint az összefügg?ség eldöntésére, legrövidebb utak keresésére szolgáló eljárások hogyan adatálhatók a kvantum modellre, mely feladatoknál érhet? el lényeges gyorsítás a hagyományos modellhez képest.

Irodalom:

Dr. Friedl Katalin
egyetemi docens
31-56
friedl@cs.bme.hu