Students and staffPhilanthropyMedia

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.2018 - 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.2018 – 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.2018 – 10.2018

  • Projekta ietvaros tika strādāts pie gandrīz visur pareizas vaicājumu algoritmu dekvantizācijas, pie ieejas orākulu ekvivalences pierādīšanas īpašību testēšanas problēmām, un pie kvantu algoritmiem un apakšējiem novērtējumiem Element Distinctness problēmas binārai versijai.
  • Raksts  Adaptive Lower Bound for Testing Monotonicity on the Line tika publicēts RANDOM 2018 rakstu krājumos.

 - Bibliogrāfiska informācija ir pieejama zemā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

  • Piedalīšanas ar prezentāciju Proving Quantum Lower Bounds for Hard-To-Distinguish Distributions Quantalgo konferencē Parīzē

 - Atsauce: http://quantalgo.ulb.be/workshop/program/

  • Piedalīšanas ar prezentāciju Adaptive Lower Bound for Testing Monotonicity on the Line Apvienotās Igaunijas-Latvijas teorijas dienas Rīgā.

 - Atsauce: http://home.lu.lv/~df/tdays-2018/ajakava.html

Piektais pārskata periods 11.2018-01.2019.

  •  Projekta ietvaros notika darbs pie sekojošiem uzdevumiem:
  • Kvantu algoritmu izveide un apakšējo novērtējumu pierādīšana divu varbūtisko sadalījumu atšķiršanai.
  • Kvantu algoritmu izveide huntu testēšanai sadalījuma-brīvā un tolerantā modeļos.
  • Izliektības testēšanas problēma, gan no algoritmu, gan no apakšējo novērtējumu perspektīvas.
  • Triju-nedēļu gara zinātniska vizīte Kvantu skaitļošanas institūtā Waterloo Universitātē, Kanādā. Tajā skaitā, uzstāšanas ar stundas-garu referātu Quantum Algorithms for Classical Probability Distributions.

- Atsauce: uwaterloo.ca/institute-for-quantum-computing/events/quantum-algorithms-classical-probability-distributions

Sestais pārskata periods 02.2019 – 04.2019

  • Projekta ietvaros tika akceptēti divi raksti
  • Quantum Algorithm for Distribution-Free Junta Testing, kas tika akceptēts CSR 2019 konferencē.
  • Quantum Dual Adversary for Hidden Subgroups and Beyond, kas tika akceptēts UCNC 2019 konferencē.
  • Projekta ietvaros tika izstrādāts raksts “Quantum Algorithms for Classical Probability Distributions”, kas ir brīvi pieejams https://arxiv.org/abs/1904.02192
  • Tika veikts darbs pie algoritmiem un apakšējiem novērtējumiem izliektības testēšanas problēmai, kā arī tika pētīti apakšējie novērtējumi kvantu skaitļošanas problēmai, kad ir doti gan pieeja individuālam virknes bitiem, gan superpozīcijai pa visiem bitiem.
 

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 tekst 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 tekst brīvi pieejams: http://drops.dagstuhl.de/opus/volltexte/2018/9435/

 

Septītais pārskata periods 05.2019–07.2019

  • Piedalīšanas UCNC 2019 konferencē ar prezentāciju Quantum Dual Adversary for Hidden Subgroups and Beyond.  Atsauce: http://www.ucnc2019.uec.ac.jp/ .
  • Raksts “Quantum Algorithms for Classical Probability Distributions”, kas ir brīvi pieejams https://arxiv.org/abs/1904.02192, tika akceptēts ESA 2019 konferencē.
  • Projekta ietvaros tika izstrādāti divi raksti, abi kopā ar Eric Blais un Abhinav Bommireddi
    • Testing convexity of functions over finite domains
    • Minimizing discrete convex functions over two-dimensional domains

            Rakstu teksti parādīsies brīvajā pieeja vēlāk, pēc papildus darba pie tiem.

  • Tika pabeigts darbs pie algoritmiem un apakšējiem novērtējumiem izliektības testēšanas problēmai, kā arī paveikts darbs pie izliekto funkciju minimizācijas. Tika turpināts darbs pie apakšējiem novērtējumiem kvantu skaitļošanas problēmai, kad ir dota gan pieeja individuālam virknes bitiem, gan superpozīcijai pa visiem bitiem.
  1. 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

  1. 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/

3. Aleksandrs Belovs. Quantum Dual Adversary for Hidden Subgroups and Beyond.  In proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019). Lecture Notes in Computer Science (LNCS), volume 11493, pages 30-36. Springer, 2019.

DOI: 10.1007/978-3-030-19311-9_4

4. Aleksandrs Belovs. Quantum Algorithm for Distribution-Free Junta Testing. In proceedings of International Computer Science Symposium in Russia (CSR 2019).  Lecture Notes in Computer Science (LNCS), volume 11532, pages 50-59. Springer, 2019.

DOI: 10.1007/978-3-030-19955-5_5

Raksta preprints ir brīvi pieejams: https://arxiv.org/abs/1903.08462.

Astotais pārskata periods 08.2019 – 10.2019

  • Piedalīšanās ESA 2019 konferencē, kas ir daļa no ALGO 2019 simpozija (https://algo2019.ak.in.tum.de), Minhenē ar prezentāciju “Quantum Algorithms for Classical Probability Distributions”.
  • Piedalīšanās Apvienotajās Igauņu-Latvijas teorijas dienās (https://theorydays.cs.ut.ee/) ar prezentāciju “Some Results in Property Testing”.
  • Kopā ar University of Waterloo pētniekiem Eric Blais un Abhinav Bommireddi iepriekš izstrādāts raksts "Testing convexity of functions over finite domains" tika pieņemts SODA 2020 konferencē ar publicētiem rakstu krājumiem. Raksta gala versijas sagatavošana.
  • Tika turpināts darbs pie kvantu vaicājumu algoritmu de-kvantizācijas, kas ir gandrīz visur pareiza. Tika analizētas vairākas tehnikas koncentrāciju rezultātu pierādīšanai ar mērķi pielietot tos šai problēmai.
  • Kopā ar Ansi Rosmani no Nagojas universitātes tika turpināts darbs pie apakšējiem novērtējumiem kvantu skaitļošanai problēmai, kad ir dota gan pieeja membership orākulam, gan superpozīcijai pa kopas elementiem. Šī problēma tika pilnībā atrisināta, turklāt analizējot arī citus resursus, kas ir pieejami kvantu algoritmam: orākuli, kas sagatavo superpozīciju pa kopas elementiem un orākuli, kas atspoguļo pret šo stāvokli.

Projekta laikā 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: drops.dagstuhl.de/opus/volltexte/2018/9250

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1712.10194

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: drops.dagstuhl.de/opus/volltexte/2018/9435/

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1801.08709

3. Aleksandrs Belovs. Quantum Dual Adversary for Hidden Subgroups and Beyond. In proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019). Lecture Notes in Computer Science (LNCS), volume 11493, pages 30-36. Springer, 2019.

DOI: 10.1007/978-3-030-19311-9_4

4. Aleksandrs Belovs. Quantum Algorithm for Distribution-Free Junta Testing. In proceedings of International Computer Science Symposium in Russia (CSR 2019). Lecture Notes in Computer Science (LNCS), volume 11532, pages 50-59. Springer, 2019.

DOI: 10.1007/978-3-030-19955-5_5

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1903.08462

5. Aleksandrs Belovs. Quantum Algorithms for Classical Probability Distributions.

In proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), volume 144, pages 16:1--16:11. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

DOI: 10.4230/LIPIcs.ESA.2019.16

Pilns raksta teksts brīvi pieejams: drops.dagstuhl.de/opus/volltexte/2019/11137

Raksta preprints ir brīvi pieejams: https://arxiv.org/abs/1904.02192

 

Devītais pārskata periods 11.2019 – 01.2020

  • Tika atsākts darbs pie laika-efektīva algoritma izveidošanas Hidden Subgroup Problēmai, izmantojot kvantu klejošanu, un balstoties uz iepriekš šajā aktivitātē izstrādāto duālo adversary atrisinājumu šai problēmai.
  • Kopā ar University of Waterloo pētniekiem Eric Blais un Abhinav Bommireddi iepriekš izstrādāts raksts "Testing convexity of functions over finite domains" tika publicēts konferences SODA 2020 rakstu krājumos. Līdzautors Eric Blais prezentēja rakstu konferencē.
  •  Kopā ar Srinivasan Arunachalam, Andrew M. Childs, Robin Kothari, Ansi Rosmani, un Ronald de Wolf tika izstrādāts raksts Quantum Coupon Collection, kas aplūko kvantu skaitļošanas versiju klasiskai Kuponu Kolekcionāra problēmai.
  • Kopā ar Ansi Rosmani tika turpināts darbs pie apakšējiem novērtējumiem kvantu skaitļošanai problēmai, kad ir doti gan pieeja membership orākulam, gan superpozīcijai pa kopas elementiem. Rezultāti tika stiprināti, pieliekot arī ieejas stāvokļa kopijas.
 

Projekta laikā 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: drops.dagstuhl.de/opus/volltexte/2018/9250

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1712.10194

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: drops.dagstuhl.de/opus/volltexte/2018/9435/

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1801.08709

3. Aleksandrs Belovs. Quantum Dual Adversary for Hidden Subgroups and Beyond. In proceedings of the 18th International Conference on Unconventional Computation and Natural Computation (UCNC 2019). Lecture Notes in Computer Science (LNCS), volume 11493, pages 30-36. Springer, 2019.

DOI: 10.1007/978-3-030-19311-9_4

4. Aleksandrs Belovs. Quantum Algorithm for Distribution-Free Junta Testing. In proceedings of International Computer Science Symposium in Russia (CSR 2019). Lecture Notes in Computer Science (LNCS), volume 11532, pages 50-59. Springer, 2019.

DOI: 10.1007/978-3-030-19955-5_5

Raksta pre-prints ir brīvi pieejams: arxiv.org/abs/1903.08462

5. Aleksandrs Belovs. Quantum Algorithms for Classical Probability Distributions.

In proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), volume 144, pages 16:1--16:11. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.

DOI: 10.4230/LIPIcs.ESA.2019.16

Pilns raksta teksts brīvi pieejams: drops.dagstuhl.de/opus/volltexte/2019/11137

Raksta preprints ir brīvi pieejams: arxiv.org/abs/1904.02192 .

6. Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi. Testing convexity of functions over finite domains.

In Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms (SODA 2020), pages 2030-2045, 2020. DOI: 10.1137/1.9781611975994.125

Pilns raksta teksts brīvi pieejams: epubs.siam.org/doi/10.1137/1.9781611975994.125

Raksta preprints ir brīvi pieejams: https://arxiv.org/abs/1908.02525.

 

Desmitais pārskata periods 02.2020 – 04.2020

  • Kopā ar Arturo Castellanos , François Le Gall , Guillaume Malod un Alexander A. Sherstov raksts “Quantum Communication Complexity of Distribution Testing” tika pastiprināts ar jauniem rezultātiem, tajā skaitā ar apakšējo novērtējuma pieradījumu. Raksts tika iesniegts COCOON 2020 konferencē ( http://cocoon-conference.org/2020/index.html ) ar publicētiem rakstu krājumiem.
  • Kopā ar Srinivasan Arunachalam, Andrew M. Childs, Robin Kothari, Ansi Rosmani, un Ronald de Wolf tika pabeigts raksts Quantum Coupon Collection, kas aplūko kvantu skaitļošanas versiju klasiskai Kuponu Kolekcionāra problēmai.  Raksts tika pieņemts TQC 2020 konferencē ( http://tqc2020.lu.lv/program/accepted-papers/ ) un tiks publicēts konferences rakstu krājumos. Raksta pre-prints ir brīvi pieejams:  https://arxiv.org/abs/2002.07688 .
  • Kopā ar Ansi Rosmani tika turpināts darbs pie apakšējiem novērtējumiem kvantu skaitļošanai problēmai, kad ir doti gan pieeja membership orākulam, gan superpozīcijai pa kopas elementiem. Šī problēma tika pilnībā atrisināta, turklāt analizējot arī citus resursus, kas ir pieejami kvantu algoritmam: orākuli, kas sagatavo superpozīciju pa kopas elementiem un orākuli, kas atspoguļo pret šo stāvokli. Raksta rezultāti tika pastiprināti, pieliekot arī ieejas stāvokļa kopijas.  Rezultāti tika apkopoti rakstā "Tight Quantum Lower Bound for Approximate Counting with Quantum States". Pirmā raksta versija tika akceptēta TQC 2020 konferencē ( http://tqc2020.lu.lv/program/accepted-papers/) kā runa, un otrā raksta versija tika iesūtīta FOCS 2020 konferencē ar publicētiem rakstu krājumiem. Otrā raksta versija tika pastiprināta ar jauno rezultātu par Find-Two problēmu.  Raksta pre-prints ir brīvi pieejams:  https://arxiv.org/pdf/2002.06879 .
  • Kopā ar Troy Lee tika izstrādāts raksts "The quantum query complexity of composition with a relation", kas atbilst Deliverable 4.3, kā rezultāts adversary apakšējiem novērtējumiem priekš relācijām. Plānos ir pastiprināt šo rakstu tālāk un iesniegt publicēšanai.  Raksts ir pieejams  https://arxiv.org/abs/2004.06439

Vienpadsmitais pārskata periods 05.2020 – 07.2020

  • Kopā ar Ansi Rosmani izstrādāts raksts "Tight Quantum Lower Bound for Approximate Counting with Quantum States" tika prezentēts TQC 2020 konferencē.
  • Kopā ar Srinivasan Arunachalam, Andrew M. Childs, Robin Kothari, Ansi Rosmani, un Ronald de Wolf izstrādāts raksts Quantum Coupon Collector, tika publicēts TQC 2020 konferences rakstu krājumos. Rakstu prezentēja līdzautors Ronald de Wolf.
  • Kopā ar Arturo Castellanos, François Le Gall, Guillaume Malod un Alexander A. Sherstov raksts “Quantum Communication Complexity of Distribution Testing”, kas netika pieņemts COCOON 2020 konferencē, tika uzlabots un aizsūtīts uz ISAAC 2020 konferenci (https://algo2020.comp.polyu.edu.hk/isaac-cfp.html) ar publicētiem rakstu krājumiem. Raksts tika ielikts arXiv preprintu serverī zem adreses arxiv.org/abs/2006.14870.
  • Tika veikts darbs pie raksta Minimizing discrete convex functions over two-dimensional domains. Tika analizētas iespējas reducēt minimuma atrašanas sarežģītību līdz logaritmiskai.
  • Kopā ar Troy Lee tika turpināts darbs pie raksta "The quantum query complexity of composition with a relation". Mērķis ir izveidot līdzīgu rezultātu pēc iespējas vispārīgākajā formā, izmantojot vispārīgus kvantu orākulus.

Divpadsmitais pārskata periods 08.2020 – 10.2020

  • Tika izmēģināta jauna pieeja, saistīta ar šīs aktivitātes jautājumiem. Tika analizētas saistības starp slēptas apakšgrupas problēmu dihedrālaja grupā (vispārīgāk, paslēptas nobīdes problēmas) saistība ar NP-pilnājiem uzdevumiem, mēģinot identificēt grūtības, kas rodas šo uzdevumu efektīvai implementācijai.
  • Kopā ar Eric Blais un Abhinav Bommireddi tika turpināts darbs pie raksta Minimizing discrete convex functions over two-dimensional domains. Tika atrasts veids reducēt algoritma sarežģītību līdz polilogaritmiskai. Tika strādāts pie algoritma vispārināšanai vairākās dimensijās.
  • Kopā ar Ansi Rosmani tika veikts darbs pie raksta "Tight Quantum Lower Bound for Approximate Counting with Quantum States" sagatavošanai žurnāla publikācijai, kā arī tika turpināts darbs pie kvantu apakšējiem novērtējumiem 3-distinctness un monotonitātes testēšanas problēmām.
  • Kā publicitātes pasākums tika nolasīta lekcija skolniekiem LU Izcilības Skolas ietvaros.  Nosaukums: “Kvantu algoritmu mūsu dzīve”.  Pieejama: https://www.youtube.com/watch?v=a7Ddz64_XFA
Last changed