Grundläggande kvantsubrutiner: Hitta flera markerade element och summera siffror

Återutgiven av Platon

anhängare: 0

Grundläggande kvantsubrutiner: hitta flera markerade element och summera siffror PlatoBlockchain Data Intelligence. Vertikal sökning. Ai.

Joran van Apeldoorn¹, Sander Gribling²och Harold Nieuwboer³

¹IViR och QuSoft, University of Amsterdam, Nederländerna
²Institutionen för ekonometri och operationsforskning, Tilburg University, Tilburg, Nederländerna
³Korteweg–de Vries Institute for Mathematics and QuSoft, University of Amsterdam, Nederländerna och fakulteten för datavetenskap, Ruhr University Bochum, Tyskland och Institutionen för matematiska vetenskaper, Köpenhamns universitet, Danmark

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Vi visar hur man hittar alla $k$ markerade element i en lista med storlek $N$ med det optimala antalet $O(sqrt{N k})$ av kvantfrågor och endast en polylogaritmisk overhead i grindens komplexitet, i inställningen där man har ett litet kvantminne. Tidigare algoritmer hade antingen en faktor $k$ overhead i grindens komplexitet, eller hade en extra faktor $log(k)$ i frågekomplexiteten.
Vi överväger sedan problemet med att hitta en multiplikativ $delta$-approximation av $s = summa_{i=1}^N v_i$ där $v=(v_i) i [0,1]^N$, givet kvantfrågeåtkomst till en binär beskrivning av $v$. Vi ger en algoritm som gör det, med sannolikhet minst $1-rho$, med $O(sqrt{N log(1/rho) / delta})$ kvantfrågor (under milda antaganden om $rho$). Detta förbättrar kvadratiskt beroendet av $1/delta$ och $log(1/rho)$ jämfört med en enkel tillämpning av amplituduppskattning. För att få det förbättrade $log(1/rho)$-beroendet använder vi det första resultatet.

► BibTeX-data

@artikel{vanApeldoorn2024basicquantum, doi = {10.22331/q-2024-03-14-1284}, url = {https://doi.org/10.22331/q-2024-03-14-1284}, title = {Grundläggande kvantsubrutiner: hitta flera markerade element och summera siffror}, författare = {van Apeldoorn, Joran och Gribling, Sander och Nieuwboer, Harold}, journal = {{Quantum}}, issn = {2521-327X}, utgivare = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volym = {8}, sidor = {1284}, månad = mar, år = {2024} }

► Referenser

[1] Srinivasan Arunachalam och Ronald de Wolf. Optimera antalet grindar i kvantsökning. Kvantinformation. 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 och P. Jodrá. Exakt Kolmogorov och totala variationsavstånd mellan några bekanta diskreta distributioner. 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 och Ronald de Wolf. Kvantalgoritmer för matrisskalning och matrisbalansering. I Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP'21), volym 198, sidorna 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 och Patrick Rall. Kvant ungefärlig räkning, förenklat. I Symposium on Simplicity in Algorithms, sidorna 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 och Alain Tapp. Snäva gränser för kvantsökning. Fortschritte der Physik, 46(4–5):493–505, 1998. Tidigare version i Physcomp'96. arXiv:quant-ph/9605034.
arXiv: kvant-ph / 9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf och Christof Zalka. Gränser för små-fel och noll-fel kvantalgoritmer. I 40th Annual Symposium on Foundations of Computer Science (FOCS'99), sidorna 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca och Alain Tapp. Kvantamplitudförstärkning och uppskattning. I Quantum Computation and Quantum Information: A Millennium Volume, volym 305 av Contemporary Mathematics, sidorna 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 och Paul Zimmermann. Modern Computer Arithmetic, volym 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even och Oded Goldreich. Nedre gränser för samplingsalgoritmer för att uppskatta medelvärdet. Information Processing Letters, 53(1):17–25, januari 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 och Leonard Wossnig. Kvantmaskininlärning: ett klassiskt 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 och Clifford Stein. Introduktion till algoritmer. MIT Press, 4:e upplagan, 2022.

[12] P. Diaconis och D. Freedman. Finita utbytbara 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 och Peter Høyer. En kvantalgoritm för att hitta minimum, 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 och Mehdi Mhalla. Quantum Query-komplexiteten hos vissa grafproblem. SIAM Journal on Computing, 35(6):1310–1328, januari 2006. doi:10.1137/050644719.
https: / / doi.org/ 10.1137 / 050644719

[15] Paul Dagum, Richard Karp, Michael Luby och Sheldon Ross. En optimal algoritm för Monte Carlo-uppskattning. SIAM Journal on Computing, 29(5):1484–1496, januari 2000. doi:10.1137/S0097539797315306.
https: / / doi.org/ 10.1137 / S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd och 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 och Harold Nieuwboer. Förbättrade nedre och övre kvantgränser för matrisskalning. I Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22), volym 219, sid 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 och Ronald de Wolf. Om kvantversioner av Yao-principen. I 19th Symposium on Theoretical Aspects of Computer Science (STACS'02), volym 2285 av Lecture Notes in Computer Science, sidorna 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. En snabb kvantmekanisk algoritm för databassökning. I Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC'96), sidorna 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. Ett ramverk för snabba kvantmekaniska algoritmer. I Proceedings of the Thirtionth Annual ACM Symposium on the Theory of Computing (STOC'98), sidorna 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. Quantum Sub-Gaussisk medelvärdesskattare. I 29th Annual European Symposium on Algorithms (ESA 2021), volym 204 av Leibniz International Proceedings in Informatics (LIPIcs), sidorna 50:1–50:17, 2021. doi:10.4230/LIPIcs.ESA.2021.50.
https: / / doi.org/ 10.4230 / LIPIcs.ESA.2021.50

[23] Svante Janson. Svansgränser för summor av geometriska och exponentiella 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. Konsten att programmera, volym III. Addison-Wesley, 2:a upplagan, 1998. URL: https://www.worldcat.org/oclc/312994415.
https:///www.worldcat.org/oclc/312994415

[25] Robin Kothari och Ryan O'Donnell. Genomsnittlig uppskattning när du har källkoden; eller, quantum Monte Carlo metoder. I Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'23), sidorna 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https: / / doi.org/ 10.1137 / 1.9781611977554.ch44

[26] Michael A. Nielsen och Isaac L. Chuang. Kvantberäkning och kvantinformation. Cambridge University Press, 2002.

[27] Ashwin Nayak och Felix Wu. Kvantfrågekomplexiteten för att approximera medianen och relaterad statistik. I Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC'99), sidorna 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. Binomial Approximation till Poisson Binomial Distribution: The Krawtchouk Expansion. 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

Citerad av

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.