Verbeterde Quantum Query-complexiteit bij eenvoudiger invoer

Heruitgegeven door Plato

volgers: 0

Noel T. Anderson¹, Jay-U Chung¹, Shelby Kimmel¹, Da-Yeon Koh²en Xiaohan Ye^1,3

¹Middlebury College, Middlebury, VT, VS
²Williams College, Williamstown, MA, VS
³Brown University, Providence, RI, VS

Vind je dit artikel interessant of wil je het bespreken? Scite of laat een reactie achter op SciRate.

Abstract

Quantum span-programma-algoritmen voor functie-evaluatie hebben soms de complexiteit van de zoekopdrachten verminderd wanneer wordt beloofd dat de invoer een bepaalde structuur heeft. We ontwerpen een aangepast spanprogramma-algoritme om aan te tonen dat deze verbeteringen aanhouden, zelfs zonder voorafgaande belofte, en we breiden deze benadering uit naar het meer algemene probleem van staatsconversie. Als toepassing bewijzen we exponentiële en superpolynomiale kwantumvoordelen in de gemiddelde complexiteit van zoekopdrachten voor verschillende zoekproblemen, waarbij we Montanaro's Search with Advice generaliseren [Montanaro, TQC 2010].

Verbeterde Quantum Query-complexiteit bij eenvoudigere invoer PlatoBlockchain Data Intelligence. Verticaal zoeken. Ai.

Uitgelichte afbeelding: Beslisboom gebruikt om een van onze algoritmen te maken.

Populaire samenvatting

We verwachten dat kwantumalgoritmen, net als klassieke algoritmen, sneller zouden moeten werken met eenvoudiger invoer. Als u bijvoorbeeld naar een item in een ongeordende lijst zoekt en er veel kopieën van dat item zijn, verwachten we dat het kwantumalgoritme in deze situatie sneller zou moeten werken dan wanneer er maar één gemarkeerd item is, zelfs zonder dat u het weet. het aantal doelitems vooraf. Voor het zoekprobleem is het inderdaad bekend hoe je een dergelijk voordeel kunt behalen met eenvoudiger invoer. Het generaliseren van dit idee naar problemen die verder gaan dan zoeken is echter een uitdaging als er geen voor de hand liggende manier is om te markeren wanneer de berekening lang genoeg heeft geduurd. We passen verschillende populaire algoritmische raamwerken in het querymodel aan om vlaggen te creëren die ons waarschuwen of de berekening lang genoeg heeft geduurd, waardoor we het algoritme vroegtijdig kunnen beëindigen bij eenvoudiger invoer, zonder van tevoren te weten of de instantie gemakkelijk of moeilijk is. Als toepassing kunnen we, gegeven een verdeling van zowel gemakkelijke als harde invoer voor een probleem, de gemiddelde complexiteit van zoekopdrachten analyseren. We laten zien dat bepaalde distributies van invoer voor zoekproblemen grote gemiddelde kwantumqueryvoordelen opleveren ten opzichte van klassieke algoritmen.

► BibTeX-gegevens

@article{Anderson2024improvedquantum, doi = {10.22331/q-2024-04-08-1309}, url = {https://doi.org/10.22331/q-2024-04-08-1309}, title = {Verbeterde {Q}uantum {Q}uery {C}omplexiteit op {E}eenvoudigere {I}nputs}, auteur = {Anderson, Noel T. en Chung, Jay-U en Kimmel, Shelby en Koh, Da-Yeon en Ye, Xiaohan}, dagboek = {{Quantum}}, issn = {2521-327X}, uitgever = {{Verein zur F{“{o}}rderung des Open Access Publizierens in de Quantenwissenschaften}}, volume = {8}, pagina's = {1309}, maand = april, jaar = {2024} }

► Referenties

[1] Andris Ambainis en Ronald de Wolf. Complexiteit van kwantumquery's in gemiddelde gevallen. 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. Kwantumcomputer. Annual Reviews of Computational Physics VI, pagina's 259–346, 1999. doi:10.1142/9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

[3] Michel Boyer, Gilles Brassard, Peter Høyer en Alain Tapp. Strakke grenzen voor kwantumzoeken. 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] Alexander Belovs. Spanprogramma's voor functies met 1-certificaten van constante grootte: Uitgebreide samenvatting. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC '12, pagina's 77–84, 2012. doi:10.1145/2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985

[5] Gilles Brassard, Peter Høyer, Michele Mosca en Alain Tapp. Kwantumamplitudeversterking en -schatting. In Quantum computation and information, deel 305 van Contemp. Wiskunde, pagina's 53–74. Amer. Wiskunde. Soc., Providence, RI, 2002. doi:10.1090/conm/305/05215.
https: / / doi.org/ 10.1090 / conm / 305 / 05215

[6] Gilles Brassard, Peter Høyer en Alain Tapp. Kwantum tellen. In Automata, Languages and Programming, pagina's 820–831, 1998. doi:10.1007/BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

[7] Aleksandrs Belovs en Ben W. Reichardt. Spanprogramma's en kwantumalgoritmen voor st-connectiviteit en klauwdetectie. 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 en Ansis Rosmanis. Strakke kwantumondergrens voor geschatte tellingen met kwantumtoestanden. 2020. arXiv:2002.06879.
arXiv: 2002.06879

[9] Salman Beigi en Leila Taghavi. Kwantumversnelling gebaseerd op klassieke beslissingsbomen. 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 en Duyal Yolcu. Enkeltje naar Las Vegas en de kwantumtegenstander. 2023. arXiv:2301.02003.
arXiv: 2301.02003

[11] Richard. Kleef, Artur. Ekert, Chiara Macchiavello en Michele Mosca. Kwantumalgoritmen opnieuw bekeken. Proceedings van de Royal Society of London. Serie A: Wiskundige, natuurkundige en technische wetenschappen, 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 en Alvaro Piedrafita. Spanprogramma's en kwantumtijdcomplexiteit. Tijdens het 45e internationale symposium over wiskundige grondslagen van computerwetenschappen (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 en Aleksandrs Belovs. Tijd- en ruimte-efficiënte kwantumalgoritmen voor het detecteren van cycli en het testen van bipartiteit. Kwantuminformatie en berekeningen, 18(1-2):18–50, 2018.

[14] Kai DeLorenzo, Shelby Kimmel en R. Teal Witter. Toepassingen van het Quantum-algoritme voor st-Connectivity. In de 14e conferentie over de theorie van kwantumcomputers, communicatie en cryptografie (TQC 2019), pagina's 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 en Stefan Woerner. Iteratieve schatting van de kwantumamplitude. npj Quantum Information, 7(1):52, maart 2021. doi:10.1038/s41534-021-00379-1.
https://doi.org/10.1038/s41534-021-00379-1

[16] Lov K. Grover. Kwantummechanica helpt bij het zoeken naar een naald in een hooiberg. 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. Waarschijnlijkheidsverschillen voor sommen van begrensde willekeurige variabelen. 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 en Stacey Jeffery. Geschatte bereikprogramma's. 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 en Alvaro Piedrafita. Kwantumalgoritmen voor connectiviteit en aanverwante problemen. In het 26e jaarlijkse Europese symposium over algoritmen (ESA 2018), pagina's 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. Kwantummetingen en het Abelse stabilisatorprobleem. 1995. arXiv:quant-ph/9511026.
arXiv: quant-ph / 9511026

[21] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek en Mario Szegedy. Quantum Query Complexiteit van toestandsconversie. In 2011 IEEE 52e jaarlijkse symposium over de grondslagen van computerwetenschappen, pagina's 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 en Miklos Santha. Zoek 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. Kwantumonderzoek met advies. In Conference on Quantum Computation, Communication, and Cryptography, pagina's 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. Omspanprogramma's en complexiteit van kwantumquery's: de algemene grens van de tegenstander is bijna krap voor elke Booleaanse functie. 50e jaarlijkse IEEE-symposium over de grondslagen van computerwetenschappen, pagina's 544–551, 2009. doi:10.1109/FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

[25] Ben W. Reichardt. Reflecties voor kwantumquery-algoritmen. In Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pagina's 560-569. 2011. doi:10.1137/1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44

[26] Leila Taghavi. Vereenvoudigd kwantumalgoritme voor het orakelidentificatieprobleem. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/s42484-022-00080-2.
https://doi.org/10.1007/s42484-022-00080-2

Geciteerd door

[1] Stacey Jeffery, Shelby Kimmel en Alvaro Piedrafita, “Quantumalgoritme voor Path-Edge Sampling”, arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel en R. Teal Witter, "Robuuste en ruimte-efficiënte Dual Adversary Quantum Query-algoritmen", arXiv: 2306.15040, (2023).

Bovenstaande citaten zijn afkomstig van SAO / NASA ADS (laatst bijgewerkt met succes 2024-04-11 15:45:18). De lijst is mogelijk onvolledig omdat niet alle uitgevers geschikte en volledige citatiegegevens verstrekken.

On De door Crossref geciteerde service er zijn geen gegevens gevonden over het citeren van werken (laatste poging 2024-04-11 15:45:17).

Dit artikel is gepubliceerd in Quantum onder de Creative Commons Naamsvermelding 4.0 Internationaal (CC BY 4.0) licentie. Het auteursrecht blijft berusten bij de oorspronkelijke houders van auteursrechten, zoals de auteurs of hun instellingen.

Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
PlatoData.Network Verticale generatieve AI. Versterk jezelf. Toegang hier.
PlatoAiStream. Web3-intelligentie. Kennis versterkt. Toegang hier.
PlatoESG. carbon, CleanTech, Energie, Milieu, Zonne, Afvalbeheer. Toegang hier.
Plato Gezondheid. Intelligentie op het gebied van biotech en klinische proeven. Toegang hier.
Bron: https://quantum-journal.org/papers/q-2024-04-08-1309/

Tijdstempel: 8 april 2024

Tijdstempel: 6 november 2023

Heruitgegeven door Plato

Qubits verdelen in hypergraph-productcodes om logische poorten te implementeren

Achtergrondonafhankelijkheid en kwantumcausale structuur

Quantum Lazy-training

De complexiteit van kwantumondersteuningsvectormachines

Op afstand bestuurde verstrengelingsgeneratie

Thermische gebiedswet voor roosterbosonen

Waarneembaarheid van getrouwheidsverval met de Lyapunov-snelheid in kwantumsimulaties van enkele qubits

Effectief versus Floquet-theorie voor de Kerr parametrische oscillator

Een experiment om de discretie van de tijd te testen

Tweekleurige lusmodellen en hun verstrengeling over lange afstanden

Fouttolerante kwantumberekening van moleculaire waarneembaarheden

Over Ons

Verticaal zoeken & Ai

Platform

Blijf verbonden

Account