Subroutine quantistiche di base: ricerca di più elementi contrassegnati e somma di numeri

Subroutine quantistiche di base: ricerca di più elementi contrassegnati e somma di numeri

Timestamp: 14 marzo 2024 9:40
Subroutine quantistiche di base: trovare più elementi contrassegnati e sommare i numeri PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Joran van Apeldoorn1, Sander Gribling2e Harold Nieuwboer3

1IViR e QuSoft, Università di Amsterdam, Paesi Bassi
2Dipartimento di Econometria e Ricerca Operativa, Università di Tilburg, Tilburg, Paesi Bassi
3Korteweg–de Vries Institute for Mathematics e QuSoft, Università di Amsterdam, Paesi Bassi e Facoltà di Informatica, Università della Ruhr Bochum, Germania e Dipartimento di Scienze Matematiche, Università di Copenhagen, Danimarca

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

Astratto

Mostriamo come trovare tutti gli elementi contrassegnati con $k$ in un elenco di dimensione $N$ utilizzando il numero ottimale $O(sqrt{N k})$ di query quantistiche e solo un sovraccarico polilogaritmico nella complessità del gate, nell'impostazione in cui uno ha una piccola memoria quantistica. Gli algoritmi precedenti comportavano un sovraccarico del fattore $k$ nella complessità del gate oppure avevano un fattore $log(k)$ aggiuntivo nella complessità della query.
Consideriamo quindi il problema di trovare un'approssimazione moltiplicativa $delta$ di $s = sum_{i=1}^N v_i$ dove $v=(v_i) in [0,1]^N$, dato l'accesso alla query quantistica a una descrizione binaria di $v$. Forniamo un algoritmo che lo fa, con probabilità almeno $1-rho$, utilizzando query quantistiche $O(sqrt{N log(1/rho) / delta})$ (sotto lievi ipotesi su $rho$). Ciò migliora quadraticamente la dipendenza da $1/delta$ e $log(1/rho)$ rispetto a una semplice applicazione della stima dell'ampiezza. Per ottenere la dipendenza migliorata $log(1/rho)$ utilizziamo il primo risultato.

► dati BibTeX

► Riferimenti

, Srinivasan Arunachalam e Ronald de Wolf. Ottimizzazione del numero di porte nella ricerca quantistica. Informazioni quantistiche. Comput., 17(3-4):251–261, 2017. doi:10.26421/​qic17.3-4.
https: / / doi.org/ 10.26421 mila / qic17.3-4

, José A. Adell e P. Jodrá. Kolmogorov esatto e distanze di variazione totale tra alcune distribuzioni discrete familiari. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/​JIA/​2006/​64307.
https://​/​doi.org/​10.1155/​JIA/​2006/​64307

, Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter e Ronald de Wolf. Algoritmi quantistici per il ridimensionamento e il bilanciamento delle matrici. In Atti del 48° Colloquio Internazionale su Automata, Linguaggi e Programmazione (ICALP'21), volume 198, pagine 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.ICALP.2021.110.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arXiv: 2011.12823

, Scott Aaronson e Patrick Rall. Conteggio quantistico approssimativo, semplificato. In Simposio sulla semplicità negli algoritmi, pagine 24–32, 2020. doi:10.1137/​1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5 mila

, Michel Boyer, Gilles Brassard, Peter Høyer e Alain Tapp. Limiti stretti alla ricerca quantistica. Fortschritte der Physik, 46(4–5):493–505, 1998. Versione precedente in Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: Quant-ph / 9605034

, Harry Buhrman, Richard Cleve, Ronald de Wolf e Christof Zalka. Limiti per algoritmi quantistici a errore piccolo e errore zero. Nel 40esimo Simposio annuale sui fondamenti dell'informatica (FOCS'99), pagine 358–368. Società informatica IEEE, 1999.

, Gilles Brassard, Peter Høyer, Michele Mosca e Alain Tapp. Amplificazione e stima dell'ampiezza quantistica. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 di Contemporary Mathematics, pagine 53–74. American Mathematical Society, 2002. 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

, Richard Brent e Paul Zimmermann. Aritmetica informatica moderna, volume 18. Cambridge University Press, 2010.

, Ran Canetti, Guy Even e Oded Goldreich. Limiti inferiori per gli algoritmi di campionamento per la stima della media. Lettere sull'elaborazione delle informazioni, 53(1):17–25, gennaio 1995. doi:10.1016/​0020-0190(94)00171-T.
https:/​/​doi.org/​10.1016/​0020-0190(94)00171-T

, Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini e Leonard Wossnig. Apprendimento automatico quantistico: una prospettiva classica. Atti della Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, gennaio 2018. doi:10.1098/​rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduzione agli algoritmi. MIT Press, 4a edizione, 2022.

, P. Diaconis e D. Freedman. Sequenze finite scambiabili. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ stabile / 2242823

, Christoph Dürr e Peter Høyer. Un algoritmo quantistico per trovare il minimo, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: Quant-ph / 9607014

, Christoph Dürr, Mark Heiligman, Peter Høyer e Mehdi Mhalla. Complessità delle query quantistiche di alcuni problemi sui grafici. SIAM Journal on Computing, 35(6):1310–1328, gennaio 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719 mila

, Paul Dagum, Richard Karp, Michael Luby e Sheldon Ross. Un algoritmo ottimale per la stima Monte Carlo. SIAM Journal on Computing, 29(5):1484–1496, gennaio 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

, Vittorio Giovannetti, Seth Lloyd e Lorenzo Maccone. Memoria quantistica ad accesso casuale. Physical Review Letters, 100(16), aprile 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

, Sander Gribling e Harold Nieuwboer. Limiti inferiori e superiori quantistici migliorati per il ridimensionamento della matrice. In Atti del 39° Simposio internazionale sugli aspetti teorici dell'informatica (STACS'22), volume 219, pagine 35:1–35:23, 2022. arXiv:2109.15282, doi:10.4230/​LIPIcs.STACS.2022.35.
https: / / doi.org/ 10.4230 / LIPIcs.STACS.2022.35
arXiv: 2109.15282

, Mart de Graaf e Ronald de Wolf. Sulle versioni quantistiche del principio Yao. Nel 19° Simposio sugli aspetti teorici dell'informatica (STACS'02), volume 2285 di Lecture Notes in Computer Science, pagine 347–358, Berlino, Heidelberg, 2002. Springer. doi:10.1007/​3-540-45841-7_28.
https:/​/​doi.org/​10.1007/​3-540-45841-7_28

, Lov K. Grover. Un algoritmo veloce di meccanica quantistica per la ricerca nei database. In Atti del 38° Simposio annuale ACM sulla teoria dell'informatica (STOC'96), pagine 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866 mila
arXiv: Quant-ph / 9605043

, Lov K. Grover. Telecalcolo quantistico, 1997. Memorandum tecnico dei Bell Labs ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: Quant-ph / 9704012

, Lov K. Grover. Un framework per algoritmi veloci di meccanica quantistica. In Atti del trentesimo simposio annuale ACM sulla teoria dell'informatica (STOC'98), pagine 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712 mila
arXiv: Quant-ph / 9711043

, Yassine Hamoudi. Stimatore della media quantistica sub-gaussiana. Nel 29° Simposio annuale europeo sugli algoritmi (ESA 2021), volume 204 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

, Svante Janson. Limiti di coda per somme di variabili geometriche ed esponenziali. Statistics & Probability Letters, 135:1–6, 2018. doi:10.1016/​j.spl.2017.11.017.
https://​/​doi.org/​10.1016/​j.spl.2017.11.017

, Donald Ervin Knuth. L'arte della programmazione informatica, volume III. Addison-Wesley, 2a edizione, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

, Robin Kothari e Ryan O'Donnell. Stima media quando si dispone del codice sorgente; o metodi Monte Carlo quantistici. In Atti del simposio annuale ACM-SIAM sugli algoritmi discreti del 2023 (SODA'23), pagine 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

, Michael A. Nielsen e Isaac L. Chuang. Calcolo quantistico e informazioni quantistiche. Cambridge University Press, 2002.

, Ashwin Nayak e Felix Wu. La complessità delle query quantistiche dell'approssimazione della mediana e delle statistiche correlate. In Atti del 31° Simposio annuale ACM SIGACT sulla teoria dell'informatica (STOC'99), pagine 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349 mila
arXiv: Quant-ph / 9804066

, B.Roos. Approssimazione binomiale alla distribuzione binomiale di Poisson: l'espansione di Krawtchouk. Teoria della probabilità e sue applicazioni, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

, Robert M. Giovane. 75.9 Costante di Eulero. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/​3620251.
https: / / doi.org/ 10.2307 / 3620251 mila

Citato da

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