Basic Quantum Subroutines: Finding Multiple Marked Elements And Summing Numbers

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

¹IViR and QuSoft, University of Amsterdam, The Netherlands
²Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands
³Korteweg–de Vries Institute for Mathematics and QuSoft, University of Amsterdam, The Netherlands and Faculty of Computer Science, Ruhr University Bochum, Germany and Department of Mathematical Sciences, University of Copenhagen, Denmark

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrt{N k})$ of quantum queries and only a polylogarithmic overhead in the gate complexity, in the setting where one has a small quantum memory. Previous algorithms either incurred a factor $k$ overhead in the gate complexity, or had an extra factor $log(k)$ in the query complexity.
We then consider the problem of finding a multiplicative $delta$-approximation of $s = sum_{i=1}^N v_i$ where $v=(v_i) in [0,1]^N$, given quantum query access to a binary description of $v$. We give an algorithm that does so, with probability at least $1-rho$, using $O(sqrt{N log(1/rho) / delta})$ quantum queries (under mild assumptions on $rho$). This quadratically improves the dependence on $1/delta$ and $log(1/rho)$ compared to a straightforward application of amplitude estimation. To obtain the improved $log(1/rho)$ dependence we use the first result.

► BibTeX data

@article{vanApeldoorn2024basicquantum, doi = {10.22331/q-2024-03-14-1284}, url = {https://doi.org/10.22331/q-2024-03-14-1284}, title = {Basic quantum subroutines: finding multiple marked elements and summing numbers}, author = {van Apeldoorn, Joran and Gribling, Sander and Nieuwboer, Harold}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {8}, pages = {1284}, month = mar, year = {2024} }

► References

[1] Srinivasan Arunachalam and Ronald de Wolf. Optimizing the number of gates in quantum search. Quantum 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 and P. Jodrá. Exact Kolmogorov and total variation distances between some familiar discrete distributions. 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, and Ronald de Wolf. Quantum algorithms for matrix scaling and matrix balancing. In Proceedings of 48th International Colloquium on Automata, Languages, and Programming (ICALP’21), volume 198, pages 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 and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity in Algorithms, pages 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, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4–5):493–505, 1998. Earlier version in Physcomp’96. arXiv:quant-ph/9605034.
arXiv:quant-ph/9605034

[6] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for small-error and zero-error quantum algorithms. In 40th Annual Symposium on Foundations of Computer Science (FOCS’99), pages 358–368. IEEE Computer Society, 1999.

[7] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics, pages 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 and Paul Zimmermann. Modern Computer Arithmetic, volume 18. Cambridge University Press, 2010.

[9] Ran Canetti, Guy Even, and Oded Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters, 53(1):17–25, January 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, and Leonard Wossnig. Quantum machine learning: a classical perspective. 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, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022.

[12] P. Diaconis and D. Freedman. Finite Exchangeable Sequences. 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 and Peter Høyer. A quantum algorithm for finding the 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, and Mehdi Mhalla. Quantum Query Complexity of Some Graph Problems. SIAM Journal on Computing, 35(6):1310–1328, January 2006. doi:10.1137/050644719.
https://doi.org/10.1137/050644719

[15] Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. An Optimal Algorithm for Monte Carlo Estimation. SIAM Journal on Computing, 29(5):1484–1496, January 2000. doi:10.1137/S0097539797315306.
https://doi.org/10.1137/S0097539797315306

[16] Vittorio Giovannetti, Seth Lloyd, and 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 and Harold Nieuwboer. Improved quantum lower and upper bounds for matrix scaling. In Proceedings of 39th International Symposium on Theoretical Aspects of Computer Science (STACS’22), volume 219, pages 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 and Ronald de Wolf. On Quantum Versions of the Yao Principle. In 19th Symposium on Theoretical Aspects of Computer Science (STACS’02), volume 2285 of Lecture Notes in Computer Science, pages 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. A fast quantum mechanical algorithm for database search. In Proceedings of 38th Annual ACM Symposium on Theory of Computing (STOC’96), pages 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 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] Lov K. Grover. A framework for fast quantum mechanical algorithms. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing (STOC’98), pages 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. Quantum Sub-Gaussian Mean Estimator. In 29th Annual European Symposium on Algorithms (ESA 2021), volume 204 of Leibniz International Proceedings in Informatics (LIPIcs), pages 50:1–50:17, 2021. doi:10.4230/LIPIcs.ESA.2021.50.
https://doi.org/10.4230/LIPIcs.ESA.2021.50

[23] Svante Janson. Tail bounds for sums of geometric and exponential variables. 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. The Art of Computer Programming, volume III. Addison-Wesley, 2nd edition, 1998. URL: https://www.worldcat.org/oclc/312994415.
https://www.worldcat.org/oclc/312994415

[25] Robin Kothari and Ryan O’Donnell. Mean estimation when you have the source code; or, quantum Monte Carlo methods. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’23), pages 1186–1215, 2023. doi:10.1137/1.9781611977554.ch44.
https://doi.org/10.1137/1.9781611977554.ch44

[26] Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2002.

[27] Ashwin Nayak and Felix Wu. The quantum query complexity of approximating the median and related statistics. In Proceedings of the 31st Annual ACM SIGACT Symposium on Theory of Computing (STOC’99), pages 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 Approximation to the 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 Euler’s Constant. The Mathematical Gazette, 75(472):187–190, 1991. doi:10.2307/3620251.
https://doi.org/10.2307/3620251

Cited by

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.

Generative Data Intelligence

Basic quantum subroutines: finding multiple marked elements and summing numbers

Abstract

► BibTeX data

► References

Cited by

Drake Threatened With Lawsuit Over Tupac AI Vocals

Shiba Inu Leads in Robinhood’s Crypto Performance

Latest Intelligence

DOJ Disputes Roman Storm’s Characterization of Tornado Cash Operations in New Filing

Top 5 Crypto Presales: BDAG Leads the Pack with 30,000x ROI Potential

Forbes Unveils 20 Crypto ‘Zombies,’ Declares Ripple And XRP Among The Undead

Consob, Italy’s Watchdog, Bans Additional Forex And Cryptocurrency Trading Websites – CryptoInfoNet

Fed’s Inflation Gauge Heats Up, Rate Cuts on Hold as Bitcoin and Stocks Slide

Explore Top 6 Cryptos for 2024: BlockDAG Leads with Unprecedented ROI Potential

Chat with us