Jaunas zinātniskās grupas izveide kvantu skaitļošanā un datorzinātņu teorijā

Projekta vadītājs Andris Ambainis

Pierādīts, ka, rēķinot simetriskas funkcijas, starpība starp kvantu un tradicionālo algoritmu darbības laiku var būt ne vairāk kā polinomiāla. Tas apstiprina zinātnieku vidē eksistējošo uzskatu, ka, lai kvantu algoritmi dotu lielus ieguvumus, tiem jāizmanto ievaddatos esošas struktūras (piemēram, algebriska rakstura struktūras), kuras nepastāv priekš simetriskām funkcijām.

Sadarbībā ar Kioto universitāti un citām Japānas zinātniskajām institūcijām, izpētīta kvantu sarežģītība priekš funkcijām, kam ir 2 vērtības: 0 un 1 un punktu skaits, kurā funkcija pieņem vērtību 0 ir neliels. Priekš šādām funkcijām izdevies pilnībā raksturot to kvantu sarežģītību.

A. Ambainis piedalījies Springer-Verlag izdevniecības izdotās “Algoritmu Enciklopēdijas” sagatavošanās, kā kvantu algoritmu sadaļas redactors un 2 rakstu autors. Šajā enciklopēdijā apkopota informācija par aptuveni 400 svarīgākajiem algoritmiem no visām datorzinātņu nozarēm.

Projektā strādājošie doktoranti pētījuši kvantu klejošanu un meklēšanu (A. Rivošs), kvantu galīgos automātus (N. Nahimovs) un kvantu spēles (D. Kravčenko) un katrs no viņiem uzstājies vismaz vienā starptautiskā konferencē.

Projektā iegūtie rezultāti referēti vairākās konferencēs: SOFSEM’09 (Slovākija, A. Ambainis un A. Rivošs), STACS’09 (Francija, A. Ambainis), TQC’09 (Japāna, N. Nahimovs), CQIT’09 (ASV, A. Ambainis), CEQIP’09 (Čehija, A. Ambainis un N. Nahimovs), ICQO’09 (Lietuva, A. Ambainis), Estonian Theory Days (Igaunija, A. Ambainis un D. Kravčenko), WQACT’09 (Singapūra, A. Ambainis). A. Ambainis uzstājies kā lektors Lisabonas universitātes organizētā vasaras skolā par galīgajiem automātiem un ar tiem saistītām matemātikas problēmām.

Trīs doktoranti, kas darbojas projektā, piedalījušies Bristoles universitātes organizētajā vasaras skolā par varbūtiskām metodēm datorzinātnēs, kur ar lekcijām uzstājās pasaulē pazīstami zinātnieki. A. Rivošs šajā vasaras skolā prezentēja plakātu par savu pētījumu rezultātiem.

Publikācijas:
1. A. Ambainis: Probabilistic and team PFIN-type learning: General properties. Journal of Computer and System Sciences, 74(4): 457-489 (2008)
2. A. Ambainis, K. Iwama, M. Nakanishi, H. Nishimura, R. Raymond, S. Tani, S. Yamashita: Quantum Query Complexity of Boolean Functions with Small On-Sets. Proceedings of ISAAC’2008. Lecture Notes in Computer Science, 5369:907-918 (2008).
3. A. Ambainis: Quantum Algorithm for Element Distinctness. Encyclopedia of Algorithms, pp. 686-689, 2008.
4. A. Ambainis: Quantum Algorithm for Search on Grids. Encyclopedia of Algorithms, pp. 696-698, 2008.