Peruskvanttialirutiinit: useiden merkittyjen elementtien löytäminen ja lukujen summaus

Peruskvanttialirutiinit: useiden merkittyjen elementtien löytäminen ja lukujen summaus

Aikaleima: 14. maaliskuuta 2024 9
Peruskvanttialirutiinit: useiden merkittyjen elementtien löytäminen ja lukujen summaus PlatoBlockchain Data Intelligence. Pystysuuntainen haku. Ai.

Joran van Apeldoorn1, Sander Gribling2ja Harold Nieuwboer3

1IViR ja QuSoft, Amsterdamin yliopisto, Alankomaat
2Ekonometriikan ja operaatiotutkimuksen laitos, Tilburgin yliopisto, Tilburg, Alankomaat
3Korteweg–de Vries Institute for Mathematics and QuSoft, Amsterdamin yliopisto, Alankomaat ja tietojenkäsittelytieteellinen tiedekunta, Ruhrin yliopisto Bochum, Saksa ja matemaattisten tieteiden laitos, Kööpenhaminan yliopisto, Tanska

Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.

Abstrakti

Näytämme, kuinka löytää kaikki $k$ merkityt elementit luettelosta, jonka koko on $N$ käyttämällä kvanttikyselyiden optimaalista määrää $O(sqrt{N k})$ ja vain polylogaritmista ylärajaa portin monimutkaisuudesta, asetuksessa, jossa jollain on pieni kvanttimuisti. Aiemmat algoritmit joko aiheuttivat portin monimutkaisuuden tekijän $k$ tai niillä oli ylimääräinen tekijä $log(k)$ kyselyn monimutkaisuuteen.
Tarkastellaan sitten ongelmaa löytää kertova $delta$-likimäärä $s = summa_{i=1}^N v_i$, jossa $v=(v_i) kohdassa [0,1]^N$, jos kvanttikyselyn käyttöoikeus on $v$:n binäärikuvaus. Annamme algoritmin, joka tekee niin todennäköisyydellä vähintään $1-rho$ käyttämällä kvanttikyselyitä $O(sqrt{N log(1/rho) / delta})$ ($rho$:n lievillä oletuksilla). Tämä parantaa neliöllisesti riippuvuutta arvoista $1/delta$ ja $log(1/rho)$ verrattuna yksinkertaiseen amplitudiestimoinnin soveltamiseen. Parannetun $log(1/rho)$-riippuvuuden saamiseksi käytämme ensimmäistä tulosta.

► BibTeX-tiedot

► Viitteet

[1] Srinivasan Arunachalam ja Ronald de Wolf. Porttien lukumäärän optimointi kvanttihaussa. Kvantti Info. 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á. Tarkat Kolmogorov- ja kokonaisvariaatioetäisyydet joidenkin tuttujen diskreettien jakaumien välillä. 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. Kvanttialgoritmit matriisin skaalaukseen ja matriisin tasapainottamiseen. Teoksessa Proceedings of 48th International Colloquium on Automata, Languages ​​ja Programming (ICALP'21), osa 198, sivut 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. Kvanttilikimääräinen laskenta, yksinkertaistettu. Symposium on Simplicity in Algorithms, sivut 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. Tiukat rajat kvanttihaulle. Fortschritte der Physik, 46(4–5):493–505, 1998. Physcomp'96:n aikaisempi versio. arXiv:quant-ph/​9605034.
arXiv: kvant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf ja Christof Zalka. Pienen virheen ja nollavirheen kvanttialgoritmien rajat. 40th Annual Symposium on Foundations of Computer Science (FOCS'99), sivut 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca ja Alain Tapp. Kvanttiamplitudin vahvistus ja estimointi. Teoksessa Quantum Computation and Quantum Information: A Millennium Volume, nide 305 of Contemporary Mathematics, sivut 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, osa 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even ja Oded Goldreich. Alarajat näytteenottoalgoritmeille keskiarvon arvioimiseksi. Information Processing Letters, 53(1):17–25, tammikuu 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. Kvanttikoneoppiminen: klassinen näkökulma. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, tammikuu 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. Johdatus algoritmeihin. MIT Press, 4. painos, 2022.

[12] P. Diaconis ja D. Freedman. Rajalliset vaihdettavat sekvenssit. The Annals of Probability, 8(4):745–764, 1980. URL-osoite: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ vakaa / 2242823

[13] Christoph Dürr ja Peter Høyer. Kvanttialgoritmi minimin löytämiseksi, 1996. doi:10.48550/​arXiv.quant-ph/​9607014.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9607014
arXiv: kvant-ph / 9607014

[14] Christoph Dürr, Mark Heiligman, Peter Høyer ja Mehdi Mhalla. Joidenkin graafisten ongelmien kvanttikysely monimutkaisuus. SIAM Journal on Computing, 35(6):1310–1328, tammikuu 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / +050644719

[15] Paul Dagum, Richard Karp, Michael Luby ja Sheldon Ross. Optimaalinen algoritmi Monte Carlon estimointiin. SIAM Journal on Computing, 29(5):1484–1496, tammikuu 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd ja Lorenzo Maccone. Kvanttihakumuisti. Physical Review Letters, 100(16), huhtikuu 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling ja Harold Nieuwboer. Parannetut kvanttiala- ja ylärajat matriisin skaalaukseen. Teoksessa Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), osa 219, sivut 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-periaatteen kvanttiversioista. 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), nide 2285 of Lecture Notes in Computer Science, sivut 347–358, Berliini, 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. Nopea kvanttimekaaninen algoritmi tietokantahakuun. Teoksessa Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), sivut 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / +237814.237866
arXiv: kvant-ph / 9605043

[20] Lov K. Grover. Quantum telecomputation, 1997. Bell Labs Technical Memorandum ITD97-31630F. doi:10.48550/​arXiv.quant-ph/​9704012.
https://​/​doi.org/​10.48550/​arXiv.quant-ph/​9704012
arXiv: kvant-ph / 9704012

[21] Lov K. Grover. Kehys nopeille kvanttimekaanisille algoritmeille. Teoksessa Proceedings of the Thirtyth Annual ACM Symposium on the Theory of Computing (STOC'98), sivut 53–62, 1998. arXiv:quant-ph/​9711043, doi:10.1145/​276698.276712.
https: / / doi.org/ 10.1145 / +276698.276712
arXiv: kvant-ph / 9711043

[22] Yassine Hamoudi. Kvantti Sub-Gaussin keskiarvon estimaattori. 29th Annual European Symposium on Algorithms (ESA 2021), Leibniz International Proceedings in Informatics (LIPIcs) nide 204, sivut 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Svante Janson. Geometristen ja eksponentiaalisten muuttujien summien loppurajat. 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. Tietokoneohjelmoinnin taito, osa III. Addison-Wesley, 2. painos, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari ja Ryan O'Donnell. Keskimääräinen arvio, kun sinulla on lähdekoodi; tai kvantti Monte Carlo -menetelmiä. Julkaisussa Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), sivut 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. Kvanttilaskenta ja kvantitiedot. Cambridge University Press, 2002.

[27] Ashwin Nayak ja Felix Wu. Mediaanin ja siihen liittyvien tilastojen lähentämisen kvanttikyselyn monimutkaisuus. Teoksessa Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), sivut 384–393, 1999. arXiv:quant-ph/​9804066, doi:10.1145/​301250.301349.
https: / / doi.org/ 10.1145 / +301250.301349
arXiv: kvant-ph / 9804066

[28] B. Roos. Binomiaalinen likimäärä Poissonin binomiaalijakaumaan: Krawtchoukin laajennus. Todennäköisyysteoria ja sen sovellukset, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

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

Viitattu

Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.

Aikaleima:

Lisää aiheesta Quantum Journal