Põhilised kvant-alamprogrammid: mitme märgitud elemendi leidmine ja arvude summeerimine

Põhilised kvant-alamprogrammid: mitme märgitud elemendi leidmine ja arvude summeerimine

Ajatempel: 14. märts 2024 9:40
Basic quantum subroutines: finding multiple marked elements and summing numbers PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Joran van Apeldoorn1, Sander Gribling2ja Harold Nieuwboer3

1IViR ja QuSoft, Amsterdami Ülikool, Holland
2Ökonomeetria ja operatsioonide uurimise osakond, Tilburgi ülikool, Tilburg, Holland
3Korteweg–de Vriesi matemaatika ja QuSofti instituut, Amsterdami ülikool, Holland ja arvutiteaduste teaduskond, Ruhri ülikool, Bochum, Saksamaa ja Kopenhaageni ülikooli matemaatikateaduste osakond, Taani

Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.

Abstraktne

Näitame, kuidas leida kõik $k$ märgitud elemendid loendist suurusega $N$, kasutades kvantpäringute optimaalset arvu $O(sqrt{N k})$ ja ainult polülogaritmilist lisakulu värava keerukuses, seades kus inimesel on väike kvantmälu. Varasemad algoritmid tekitasid värava keerukuses teguri $k$ või lisategur $log(k)$ päringu keerukuses.
Seejärel käsitleme probleemi $s = summa_{i=1}^N v_i$ korduva $delta$-lähenduse leidmisel, kus $v=(v_i) väärtuses [0,1]^N$, kui kvantpäringule on juurdepääs $v$ binaarne kirjeldus. Anname algoritmi, mis seda teeb vähemalt $1-rho$ tõenäosusega, kasutades $O(sqrt{N log(1/rho) / delta})$ kvantpäringuid ($rho$ kergetel eeldustel). Võrreldes amplituudi hindamise lihtsa rakendamisega, parandab see ruutkeskmiselt sõltuvust $1/delta$ ja $log(1/rho)$-st. Täiustatud sõltuvuse $log(1/rho)$ saamiseks kasutame esimest tulemust.

► BibTeX-i andmed

► Viited

[1] Srinivasan Arunachalam ja Ronald de Wolf. Väravate arvu optimeerimine kvantotsingus. Kvantinfo. 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 ja P. Jodrá. Täpne Kolmogorovi ja kogu variatsioonikaugus mõne tuttava diskreetjaotuse vahel. 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 ja Ronald de Wolf. Kvantalgoritmid maatriksi skaleerimiseks ja maatriksi tasakaalustamiseks. Väljaandes Proceedings of 48th International Colloquium on Automata, Languages ​​ja Programming (ICALP'21), köide 198, lk 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 ja Patrick Rall. Kvantligikaudne loendamine, lihtsustatud. In Symposium on Simplicity in Algorithms, lk 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 ja Alain Tapp. Ranged piirid kvantotsingul. Fortschritte der Physik, 46(4–5):493–505, 1998. Physcomp'96 varasem versioon. arXiv:quant-ph/9605034.
arXiv:quant-ph/9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf ja Christof Zalka. Väikese vea ja nullveaga kvantalgoritmide piirid. In 40th Annual Symposium on Foundations of Computer Science (FOCS'99), lk 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvantamplituudi võimendamine ja hindamine. In Quantum Computation and Quantum Information: A Millennium Volume, Contemporary Mathematics, köide 305, lk 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

[8] Richard Brent ja Paul Zimmermann. Modern Computer Aithmetic, köide 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even ja Oded Goldreich. Keskmise hindamise diskreetimisalgoritmide alumised piirid. Information Processing Letters, 53(1):17–25, jaanuar 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 ja Leonard Wossnig. Kvantmasinõpe: klassikaline vaatenurk. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, jaan 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 ja Clifford Stein. Algoritmide tutvustus. MIT Press, 4. väljaanne, 2022.

[12] P. Diaconis ja D. Freedman. Piiratud vahetatavad jadad. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https://​/​www.jstor.org/​stable/​2242823

[13] Christoph Dürr ja Peter Høyer. Kvantalgoritm miinimumi leidmiseks, 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 ja Mehdi Mhalla. Mõnede graafikuprobleemide kvantpäringu keerukus. SIAM Journal on Computing, 35(6):1310–1328, jaanuar 2006. doi:10.1137/​050644719.
https://​/​doi.org/​10.1137/​050644719

[15] Paul Dagum, Richard Karp, Michael Luby ja Sheldon Ross. Monte Carlo hinnangu optimaalne algoritm. SIAM Journal on Computing, 29(5):1484–1496, jaanuar 2000. doi:10.1137/​S0097539797315306.
https://​/​doi.org/​10.1137/​S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd ja Lorenzo Maccone. Kvant-muutmälu. Physical Review Letters, 100(16), aprill 2008. doi:10.1103/​physrevlett.100.160501.
https://​/​doi.org/​10.1103/​physrevlett.100.160501

[17] Sander Gribling ja Harold Nieuwboer. Täiustatud maatriksi skaleerimise kvant alumine ja ülemine piir. Väljaandes Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), köide 219, lk 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 ja Ronald de Wolf. Yao põhimõtte kvantversioonide kohta. In 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), köide 2285 of Lecture Notes in Computer Science, lk 347–358, Berliin, 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. Kiire kvantmehaaniline algoritm andmebaasi otsimiseks. Väljaandes Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), lk 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. Bell Labsi tehniline memorandum 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. Kiirete kvantmehaaniliste algoritmide raamistik. Väljaandes Proceedings of the Thirtyth Annual ACM Symposium on the Theory of Computing (STOC'98), lk 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. Kvant-Gaussi keskväärtuse hindaja. 29. iga-aastasel Euroopa algoritmide sümpoosionil (ESA 2021), Leibniz International Proceedings in Informatics (LIPIcs) köide 204, lk 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] Svante Janson. Geomeetriliste ja eksponentsiaalsete muutujate summade sabapiirid. 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. Arvutiprogrammeerimise kunst, III köide. Addison-Wesley, 2. väljaanne, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari ja Ryan O'Donnell. Keskmine hinnang, kui teil on lähtekood; või kvant-Monte Carlo meetodid. 2023. aasta ACM-SIAM-i iga-aastase diskreetsete algoritmide sümpoosioni (SODA'23) toimetised, lk 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https://​/​doi.org/​10.1137/​1.9781611977554.ch44

[26] Michael A. Nielsen ja Isaac L. Chuang. Kvantarvutus ja kvantteave. Cambridge University Press, 2002.

[27] Ashwin Nayak ja Felix Wu. Kvantpäringu keerukus mediaani ja sellega seotud statistika lähendamiseks. In Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), lk 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. Poissoni binoomjaotuse binoomiline lähendamine: Krawtchouki laiendus. Tõenäosusteooria ja selle rakendused, 45(2):258–272, 2001. doi: 10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

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

Viidatud

See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.

Ajatempel:

Veel alates Quantum Journal