6533b827fe1ef96bd12869c6
RESEARCH PRODUCT
Laika-atmiņas kompromisi eksponenciālā laika kvantu algoritmiem
Dārta Ritumasubject
eksponenciāli algoritmikvantu algoritmikvantu atmiņas-laika kompromisidinamiskā programmēšanaDatorzinātneceļa atrašana hiperkubādescription
Arvien vairāk uzdevumiem tiek izgudroti kvantu algoritmi, kas ir pārāki pār labākajiem zināmajiem klasiskajiem algoritmiem. Bieži šiem algoritmiem nepieciešamais atmiņas daudzums ir liels, kas pašlaik mazās pieejamās kvantu atmiņas dēļ nav optimāli. Tādēļ ir būtiski apskatīt algoritmus, kuru atmiņas sarežģītība ir samazināta, palielinot laika sarežģītību, bet kas vēl aizvien sniedz uzlabojumu pār klasiskajiem algoritmiem. Viens no šādiem uzdevumiem ir algoritms ceļa atrašanai hiperkubā, kuram 2019. gadā atrasts kvantu algoritms ar laika un atmiņas sarežģītību $\widetilde O(1.817^n)$. Šis uzdevums ir interesants, jo ar tā palīdzību var modelēt daudzas NP-pilnas problēmas, šādi tās atrisinot ātrāk nekā klasiski $\widetilde O(2^n)$. Šajā darbā ir iegūti kvantu laika-atmiņas kompromisi, modificējot hiperkuba algoritma parametrus, kā arī tiek aplūkots zināms laika-atmiņas kompromisa algoritms \emph{pairwise-scheme} tādiem uzdevumiem, ko paātrina, izmantojot kvantu skaitļošanas metodes. Ir salīdzināts, kuros gadījumos ir labāk izmantot vienu vai otru algoritmu.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2021-01-01 |