Subrutine cuantice de bază: găsirea mai multor elemente marcate și însumarea numerelor

Republicat de Platon

Urmaritori: 0

Subrutine cuantice de bază: găsirea mai multor elemente marcate și însumarea numerelor PlatoBlockchain Data Intelligence. Căutare verticală. Ai.

Joran van Apeldoorn¹, Sander Gribling², și Harold Nieuwboer³

¹IViR și QuSoft, Universitatea din Amsterdam, Țările de Jos
²Departamentul de Econometrie și Cercetare Operațională, Universitatea Tilburg, Tilburg, Țările de Jos
³Institutul Korteweg–de Vries pentru Matematică și QuSoft, Universitatea din Amsterdam, Țările de Jos și Facultatea de Informatică, Universitatea Ruhr Bochum, Germania și Departamentul de Științe Matematice, Universitatea din Copenhaga, Danemarca

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

Abstract

Arătăm cum să găsim toate elementele marcate $k$ într-o listă de mărime $N$ folosind numărul optim $O(sqrt{N k})$ de interogări cuantice și doar o suprasarcină polilogaritmică în complexitatea porții, în setarea în care unul are o memorie cuantică mică. Algoritmii anteriori fie au suportat un factor $k$ în complexitatea porții, fie au avut un factor suplimentar $log(k)$ în complexitatea interogării.
Apoi luăm în considerare problema găsirii unei $delta$-aproximații multiplicative a $s = sum_{i=1}^N v_i$ unde $v=(v_i) în [0,1]^N$, având în vedere accesul la interogarea cuantică la o descriere binară a $v$. Oferim un algoritm care face acest lucru, cu probabilitate de cel puțin $1-rho$, folosind $O(sqrt{N log(1/rho) / delta})$ interogări cuantice (în ipoteze ușoare pe $rho$). Acest lucru îmbunătățește în mod pătratic dependența de $1/delta$ și $log(1/rho)$ în comparație cu o aplicare simplă a estimării amplitudinii. Pentru a obține dependența îmbunătățită $log(1/rho)$ folosim primul rezultat.

► Date BibTeX

@articol{vanApeldoorn2024basicquantum, doi = {10.22331/q-2024-03-14-1284}, url = {https://doi.org/10.22331/q-2024-03-14-1284}, titlu = {subrutine cuantice de bază: găsirea mai multor elemente marcate și însumarea numerelor}, autor = {van Apeldoorn, Joran și Gribling, Sander și Nieuwboer, Harold}, jurnal = {{Quantum}}, issn = {2521-327X}, editor = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volum = {8}, pagini = {1284}, luna = martie, an = {2024} }

► Referințe

[1] Srinivasan Arunachalam și Ronald de Wolf. Optimizarea numărului de porți în căutarea cuantică. Informații cuantice. Comput., 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell și P. Jodrá. Kolmogorov exact și distanțe de variație totală între unele distribuții discrete familiare. Journal of Inequalities and Applications, 2006(1):1–8, 2006. doi:10.1155/JIA/2006/64307.
https:///doi.org/10.1155/JIA/2006/64307

[3] Joran van Apeldoorn, Sander Gribling, Yinan Li, Harold Nieuwboer, Michael Walter și Ronald de Wolf. Algoritmi cuantici pentru scalarea matricei și echilibrarea matricei. În Proceedings of 48th International Coloquium on Automata, Languages, and Programming (ICALP'21), volumul 198, paginile 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

[4] Scott Aaronson și Patrick Rall. Numărarea aproximativă cuantică, simplificată. În Symposium on Simplicity in Algorithms, paginile 24–32, 2020. doi:10.1137/1.9781611976014.5.
https: / / doi.org/ 10.1137 / 1.9781611976014.5

[5] Michel Boyer, Gilles Brassard, Peter Høyer și Alain Tapp. Limite strânse în căutarea cuantică. Fortschritte der Physik, 46(4–5):493–505, 1998. Versiunea anterioară în Physcomp'96. arXiv:quant-ph/9605034.
arXiv: Quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf și Christof Zalka. Limite pentru algoritmii cuantici cu eroare mică și zero eroare. În cel de-al 40-lea Simpozion anual privind fundamentele informaticii (FOCS'99), paginile 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca și Alain Tapp. Amplificarea și estimarea amplitudinii cuantice. În Quantum Computation and Quantum Information: A Millennium Volume, volumul 305 din Contemporary Mathematics, paginile 53–74. Societatea Americană de Matematică, 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

[8] Richard Brent și Paul Zimmermann. Modern Computer Arithmetic, volumul 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even și Oded Goldreich. Limite inferioare pentru algoritmii de eșantionare pentru estimarea mediei. Information Processing Letters, 53(1):17–25, ianuarie 1995. doi:10.1016/0020-0190(94)00171-T.
https://doi.org/10.1016/0020-0190(94)00171-T

[10] Carlo Ciliberto, Mark Herbster, Alessandro Davide Ialongo, Massimiliano Pontil, Andrea Rocchetto, Simone Severini și Leonard Wossnig. Învățarea cuantică a mașinilor: o perspectivă clasică. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, jan 2018. doi:10.1098/rspa.2017.0551.
https: / / doi.org/ 10.1098 / rspa.2017.0551

[11] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein. Introducere în algoritmi. MIT Press, ediția a 4-a, 2022.

[12] P. Diaconis şi D. Freedman. Secvențe finite interschimbabile. The Annals of Probability, 8(4):745–764, 1980. URL: https:///www.jstor.org/stable/2242823.
https: / / www.jstor.org/ stabil / 2242823

[13] Christoph Dürr și Peter Høyer. Un algoritm cuantic pentru găsirea minimului, 1996. doi:10.48550/arXiv.quant-ph/9607014.
https:///doi.org/10.48550/arXiv.quant-ph/9607014
arXiv: Quant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer și Mehdi Mhalla. Complexitatea interogării cuantice a unor probleme de grafic. SIAM Journal on Computing, 35(6):1310–1328, ianuarie 2006. doi:10.1137/050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby și Sheldon Ross. Un algoritm optim pentru estimarea Monte Carlo. SIAM Journal on Computing, 29(5):1484–1496, ianuarie 2000. doi:10.1137/S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd și Lorenzo Maccone. Memoria cuantică cu acces aleatoriu. Physical Review Letters, 100(16), apr 2008. doi:10.1103/physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling și Harold Nieuwboer. Limitele inferioare și superioare cuantice îmbunătățite pentru scalarea matricei. În Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), volumul 219, paginile 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

[18] Mart de Graaf și Ronald de Wolf. Pe versiunile cuantice ale principiului Yao. În 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), volumul 2285 din Lecture Notes in Computer Science, paginile 347–358, Berlin, Heidelberg, 2002. Springer. doi:10.1007/3-540-45841-7_28.
https://doi.org/10.1007/3-540-45841-7_28

[19] Lov K. Grover. Un algoritm mecanic cuantic rapid pentru căutarea în baze de date. În Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), paginile 212–219, 1996. arXiv:quant-ph/9605043, doi:10.1145/237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arXiv: Quant-ph / 9605043

[20] Lov K. Grover. Quantum telecomputation, 1997. Memorandumul tehnic Bell Labs ITD97-31630F. doi:10.48550/arXiv.quant-ph/9704012.
https:///doi.org/10.48550/arXiv.quant-ph/9704012
arXiv: Quant-ph / 9704012

[21] Lov K. Grover. Un cadru pentru algoritmi de mecanică cuantică rapidă. În Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC'98), paginile 53–62, 1998. arXiv:quant-ph/9711043, doi:10.1145/276698.276712.
https: / / doi.org/ 10.1145 / 276698.276712
arXiv: Quant-ph / 9711043

[22] Yassine Hamoudi. Estimator mediu cuantic sub-gaussian. În 29th Annual European Symposium on Algorithms (ESA 2021), volumul 204 din Leibniz International Proceedings in Informatics (LIPIcs), paginile 50:1–50:17, 2021. doi:10.4230/LIPIcs.ESA.2021.50.
https:///doi.org/10.4230/LIPIcs.ESA.2021.50

[23] Svante Janson. Limite de coadă pentru sumele variabilelor geometrice și exponențiale. 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

[24] Donald Ervin Knuth. Arta programarii computerelor, volumul III. Addison-Wesley, ediția a 2-a, 1998. URL: https:///www.worldcat.org/oclc/312994415.
https:///www.worldcat.org/oclc/312994415

[25] Robin Kothari și Ryan O'Donnell. Estimare medie atunci când aveți codul sursă; sau, metode cuantice Monte Carlo. În Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), paginile 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen și Isaac L. Chuang. Calcul cuantic și informația cuantică. Cambridge University Press, 2002.

[27] Ashwin Nayak și Felix Wu. Complexitatea interogării cuantice a aproximării medianei și a statisticilor aferente. În Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), paginile 384–393, 1999. arXiv:quant-ph/9804066, doi:10.1145/301250.301349.
https: / / doi.org/ 10.1145 / 301250.301349
arXiv: Quant-ph / 9804066

[28] B. Roos. Aproximarea binomială la distribuția binomială Poisson: expansiunea Krawtchouk. Teoria probabilității și aplicațiile sale, 45(2):258–272, 2001. doi:10.1137/S0040585X9797821X.
https:///doi.org/10.1137/S0040585X9797821X

[29] Robert M. Young. 75.9 Constanta lui Euler. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/3620251.
https: / / doi.org/ 10.2307 / 3620251

Citat de

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.