Complexitate îmbunătățită a interogărilor cuantice pe intrări mai ușoare

Complexitate îmbunătățită a interogărilor cuantice pe intrări mai ușoare

Marca temporală: 8 aprilie 2024 11:29

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

1Middlebury College, Middlebury, VT, SUA
2Williams College, Williamstown, MA, SUA
3Universitatea Brown, Providence, RI, SUA

Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.

Abstract

Algoritmii programului cuantic span pentru evaluarea funcțiilor au uneori o complexitate redusă a interogărilor atunci când li se promite că intrarea are o anumită structură. Proiectăm un algoritm de program span modificat pentru a arăta că aceste îmbunătățiri persistă chiar și fără o promisiune în avans și extindem această abordare la problema mai generală a conversiei stărilor. Ca aplicație, demonstrăm avantaje cuantice exponențiale și superpolinomiale în complexitatea medie a interogării pentru mai multe probleme de căutare, generalizând Căutarea cu Sfaturi a lui Montanaro [Montanaro, TQC 2010].

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

Imagine prezentată: Arborele de decizie folosit pentru a crea unul dintre algoritmii noștri.

Rezumat popular

Ne așteptăm ca algoritmii cuantici, precum algoritmii clasici, să ruleze mai rapid pe intrări mai ușoare. De exemplu, dacă căutați un articol dintr-o listă neordonată și există multe copii ale acelui articol, ne-am aștepta ca algoritmul cuantic să ruleze mai repede în această situație comparativ cu atunci când există un singur element marcat, chiar și fără a ști numărul de articole țintă în avans. Într-adevăr, pentru problema căutării, se știe cum să obții un astfel de avantaj pe intrări mai ușoare. Cu toate acestea, generalizarea acestei idei la probleme dincolo de căutare este o provocare atunci când nu există o modalitate evidentă de a semnala atunci când calculul a rulat suficient de mult. Modificăm mai multe cadre algoritmice populare în modelul de interogare pentru a crea semnale care ne avertizează dacă calculul a rulat suficient de mult, permițându-ne să încheiem algoritmul devreme cu intrări mai ușoare, fără a ști dinainte dacă instanța este ușoară sau dificilă. Ca aplicație, având în vedere o distribuție a intrărilor atât ușoare, cât și dificile pentru o problemă, putem analiza complexitatea medie a interogărilor. Arătăm că anumite distribuții de intrări pentru problemele de căutare oferă avantaje mari de interogare cuantică medie față de algoritmii clasici.

► Date BibTeX

► Referințe

[1] Andris Ambainis și Ronald de Wolf. Complexitatea interogărilor cuantice medii. 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 Aharov. Calcul cuantic. Annual Reviews of Computational Physics VI, paginile 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer și Alain Tapp. Limite strânse ale căutării cuantice. 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] Aleksandrs Belovs. Programe span pentru funcții cu certificate 1 de dimensiune constantă: Rezumat extins. În Proceedings of the Fourty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, paginile 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca și Alain Tapp. Amplificarea și estimarea amplitudinii cuantice. În Quantum calcule and information, volumul 305 din Contemp. Math., paginile 53–74. Amer. Matematică. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305/05215

[6] Gilles Brassard, Peter Høyer și Alain Tapp. Numărarea cuantică. În Automate, Languages ​​and Programming, paginile 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs și Ben W. Reichardt. Programe span și algoritmi cuantici pentru conectivitate st și detectarea ghearelor. 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 și Ansis Romanis. Limită inferioară cuantică strânsă pentru numărare aproximativă cu stări cuantice. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi și Leila Taghavi. Accelerarea cuantică bazată pe arbori de decizie clasici. 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 și Duyal Yolcu. Bilet dus dus către Las Vegas și adversarul cuantic. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello și Michele Mosca. Algoritmi cuantici revăzuți. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 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 și Alvaro Piedrafita. Programe span și complexitatea timpului cuantic. În cel de-al 45-lea Simpozion Internațional despre Fundamentele Matematice ale Informaticii (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 și Aleksandrs Belovs. Algoritmi cuantici eficienti în timp și spațiu pentru detectarea ciclurilor și testarea bipartității. Quantum Information & Computation, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel și R. Teal Witter. Aplicații ale algoritmului cuantic pentru st-Conectivity. În a 14-a Conferință privind teoria calculului cuantic, comunicării și criptografiei (TQC 2019), paginile 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 și Stefan Woerner. Estimarea iterativă a amplitudinii cuantice. npj Quantum Information, 7(1):52, Mar 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

[16] Lov K. Grover. Mecanica cuantică ajută la căutarea unui ac într-un car de fân. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

[17] Wassily Hoeffding. Inegalități de probabilitate pentru sumele variabilelor aleatoare mărginite. Jurnalul Asociației Americane de Statistică, 58(301):13–30, 1963. doi:10.1080/​01621459.1963.10500830.
https: / / doi.org/ 10.1080 / 01621459.1963.10500830

[18] Tsuyoshi Ito și Stacey Jeffery. Programe de acoperire aproximativă. 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 și Alvaro Piedrafita. Algoritmi cuantici pentru conectivitate și probleme conexe. În cel de-al 26-lea Simpozion European anual privind algoritmi (ESA 2018), paginile 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2018.49

[20] Alexei Y. Kitaev. Măsurătorile cuantice și problema stabilizatorului abelian. 1995. arXiv:quant-ph/​9511026.
arXiv: Quant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek și Mario Szegedy. Interogare cuantică Complexitatea conversiei stărilor. În 2011 IEEE 52th Annual Symposium on Foundations of Computer Science, paginile 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 și Miklos Santha. Căutați prin Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Căutare cuantică cu sfaturi. În Conferința privind calculul cuantic, comunicarea și criptografia, paginile 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. Programe span și complexitatea interogărilor cuantice: limita generală a adversarului este aproape strânsă pentru fiecare funcție booleană. 50th Annual IEEE Symposium on Foundations of Computer Science, paginile 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Reflecții pentru algoritmi de interogare cuantică. În Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pages 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Algoritm cuantic simplificat pentru problema identificării oracolului. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Citat de

[1] Stacey Jeffery, Shelby Kimmel și Alvaro Piedrafita, „Quantum Algorithm for Path-Edge Sampling”, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel și R. Teal Witter, „Algoritmi de interogare cuantică cu dublu adversar robust și eficient în spațiu”, arXiv: 2306.15040, (2023).

Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2024-04-11 15:45:18). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.

On Serviciul citat de Crossref nu s-au găsit date despre citarea lucrărilor (ultima încercare 2024-04-11 15:45:17).

Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.

Timestamp-ul:

Mai mult de la Jurnalul cuantic