Izboljšana kompleksnost kvantnih poizvedb pri lažjih vnosih

Izboljšana kompleksnost kvantnih poizvedb pri lažjih vnosih

Časovni žig: 8. april 2024 11

Noel T. Anderson1, Jay-U Chung1, Shelby Kimmel1, Da-Yeon Koh2in Xiaohan Ye1,3

1Middlebury College, Middlebury, VT, ZDA
2Williams College, Williamstown, MA, ZDA
3Univerza Brown, Providence, RI, ZDA

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Programski algoritmi kvantnega razpona za ovrednotenje funkcije včasih zmanjšajo kompleksnost poizvedbe, ko je obljubljeno, da ima vhod določeno strukturo. Oblikujemo spremenjen algoritem programa za razpon, da pokažemo, da te izboljšave trajajo tudi brez obljube vnaprej, in ta pristop razširimo na splošnejši problem pretvorbe stanja. Kot aplikacija dokazujemo eksponentne in superpolinomske kvantne prednosti v povprečni kompleksnosti poizvedbe za več iskalnih težav, s čimer posplošujemo Montanarovo iskanje z nasveti [Montanaro, TQC 2010].

Improved Quantum Query Complexity on Easier Inputs PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Predstavljena slika: Odločitveno drevo, uporabljeno za ustvarjanje enega od naših algoritmov.

Priljubljen povzetek

Pričakujemo, da bi kvantni algoritmi, tako kot klasični algoritmi, delovali hitreje pri lažjih vnosih. Na primer, če iščete element na neurejenem seznamu in obstaja veliko kopij tega elementa, bi pričakovali, da bi moral kvantni algoritem v tej situaciji delovati hitreje v primerjavi s stanjem, ko je označen samo en element, čeprav ne veste število ciljnih elementov pred časom. Za problem iskanja se namreč ve, kako dobiti takšno prednost pri lažjih vnosih. Vendar pa je posploševanje te ideje na težave zunaj iskanja zahtevno, če ni očitnega načina za označitev, ko je izračun potekal dovolj dolgo. V modelu poizvedbe spremenimo več priljubljenih algoritemskih okvirov, da ustvarimo zastavice, ki nas opozorijo, ali je izračun potekal dovolj dolgo, kar nam omogoča, da algoritem končamo zgodaj pri lažjih vnosih, ne da bi vnaprej vedeli, ali je primer enostaven ali težak. Kot aplikacija lahko glede na distribucijo preprostih in težkih vnosov v problem analiziramo povprečno kompleksnost poizvedbe. Pokažemo, da določene porazdelitve vnosov v iskalne probleme prinašajo velike povprečne prednosti kvantne poizvedbe pred klasičnimi algoritmi.

► BibTeX podatki

► Reference

[1] Andris Ambainis in Ronald de Wolf. Kompleksnost kvantne poizvedbe v povprečnem primeru. Journal of Physics A: Mathematical and General, 34(35):6741, 2001. doi:10.1088/​0305-4470/​34/​35/​302.
https:/​/​doi.org/​10.1088/​0305-4470/​34/​35/​302

[2] Dorit Aharonov. Kvantno računanje. Annual Reviews of Computational Physics VI, strani 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer in Alain Tapp. Tesne meje kvantnega iskanja. Fortschritte der Physik, 46(4-5):493–505, 1998. doi:10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2 -P.
<a href="https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P”>https:/​/​doi.org/​10.1002/​(SICI)1521-3978(199806)46:4/​5<493::AID-PROP493>3.0.CO;2-P

[4] Aleksandr Belovs. Razponski programi za funkcije z 1-certifikati konstantne velikosti: razširjen povzetek. V zborniku štiriinštiridesetega letnega simpozija ACM o teoriji računalništva, STOC '12, strani 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca in Alain Tapp. Ojačitev in ocena kvantne amplitude. V Kvantnem računanju in informacijah, zvezek 305 Contemp. Math., strani 53–74. Amer. matematika Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Høyer in Alain Tapp. Kvantno štetje. V Avtomati, jeziki in programiranje, strani 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs in Ben W. Reichardt. Razponski programi in kvantni algoritmi za st-povezljivost in zaznavanje krempljev. Lecture Notes in Computer Science, 7501 LNCS:193–204, 2012. doi:10.1007/​978-3-642-33090-2_18.
https:/​/​doi.org/​10.1007/​978-3-642-33090-2_18

[8] Aleksandrs Belovs in Ansis Rosmanis. Tesna kvantna spodnja meja za približno štetje s kvantnimi stanji. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi in Leila Taghavi. Kvantna pospešitev na podlagi klasičnih odločitvenih dreves. Quantum, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

[10] Aleksandrs Belovs in Duyal Yolcu. Enosmerna vozovnica za las vegas in kvantnega nasprotnika. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello in Michele Mosca. Ponovni pregled kvantnih algoritmov. Zbornik Kraljeve družbe v Londonu. Serija A: Matematične, fizikalne in inženirske vede, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

[12] Arjan Cornelissen, Stacey Jeffery, Maris Ozols in Alvaro Piedrafita. Razponski programi in kvantna časovna kompleksnost. Na 45. mednarodnem simpoziju o matematičnih osnovah računalništva (MFCS 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. doi:10.4230/​LIPIcs.MFCS.2020.26.
https: / / doi.org/ 10.4230 / LIPIcs.MFCS.2020.26

[13] Chris Cade, Ashley Montanaro in Aleksandrs Belovs. Časovno in prostorsko učinkoviti kvantni algoritmi za odkrivanje ciklov in testiranje bipartitnosti. Kvantne informacije in računanje, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel in R. Teal Witter. Uporaba kvantnega algoritma za st-povezljivost. Na 14. konferenci o teoriji kvantnega računalništva, komunikacije in kriptografije (TQC 2019), strani 6:1–6:14, 2019. doi:10.4230/​LIPIcs.TQC.2019.6.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2019.6

[15] Dmitry Grinko, Julien Gacon, Christa Zoufal in Stefan Woerner. Iterativna ocena kvantne amplitude. npj Kvantne informacije, 7(1):52, marec 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Lov K. Grover. Kvantna mehanika pomaga pri iskanju igle v kupu sena. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

[17] Vasilij Hoeffding. Verjetnostne neenakosti za vsote omejenih naključnih spremenljivk. Journal of the American Statistical Association, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Tsuyoshi Ito in Stacey Jeffery. Programi približnega razpona. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

[19] Michael Jarret, Stacey Jeffery, Shelby Kimmel in Alvaro Piedrafita. Kvantni algoritmi za povezljivost in sorodne težave. Na 26. letnem evropskem simpoziju o algoritmih (ESA 2018), strani 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] Aleksej Y. Kitaev. Kvantne meritve in problem Abelovega stabilizatorja. 1995. arXiv:quant-ph/9511026.
arXiv: kvant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek in Mario Szegedy. Kompleksnost kvantne poizvedbe pretvorbe stanja. Leta 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, strani 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

[22] Frédéric Magniez, Ashwin Nayak, Jérémie Roland in Miklos Santha. Išči preko Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Kvantno iskanje z nasveti. Na konferenci o kvantnem računanju, komunikaciji in kriptografiji, strani 77–93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

[24] Ben W. Reichardt. Razponski programi in kompleksnost kvantne poizvedbe: splošna nasprotna meja je skoraj tesna za vsako logično funkcijo. 50. letni simpozij IEEE o temeljih računalništva, strani 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Odsevi za algoritme kvantnih poizvedb. V zborniku letnega simpozija ACM-SIAM o diskretnih algoritmih 2011, zbornik, strani 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Poenostavljen kvantni algoritem za problem identifikacije oraklja. Kvantna strojna inteligenca, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Navedel

[1] Stacey Jeffery, Shelby Kimmel in Alvaro Piedrafita, "Kvantni algoritem za vzorčenje na robu poti", arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel in R. Teal Witter, “Robust and space-Efficient Dual Adversary Quantum Query Algorithms”, arXiv: 2306.15040, (2023).

Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2024-04-11 15:45:18). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.

On Crossref je navedel storitev ni bilo najdenih podatkov o navajanju del (zadnji poskus 2024-04-11 15:45:17).

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal