Kvantu klejošana lieliem paātrinājumiem, un kvantu algoritmu ierobežojumi

Projekta nosaukums
Kvantu klejošana lieliem paātrinājumiem, un kvantu algoritmu ierobežojumi

Projekta līguma numurs
1.1.1.2/VIAA/1/16/113

Projekta sadarbības partneri
Centre for Quantum Technologies (CQT), National University of Singapore
(Tas ir viens partneris)

Projekta īstenošanas termiņš
01.11.2017. - 31.10.2020.

Projekta kopējais finansējums, LU daļa

Kopējas izmaksas: EUR 133,806.00

LU daļa: EUR 6,690.30

Projekta mērķis
Progress informāciju tehnoloģijās ir viens no lielākajiem 20. gadsimta beigu un 21. gadsimta sākuma sasniegumiem. Tomēr, mūsdienu tehnoloģijas ir sava vairākumā balstītas uz klasiskās, 19. gadsimta, fizikas likumiem, un lielā mērā ignorē 20. gadsimta teorētiskās fizikas sasniegumus, tai skaitā kvantu fiziku. Kaut gan 1990. gados tika parādīts, ka kvantu fizikai ir potenciāls lai sasniegtu tehnoloģijas, kuras nav sasniedzamas ar klasisko fiziku. Nozīmīgākie piemēri ir BB84 kvantu kriptogrāfijas shēma un Shor algoritms skaitļu sadalīšanai reizinātājos un diskrēta logaritma atrašanai. Otrais no šiem algoritmiem apdraud mūsdienu atklātās atslēgas kriptogrāfiju, jo tā gandrīz pilnībā ir balstīta uz šo problēmu sarežģītību klasiskiem datoriem. Šie sasniegumi izraisīja lielu interesi kvantu informācijas tehnoloģiju izveidei, kas šodien ir viens no lielākiem inženierzinātnes izaicinājumiem. Neskatoties uz šo interesi, tekošie kvantu skaitļošanas pielietojumi joprojām ir diezgan ierobežoti. Kaut gan esošo kvantu algoritmu skaits nemitīgi pieaug, ir grūti izdalīt kādu algoritmu, kas būtu salīdzināms ar Shor vai Grover algoritmiem.
Projekta pirmais mērķis ir izveidot jaunu, uz kvantu klejošanas balstītu, kvantu algoritmu izstrādes metodiķi, kas sasniedz būtiskus uzlabojumus, salīdzinot ar klasiskiem (ne-kvantu) algoritmiem.
Projekta otrais mērķis ir kvantu algoritmu ierobežojumu parādīšana.

Projekta rezultāti
1. Kvantu klejošana ar eksponenciāliem paātrinājumiem
2. Jaunie, uz kvantu klejošanas balstītie, algoritmi ar polinomiāliem paātrinājumiem.
3. Vaicājumu algoritmu de-kvantizācija
4. Kvantu apakšējo novērtējumu pierādīšanas tehnikas
Plānotais publikāciju apjoms
5 publikācijas Projekta laikā paveiktais  

Izstrādātie raksti un piedalīšanas konferencēs:

Pirmais pārskata periods 11.2017 - 01.2018 ·         Raksta Quantum Lower Bound for a Tripartite Version of the Hidden Shift Problem preprints izvietots arXiv repozitorijā. ◦     Pieejams: http://arxiv.org/abs/1712.10194 ·         Raksta  Adaptive Lower Bound for Testing Monotonicity on the Line preprints izvietots arXiv repozitorijā.  ◦     Pieejams: http://arxiv.org/abs/1801.08709 ·         Apvienotājās Igauņu-Latvijas teorijas dienās prezentēts referāts Provably secure key establishment against quantum adversaries. ◦     Atsauce: http://theorydays.cs.ut.ee/index.php/2017/Program ·         Prezentācija Quantum Adversary Bound seminārā Čehijas Zinātņu akadēmijas Matemātikas institūtā. ◦     Atsauce: http://calendar.math.cas.cz/content/quantum-adversary-bound Otrais pārskata periods 02.2017 - 04.2018 ·         Būtiski papildināta raksta Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems versija tika izvietota arXiv repozitorijā.  Rakstam ir jauns līdzautors Ansis Rosmanis. ◦     Pieejams: http://arxiv.org/abs/1712.10194 ·         Mobilitātes pasākumā ietvaros viens ar pusi mēnesis tika pavadīts iekš Centre for Quantum Technologies Singapūrā. ·         Konferencē Workshop on Quantum Algoritms and Complexity Theory 2018 tika prezentēts referāts Challenges for the quantum adversary bound. ◦     Atsauce: http://wqact.quantumlah.org/ Trešais pārskata periods 05.2017 – 07.2018 ·         Raksta  Adaptive Lower Bound for Testing Monotonicity on the Line jauna papildināta versija izvietots arXiv repozitorijā. ◦     Pieejams: http://arxiv.org/abs/1801.08709 ·         Raksts  Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems tika publicēts TQC 2018 konferences rakstu krājumos. ◦     Bibliogrāfiska informācija ir pieejama zēmāk. ·         Raksta Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems līdzautors Ansis Rosmanis prezentēja to TQC konferencē Sidnijā. ◦     Atsauce: https://www.tqc2018.org/accepted-talks Ceturtais pārskata periods 08.2017 - 10.2018 ·         Raksts  Adaptive Lower Bound for Testing Monotonicity on the Line tika publicēts RANDOM 2018 rakstu krājumos. ◦     Bibliogrāfiska informācija ir pieejama zēmāk. ·         Raksts Adaptive Lower Bound for Testing Monotonicity on the Line tika prezentēts RANDOM 2018 konferencē Prinstonē. ◦     Atsauce: http://cui.unige.ch/tcs/random-approx/2018/index.php?id=6  

Publicētie raksti

1.      Aleksandrs Belovs, Ansis Rosmanis. Quantum Lower Bounds for Tripartite Versions of the Hidden Shift and the Set Equality Problems. In proceedings of the 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018). Leibniz International Proceedings in Informatics (LIPIcs), volume 111, pages 3:1--3:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. DOI: 10.4230/LIPIcs.TQC.2018.3 Pilns raksta teksts brīvi pieejams: http://drops.dagstuhl.de/opus/volltexte/2018/9250 2.      Aleksandrs Belovs. Adaptive Lower Bound for Testing Monotonicity on the Line. In proceedings of Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018).  Leibniz International Proceedings in Informatics (LIPIcs), volume 116, pages 31:1–31:10. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2018. DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.31 Pilns raksta teksts brīvi pieejams: http://drops.dagstuhl.de/opus/volltexte/2018/9435/