6533b85dfe1ef96bd12be239
RESEARCH PRODUCT
Kvantu meklēšanas stacionāro stāvokļu apraksts
Dārta Ritumasubject
kvantu meklēšanaDatorzinātnestacionārie stāvokļiGrovera transformācijagrafidescription
Kvantu meklēšana ir uz klasiskās gadījumklejošanas balstīts meklēšanas algoritms, kur strukturētā datubāzē -- grafā meklē iezīmētu virsotni. Ir zināms, ka daudzos gadījumos kvantu klejošana var atrast iezīmēto virsotni laikā $O(\sqrt{n})$, kamēr klasiski nepieciešams $\Omega(n)$ laiks, kur $n$ ir grafa virsotņu skaits. Ja klejošanas sākumstāvoklis ir aptuveni vienāds ar stacionāro stāvokli, tad kvantu algoritms nesniedz priekšrocību pāri klasiskajam. Līdz ar to tiek pētīts, kad eksistē stacionārie stāvokļi, atkarībā no grafa un iezīmētām virsotnēm. Šajā darbā tiek pētīta kvantu meklēšana ar Grovera monētu, un tās stacionārie stāvokļi -- tādi gadījumi, kad klejošana neietekmē stāvokli visas savas darbības laikā. Ir zināms risinājums stacionāro stāvokļu eksistencei situācijā, kad marķētās virsotnes veido vienu sakarīgu komponenti un nemarķētās virsotnes veido citu sakarīgu komponenti. Šajā darbā esošie rezultāti vispārināti līdz stāvokļu eksistencei patvaļīgā grafā.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-01-01 |