Osnovne kvantne podprograme: iskanje več označenih elementov in seštevanje števil

Osnovne kvantne podprograme: iskanje več označenih elementov in seštevanje števil

Časovni žig: 14. marec 2024 9
Osnovne kvantne podprograme: iskanje več označenih elementov in seštevanje števil PlatoBlockchain Data Intelligence. Navpično iskanje. Ai.

Joran van Apeldoorn1, Sander Gribling2in Harold Nieuwboer3

1IViR in QuSoft, Univerza v Amsterdamu, Nizozemska
2Oddelek za ekonometrijo in operacijske raziskave, Univerza v Tilburgu, Tilburg, Nizozemska
3Korteweg–de Vries Institute for Mathematics in QuSoft, Univerza v Amsterdamu, Nizozemska in Fakulteta za računalništvo, Ruhr University Bochum, Nemčija in Oddelek za matematične vede, Univerza v Kopenhagnu, Danska

Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.

Minimalizem

Pokažemo, kako poiskati vse $k$ označene elemente na seznamu velikosti $N$ z uporabo optimalnega števila $O(sqrt{N k})$ kvantnih poizvedb in samo polilogaritmičnih stroškov v kompleksnosti vrat, v nastavitvi, kjer eden ima majhen kvantni spomin. Prejšnji algoritmi so povzročili faktor $k$ dodatnih stroškov pri zapletenosti vrat ali pa so imeli dodaten faktor $log(k)$ pri kompleksnosti poizvedbe.
Nato razmislimo o problemu iskanja multiplikativnega $delta$-približka $s = sum_{i=1}^N v_i$, kjer je $v=(v_i) v [0,1]^N$, glede na dostop kvantne poizvedbe do binarni opis $v$. Podamo algoritem, ki to počne z verjetnostjo vsaj $1-rho$, z uporabo kvantnih poizvedb $O(sqrt{N log(1/rho) / delta})$ (pod blagimi predpostavkami o $rho$). To kvadratno izboljša odvisnost od $1/delta$ in $log(1/rho)$ v primerjavi z enostavno uporabo ocene amplitude. Za pridobitev izboljšane odvisnosti $log(1/rho)$ uporabimo prvi rezultat.

► BibTeX podatki

► Reference

[1] Srinivasan Arunachalam in Ronald de Wolf. Optimizacija števila vrat v kvantnem iskanju. Kvantne informacije. Računalništvo, 17(3-4):251–261, 2017. doi:10.26421/qic17.3-4.
https: / / doi.org/ 10.26421 / qic17.3-4

[2] José A. Adell in P. Jodrá. Natančne Kolmogorove in skupne variacijske razdalje med nekaterimi znanimi diskretnimi porazdelitvami. 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 in Ronald de Wolf. Kvantni algoritmi za skaliranje matrike in uravnoteženje matrike. V zborniku 48. mednarodnega kolokvija o avtomatih, jezikih in programiranju (ICALP'21), zvezek 198, strani 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 in Patrick Rall. Kvantno približno štetje, poenostavljeno. V simpoziju o preprostosti v algoritmih, strani 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 in Alain Tapp. Ozke meje kvantnega iskanja. Fortschritte der Physik, 46(4–5):493–505, 1998. Starejša različica v Physcomp'96. arXiv:quant-ph/​9605034.
arXiv: kvant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf in Christof Zalka. Meje za kvantne algoritme z majhnimi in ničelnimi napakami. Na 40. letnem simpoziju o temeljih računalništva (FOCS'99), strani 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca in Alain Tapp. Ojačitev in ocena kvantne amplitude. V Quantum Computation and Quantum Information: A Millennium Volume, zvezek 305 Contemporary Mathematics, strani 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 in Paul Zimmermann. Modern Computer Arithmetic, zvezek 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even in Oded Goldreich. Spodnje meje algoritmov vzorčenja za ocenjevanje povprečja. Pisma o obdelavi informacij, 53(1):17–25, januar 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 in Leonard Wossnig. Kvantno strojno učenje: klasična perspektiva. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 474(2209):20170551, januar 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 in Clifford Stein. Uvod v algoritme. MIT Press, 4. izdaja, 2022.

[12] P. Diaconis in D. Freedman. Končna zamenljiva zaporedja. The Annals of Probability, 8(4):745–764, 1980. URL: https://​/​www.jstor.org/​stable/​2242823.
https: / / www.jstor.org/ hlev / 2242823

[13] Christoph Dürr in Peter Høyer. Kvantni algoritem za iskanje minimuma, 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 in Mehdi Mhalla. Kompleksnost kvantne poizvedbe nekaterih težav z grafom. SIAM Journal on Computing, 35(6):1310–1328, januar 2006. doi:10.1137/​050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby in Sheldon Ross. Optimalni algoritem za Monte Carlo oceno. SIAM Journal on Computing, 29(5):1484–1496, januar 2000. doi:10.1137/​S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd in Lorenzo Maccone. Kvantni pomnilnik z naključnim dostopom. Physical Review Letters, 100(16), apr. 2008. doi:10.1103/physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling in Harold Nieuwboer. Izboljšane kvantne spodnje in zgornje meje za skaliranje matrike. V zborniku 39. mednarodnega simpozija o teoretičnih vidikih računalništva (STACS'22), zvezek 219, strani 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 in Ronald de Wolf. O kvantnih različicah načela Yao. V 19. simpoziju o teoretičnih vidikih računalništva (STACS'02), zvezek 2285 Lecture Notes in Computer Science, strani 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. Hiter kvantno mehanski algoritem za iskanje po bazi podatkov. V zborniku 38. letnega simpozija ACM o teoriji računalništva (STOC'96), strani 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. Kvantno telekomputiranje, 1997. Tehnični memorandum Bell Labs 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. Ogrodje za hitre kvantno mehanske algoritme. V zborniku tridesetega letnega simpozija ACM o teoriji računalništva (STOC'98), strani 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. Ocenjevalnik kvantne sub-Gaussove sredine. V 29. letnem evropskem simpoziju o algoritmih (ESA 2021), zvezek 204 Leibniz International Proceedings in Informatics (LIPIcs), strani 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] Svante Janson. Repne meje za vsote geometrijskih in eksponentnih spremenljivk. 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. Umetnost računalniškega programiranja, zvezek III. Addison-Wesley, 2. izdaja, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari in Ryan O'Donnell. Povprečna ocena, ko imate izvorno kodo; ali kvantne metode Monte Carlo. V zborniku letnega simpozija ACM-SIAM o diskretnih algoritmih 2023 (SODA'23), strani 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen in Isaac L. Chuang. Kvantno računanje in kvantne informacije. Cambridge University Press, 2002.

[27] Ashwin Nayak in Felix Wu. Kompleksnost kvantne poizvedbe približevanja mediane in s tem povezane statistike. V zborniku 31. letnega simpozija ACM SIGACT o teoriji računalništva (STOC'99), strani 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. Binomski približek Poissonovi binomski porazdelitvi: Krawtchoukova ekspanzija. Teorija verjetnosti in njene aplikacije, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

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

Navedel

Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.

Časovni žig:

Več od Quantum Journal