Complessità delle query quantistiche migliorata su input più semplici

Complessità delle query quantistiche migliorata su input più semplici

Timestamp: 8 aprile 2024 11:29

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

1Middlebury College, Middlebury, Vermont, Stati Uniti
2Williams College, Williamstown, MA, Stati Uniti
3Brown University, Providence, RI, Stati Uniti

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Gli algoritmi del programma Quantum Span per la valutazione delle funzioni a volte hanno ridotto la complessità delle query quando viene promesso che l'input ha una determinata struttura. Progettiamo un algoritmo di programma di span modificato per dimostrare che questi miglioramenti persistono anche senza una promessa anticipata ed estendiamo questo approccio al problema più generale della conversione dello stato. Come applicazione, dimostriamo vantaggi quantistici esponenziali e superpolinomiali nella complessità media delle query per diversi problemi di ricerca, generalizzando il metodo Search with Advice di Montanaro [Montanaro, TQC 2010].

Migliorata la complessità delle query quantistiche su input più semplici PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Immagine in primo piano: albero decisionale utilizzato per creare uno dei nostri algoritmi.

Riepilogo popolare

Ci aspettiamo che gli algoritmi quantistici, come gli algoritmi classici, funzionino più velocemente con input più semplici. Ad esempio, se stai cercando un elemento in un elenco non ordinato e ci sono molte copie di quell'elemento, ci aspetteremmo che l'algoritmo quantistico funzioni più velocemente in questa situazione rispetto a quando c'è un solo elemento contrassegnato, anche senza sapere il numero di elementi target in anticipo. In effetti, per quanto riguarda il problema della ricerca, è noto come ottenere un tale vantaggio su input più facili. Tuttavia, generalizzare questa idea a problemi che vanno oltre la ricerca è difficile quando non esiste un modo ovvio per segnalare quando il calcolo è stato eseguito per un tempo sufficientemente lungo. Modifichiamo diversi framework algoritmici popolari nel modello di query per creare flag che ci avvisano se il calcolo è stato eseguito abbastanza a lungo, permettendoci di terminare l'algoritmo in anticipo su input più facili, senza sapere in anticipo se l'istanza è facile o difficile. Come applicazione, data una distribuzione di input sia facili che difficili per un problema, possiamo analizzare la complessità media della query. Mostriamo che alcune distribuzioni di input per i problemi di ricerca producono grandi vantaggi medi di query quantistiche rispetto agli algoritmi classici.

► dati BibTeX

► Riferimenti

, Andris Ambainis e Ronald de Wolf. Complessità delle query quantistiche nel caso medio. 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

, Dorit Aharonov. Calcolo quantistico. Annual Reviews of Computational Physics VI, pagine 259–346, 1999. doi:10.1142/​9789812815569_0007.
https: / / doi.org/ 10.1142 / 9789812815569_0007

, Michel Boyer, Gilles Brassard, Peter Høyer e Alain Tapp. Limiti stretti alla ricerca quantistica. 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

, Aleksandrs Belovs. Programmi span per funzioni con certificati 1 di dimensione costante: abstract esteso. In Atti del quarantaquattresimo simposio annuale ACM sulla teoria dell'informatica, STOC '12, pagine 77–84, 2012. doi:10.1145/​2213977.2213985.
https: / / doi.org/ 10.1145 / 2213977.2213985 mila

, Gilles Brassard, Peter Høyer, Michele Mosca e Alain Tapp. Amplificazione e stima dell'ampiezza quantistica. In Calcolo e informazione quantistica, volume 305 di Contemp. Matematica, pagine 53–74. Amer. Matematica. Soc., Providence, RI, 2002. doi:10.1090/​conm/​305/​05215.
https: / / doi.org/ 10.1090 / conm / 305 / 05215

, Gilles Brassard, Peter Høyer e Alain Tapp. Conteggio quantistico. In Automata, Languages ​​and Programming, pagine 820–831, 1998. doi:10.1007/​BFb0055105.
https: / / doi.org/ 10.1007 / BFb0055105

, Aleksandrs Belovs e Ben W. Reichardt. Programmi span e algoritmi quantistici per la connettività st e il rilevamento degli artigli. Appunti delle lezioni di informatica, 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

, Aleksandrs Belovs e Ansis Rosmanis. Limite inferiore quantistico stretto per il conteggio approssimativo con gli stati quantistici. 2020. arXiv:2002.06879.
arXiv: 2002.06879

, Salman Beigi e Leila Taghavi. Accelerazione quantistica basata su alberi decisionali classici. Quantum, 4:241, 2020. doi:10.22331/​q-2020-03-02-241.
https:/​/​doi.org/​10.22331/​q-2020-03-02-241

, Aleksandrs Belovs e Duyal Yolcu. Biglietto di sola andata per Las Vegas e l'avversario quantistico. 2023. arXiv:2301.02003.
arXiv: 2301.02003

, Richard. Cleve, Artur. Ekert, Chiara Machiavello e Michele Mosca. Algoritmi quantistici rivisitati. Atti della Royal Society di Londra. Serie A: Scienze matematiche, fisiche e ingegneristiche, 454(1969):339–354, 1998. doi:10.1098/​rspa.1998.0164.
https: / / doi.org/ 10.1098 / rspa.1998.0164

, Arjan Cornelissen, Stacey Jeffery, Maris Ozols e Alvaro Piedrafita. Programmi span e complessità del tempo quantistico. Nel 45° Simposio Internazionale sui Fondamenti Matematici dell'Informatica (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

, Chris Cade, Ashley Montanaro e Aleksandrs Belovs. Algoritmi quantistici efficienti in termini di tempo e spazio per rilevare cicli e testare la bipartitezza. Informazioni e calcolo quantistici, 18(1-2):18–50, 2018.

, Kai DeLorenzo, Shelby Kimmel e R. Teal Witter. Applicazioni dell'Algoritmo Quantistico per la st-Connettività. Nella 14a conferenza sulla teoria del calcolo quantistico, della comunicazione e della crittografia (TQC 2019), pagine 6:1–6:14, 2019. doi:10.4230/​LIPIcs.TQC.2019.6.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2019.6

, Dmitry Grinko, Julien Gacon, Christa Zoufal e Stefan Woerner. Stima iterativa dell'ampiezza quantistica. npj Quantum Information, 7(1):52, marzo 2021. doi:10.1038/​s41534-021-00379-1.
https:/​/​doi.org/​10.1038/​s41534-021-00379-1

, Lov K. Grover. La meccanica quantistica aiuta a cercare un ago in un pagliaio. Physical Review Letters, 79(2):325–328, 1997. doi:10.1103/​PhysRevLett.79.325.
https: / / doi.org/ 10.1103 / PhysRevLett.79.325

, Wassily Hoeffding. Disuguaglianze di probabilità per somme di variabili casuali limitate. 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 mila

, Tsuyoshi Ito e Stacey Jeffery. Programmi di intervallo approssimativo. Algorithmica, 81(6):2158–2195, 2019. doi:10.1007/​s00453-018-0527-1.
https:/​/​doi.org/​10.1007/​s00453-018-0527-1

, Michael Jarret, Stacey Jeffery, Shelby Kimmel e Alvaro Piedrafita. Algoritmi quantistici per la connettività e problemi correlati. Nel 26° Simposio europeo annuale sugli algoritmi (ESA 2018), pagine 49:1–49:13, 2018. doi:10.4230/​LIPIcs.ESA.2018.49.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2018.49

, Alexei Y. Kitaev. Misure quantistiche e problema dello stabilizzatore abeliano. 1995. arXiv:quant-ph/​9511026.
arXiv: Quant-ph / 9511026

, Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek e Mario Szegedy. Complessità delle query quantistiche della conversione dello stato. Nel 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pagine 344–353, 2011. doi:10.1109/​FOCS.2011.75.
https: / / doi.org/ 10.1109 / FOCS.2011.75

, Frédéric Magniez, Ashwin Nayak, Jérémie Roland e Miklos Santha. Cerca tramite Quantum Walk. SIAM Journal on Computing, 40(1):142–164, 2011. doi:10.1137/​090745854.
https: / / doi.org/ 10.1137 / 090745854 mila

, Ashley Montanaro. Ricerca quantistica con consigli. In Conferenza su calcolo quantistico, comunicazione e crittografia, pagine 77–93. Springer, 2010. doi:10.1007/​978-3-642-18073-6_7.
https:/​/​doi.org/​10.1007/​978-3-642-18073-6_7

, Ben W. Reichardt. Programmi span e complessità delle query quantistiche: il limite generale dell'avversario è quasi stretto per ogni funzione booleana. 50° Simposio annuale dell'IEEE sui fondamenti dell'informatica, pagine 544–551, 2009. doi:10.1109/​FOCS.2009.55.
https: / / doi.org/ 10.1109 / FOCS.2009.55

, Ben W. Reichardt. Riflessioni per algoritmi di query quantistica. In Atti del simposio annuale ACM-SIAM 2011 sugli algoritmi discreti, Atti, pagine 560–569. 2011. doi:10.1137/​1.9781611973082.44.
https: / / doi.org/ 10.1137 / 1.9781611973082.44 mila

, Leila Taghavi. Algoritmo quantistico semplificato per il problema dell'identificazione dell'oracolo. Quantum Machine Intelligence, 4(2):19, 2022. doi:10.1007/​s42484-022-00080-2.
https:/​/​doi.org/​10.1007/​s42484-022-00080-2

Citato da

[1] Stacey Jeffery, Shelby Kimmel e Alvaro Piedrafita, "Algoritmo quantistico per il campionamento del bordo del percorso", arXiv: 2303.03319, (2023).

[2] Michael Czekanski, Shelby Kimmel e R. Teal Witter, "Algoritmi di query quantistica a doppio avversario robusti ed efficienti in termini di spazio", arXiv: 2306.15040, (2023).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2024-04-11 15:45:18). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2024-04-11 15:45:17).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico