Grunnleggende kvantesubrutiner: finne flere merkede elementer og summere tall

Grunnleggende kvantesubrutiner: finne flere merkede elementer og summere tall

Tidsstempel: 14. mars 2024 9:40
Grunnleggende kvantesubrutiner: finne flere merkede elementer og summere tall PlatoBlockchain Data Intelligence. Vertikalt søk. Ai.

Joran van Apeldoorn1, Sander Gribling2og Harold Nieuwboer3

1IViR og QuSoft, University of Amsterdam, Nederland
2Institutt for økonometrikk og operasjonsforskning, Tilburg University, Tilburg, Nederland
3Korteweg–de Vries Institutt for matematikk og QuSoft, Universitetet i Amsterdam, Nederland og fakultetet for datavitenskap, Ruhr Universitetet i Bochum, Tyskland og Institutt for matematiske vitenskaper, Københavns Universitet, Danmark

Finn dette papiret interessant eller vil diskutere? Scite eller legg igjen en kommentar på SciRate.

Abstrakt

Vi viser hvordan du finner alle $k$-merkede elementer i en liste med størrelse $N$ ved å bruke det optimale antallet $O(sqrt{N k})$ av kvantespørringer og bare en polylogaritmisk overhead i portkompleksiteten, i innstillingen hvor man har et lite kvanteminne. Tidligere algoritmer pådro seg enten en faktor $k$ overhead i gatekompleksiteten, eller hadde en ekstra faktor $log(k)$ i spørringskompleksiteten.
Vi vurderer deretter problemet med å finne en multiplikativ $delta$-tilnærming av $s = sum_{i=1}^N v_i$ hvor $v=(v_i) i [0,1]^N$, gitt kvantespørringstilgang til en binær beskrivelse av $v$. Vi gir en algoritme som gjør det, med sannsynlighet minst $1-rho$, ved å bruke $O(sqrt{N log(1/rho) / delta})$ kvantespørringer (under milde antakelser om $rho$). Dette forbedrer kvadratisk avhengigheten av $1/delta$ og $log(1/rho)$ sammenlignet med en enkel anvendelse av amplitudeestimering. For å oppnå den forbedrede $log(1/rho)$-avhengigheten bruker vi det første resultatet.

► BibTeX-data

► Referanser

[1] Srinivasan Arunachalam og Ronald de Wolf. Optimalisering av antall porter i kvantesøk. Kvanteinformasjon. 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 og P. Jodrá. Nøyaktig Kolmogorov og total variasjonsavstand mellom noen kjente diskrete distribusjoner. 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 og Ronald de Wolf. Kvantealgoritmer for matriseskalering og matrisebalansering. I Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), bind 198, side 110:1–110:17, 2021. arXiv:2011.12823, doi:10.4230/​LIPIcs.2021.110ICALP.XNUMX.
https: / / doi.org/ 10.4230 / LIPIcs.ICALP.2021.110
arxiv: 2011.12823

[4] Scott Aaronson og Patrick Rall. Kvante omtrentlig telling, forenklet. I Symposium on Simplicity in Algorithms, side 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 og Alain Tapp. Trange grenser for kvantesøk. Fortschritte der Physik, 46(4–5):493–505, 1998. Tidligere versjon i Physcomp'96. arXiv:quant-ph/​9605034.
arxiv: Quant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf og Christof Zalka. Grenser for små-feil og null-feil kvantealgoritmer. I 40th Annual Symposium on Foundations of Computer Science (FOCS'99), side 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca og Alain Tapp. Kvanteamplitudeforsterkning og estimering. I Quantum Computation and Quantum Information: A Millennium Volume, bind 305 av Contemporary Mathematics, side 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 og Paul Zimmermann. Modern Computer Arithmetic, bind 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even og Oded Goldreich. Nedre grenser for prøvetakingsalgoritmer for å estimere gjennomsnittet. Information Processing Letters, 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 og Leonard Wossnig. Kvantemaskinlæring: et klassisk perspektiv. 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 og Clifford Stein. Introduksjon til algoritmer. MIT Press, 4. utgave, 2022.

[12] P. Diaconis og D. Freedman. Finite utskiftbare sekvenser. 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 og Peter Høyer. En kvantealgoritme for å finne minimum, 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 og Mehdi Mhalla. Kvantespørringskompleksiteten til noen grafproblemer. 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 og Sheldon Ross. En optimal algoritme for Monte Carlo-estimering. 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 og Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100(16), apr 2008. doi:10.1103/​physrevlett.100.160501.
https: / / doi.org/ 10.1103 / physrevlett.100.160501

[17] Sander Gribling og Harold Nieuwboer. Forbedrede nedre og øvre kvantegrenser for matriseskalering. I Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), bind 219, side 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 og Ronald de Wolf. Om kvanteversjoner av Yao-prinsippet. I 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), bind 2285 av Lecture Notes in Computer Science, side 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] Kjærlighet K. Grover. En rask kvantemekanisk algoritme for databasesøk. I Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), side 212–219, 1996. arXiv:quant-ph/​9605043, doi:10.1145/​237814.237866.
https: / / doi.org/ 10.1145 / 237814.237866
arxiv: Quant-ph / 9605043

[20] Kjærlighet 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: Quant-ph / 9704012

[21] Kjærlighet K. Grover. Et rammeverk for raske kvantemekaniske algoritmer. I Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC'98), side 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. Kvante sub-Gaussisk gjennomsnittlig estimator. I 29th Annual European Symposium on Algorithms (ESA 2021), bind 204 av Leibniz International Proceedings in Informatics (LIPIcs), side 50:1–50:17, 2021. doi:10.4230/​LIPIcs.ESA.2021.50.
https://​/​doi.org/​10.4230/​LIPIcs.ESA.2021.50

[23] Svante Janson. Halegrenser for summer av geometriske og eksponentielle variabler. 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. Kunsten å programmere, bind III. Addison-Wesley, 2. utgave, 1998. URL: https://​/​www.worldcat.org/​oclc/​312994415.
https://​/​www.worldcat.org/​oclc/​312994415

[25] Robin Kothari og Ryan O'Donnell. Gjennomsnittlig estimering når du har kildekoden; eller, kvante Monte Carlo metoder. I Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), side 1186–1215, 2023. doi:10.1137/​1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen og Isaac L. Chuang. Kvanteberegning og kvanteinformasjon. Cambridge University Press, 2002.

[27] Ashwin Nayak og Felix Wu. Kvantespørringskompleksiteten ved tilnærming av medianen og relatert statistikk. I Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), side 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. Binomial tilnærming til Poisson-binomialfordelingen: Krawtchouk-utvidelsen. Theory of Probability & Its Applications, 45(2):258–272, 2001. doi:10.1137/​S0040585X9797821X.
https://​/​doi.org/​10.1137/​S0040585X9797821X

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

Sitert av

Denne artikkelen er utgitt i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) tillatelse. Opphavsrett forblir hos de opprinnelige rettighetshaverne som forfatterne eller institusjonene deres.

Tidstempel:

Mer fra Kvantejournal