Kvantu klejošana grafos

2013

Šajā darbā tiek pētīta meklēšana divdimensionālā režģi ar kvantu klejošanas palīdzību. Mums ir $N$ virsotnes, kas ir izkārtotas $\sqrt{N} \times \sqrt{N}$ režģī. Mēs meklējam uz šī režģa iezīmēto elementu ar kvantu klejošanas palīdzību. Šobrīd labākais algoritms atrod iezīmēto elementu pēc $O(\sqrt{N \log N})$ soļiem, un nav skaidrs, vai šis soļu skaits ir optimāls. Mēs mēģinam pieiet šai problēmai no divām pusēm --- pētot kvantu klejošanu asimetriskos (taisnstūra) režģos un klejošanu nejaušos grafos. Eksperimentu rezultātā tika atrasti trīs asimetrisko režģu gadījumi uz kuriem ir interesanti kvantu klejošanas rezultāti.