Förbättrad Quantum Query-komplexitet på enklare indata

Förbättrad Quantum Query-komplexitet på enklare indata

Tidsstämpel: 8 april 2024 11:29

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

1Middlebury College, Middlebury, VT, USA
2Williams College, Williamstown, MA, USA
3Brown University, Providence, RI, USA

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Quantum span programalgoritmer för funktionsutvärdering har ibland minskad frågekomplexitet när man lovar att indata har en viss struktur. Vi designar en modifierad spanprogramalgoritm för att visa att dessa förbättringar kvarstår även utan ett löfte i förväg, och vi utökar detta tillvägagångssätt till det mer allmänna problemet med tillståndsomvandling. Som en applikation bevisar vi exponentiella och superpolynomiska kvantfördelar i genomsnittlig frågekomplexitet för flera sökproblem, och generaliserar Montanaros Search with Advice [Montanaro, TQC 2010].

Förbättrad Quantum Query-komplexitet på enklare indata PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Utvald bild: Beslutsträd som används för att skapa en av våra algoritmer.

Populär sammanfattning

Vi förväntar oss att kvantalgoritmer, precis som klassiska algoritmer, ska köras snabbare på enklare ingångar. Till exempel, om du söker efter ett objekt i en oordnad lista, och det finns många kopior av det objektet, förväntar vi oss att kvantalgoritmen ska köras snabbare i den här situationen jämfört med när om det bara finns en markerad artikel, även utan att veta antalet målobjekt i förväg. För problemet med sökning är det faktiskt känt hur man får en sådan fördel på enklare inmatningar. Att generalisera denna idé till problem bortom sökning är dock utmanande när det inte finns ett uppenbart sätt att flagga när beräkningen har pågått tillräckligt länge. Vi modifierar flera populära algoritmiska ramverk i frågemodellen för att skapa flaggor som varnar oss om huruvida beräkningen har körts tillräckligt länge, vilket gör att vi kan avsluta algoritmen tidigt vid enklare inmatningar, utan att i förväg veta om instansen är lätt eller svår. Som en applikation, med en fördelning av både enkla och hårda indata till ett problem, kan vi analysera den genomsnittliga frågekomplexiteten. Vi visar att vissa distributioner av indata till sökproblem ger stora genomsnittliga kvantfrågefördelar jämfört med klassiska algoritmer.

► BibTeX-data

► Referenser

[1] Andris Ambainis och Ronald de Wolf. Genomsnittlig kvantfrågekomplexitet. 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. Kvantberäkning. Annual Reviews of Computational Physics VI, sidorna 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer och Alain Tapp. Snäva gränser för kvantsökning. 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. Spänn program för funktioner med konstantstora 1-certifikat: Utökat abstrakt. I Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, sidorna 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca och Alain Tapp. Kvantamplitudförstärkning och uppskattning. I Quantum computation and information, volym 305 av Contemp. Math., sidorna 53–74. Amer. Matematik. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305 / 05215

[6] Gilles Brassard, Peter Høyer och Alain Tapp. Kvanträkning. I Automata, Languages ​​and Programming, sidorna 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs och Ben W. Reichardt. Span-program och kvantalgoritmer för st-anslutning och klodetektering. 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 och Ansis Rosmanis. Tight nedre kvantgräns för ungefärlig räkning med kvanttillstånd. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi och Leila Taghavi. Quantum speedup baserat på klassiska beslutsträd. 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 och Duyal Yolcu. Enkelbiljett till las vegas och kvantmotståndaren. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Cleve, Artur. Ekert, Chiara Macchiavello och Michele Mosca. Kvantalgoritmer återbesöks. Proceedings of the Royal Society of London. Serie 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 och Alvaro Piedrafita. Spanprogram och kvanttidskomplexitet. I 45:e internationella symposium om matematiska grunder för datavetenskap (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 och Aleksandrs Belovs. Tids- och rymdeffektiva kvantalgoritmer för att detektera cykler och testa tvådeladhet. Quantum Information & Computation, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel och R. Teal Witter. Tillämpningar av Quantum Algorithm för st-Connectivity. I 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), sidorna 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 och Stefan Woerner. Iterativ kvantamplituduppskattning. 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. Kvantmekanik hjälper till att leta efter en nål i en höstack. 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. Sannolikhetsolikheter för summor av avgränsade stokastiska variabler. 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 och Stacey Jeffery. Ungefärliga spanprogram. 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 och Alvaro Piedrafita. Kvantalgoritmer för anslutning och relaterade problem. I 26th Annual European Symposium on Algorithms (ESA 2018), sidorna 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. Kvantmätningar och Abelian Stabilizer Problem. 1995. arXiv:quant-ph/​9511026.
arXiv: kvant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek och Mario Szegedy. Quantum Query Complexity of State Conversion. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, sidorna 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 och Miklos Santha. Sök via Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854

[23] Ashley Montanaro. Kvantsökning med råd. I konferens om kvantberäkning, kommunikation och kryptografi, sidorna 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. Spännande program och kvantfrågekomplexitet: Den allmänna motståndargränsen är nästan snäv för varje boolesk funktion. 50:e årliga IEEE Symposium on Foundations of Computer Science, sidorna 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Reflektioner för kvantfrågealgoritmer. I Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, sidorna 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Förenklad kvantalgoritm för orakelidentifieringsproblemet. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Citerad av

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

[2] Michael Czekanski, Shelby Kimmel och R. Teal Witter, "Robust and Space-Efficient Dual Adversary Quantum Query Algorithms", arXiv: 2306.15040, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-04-11 15:45:18). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2024-04-11 15:45:17).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal