{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T16:54:32Z","timestamp":1769964872565,"version":"3.49.0"},"reference-count":29,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["OCENW.KLEIN.267"],"award-info":[{"award-number":["OCENW.KLEIN.267"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["101040907"],"award-info":[{"award-number":["101040907"]}]},{"name":"European Research Council","award":["81876432"],"award-info":[{"award-number":["81876432"]}]},{"DOI":"10.13039\/100008398","name":"VILLUM FONDEN","doi-asserted-by":"crossref","award":["10059"],"award-info":[{"award-number":["10059"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["024.003.037"],"award-info":[{"award-number":["024.003.037"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003246","name":"Dutch Research Council","doi-asserted-by":"crossref","award":["QuantumDelta NL"],"award-info":[{"award-number":["QuantumDelta NL"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"We show how to find allk<\/mml:mi><\/mml:math>marked elements in a list of sizeN<\/mml:mi><\/mml:math>using the optimal numberO<\/mml:mi>(<\/mml:mo>N<\/mml:mi>k<\/mml:mi><\/mml:msqrt>)<\/mml:mo><\/mml:math>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 factork<\/mml:mi><\/mml:math>overhead in the gate complexity, or had an extra factorlog<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>k<\/mml:mi>)<\/mml:mo><\/mml:math>in the query complexity.We then consider the problem of finding a multiplicative&#x03B4;<\/mml:mi><\/mml:math>-approximation ofs<\/mml:mi>=<\/mml:mo>&#x2211;<\/mml:mo>i<\/mml:mi>=<\/mml:mo>1<\/mml:mn><\/mml:mrow>N<\/mml:mi><\/mml:munderover>v<\/mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math>wherev<\/mml:mi>=<\/mml:mo>(<\/mml:mo>v<\/mml:mi>i<\/mml:mi><\/mml:msub>)<\/mml:mo>&#x2208;<\/mml:mo>[<\/mml:mo>0<\/mml:mn>,<\/mml:mo>1<\/mml:mn>]<\/mml:mo>N<\/mml:mi><\/mml:msup><\/mml:math>, given quantum query access to a binary description ofv<\/mml:mi><\/mml:math>. We give an algorithm that does so, with probability at least1<\/mml:mn>&#x2212;<\/mml:mo>&#x03C1;<\/mml:mi><\/mml:math>, usingO<\/mml:mi>(<\/mml:mo>N<\/mml:mi>log<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03C1;<\/mml:mi>)<\/mml:mo>\/<\/mml:mo><\/mml:mrow>&#x03B4;<\/mml:mi><\/mml:msqrt>)<\/mml:mo><\/mml:math>quantum queries (under mild assumptions on&#x03C1;<\/mml:mi><\/mml:math>). This quadratically improves the dependence on1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03B4;<\/mml:mi><\/mml:math>andlog<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03C1;<\/mml:mi>)<\/mml:mo><\/mml:math>compared to a straightforward application of amplitude estimation. To obtain the improvedlog<\/mml:mi>&#x2061;<\/mml:mo>(<\/mml:mo>1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03C1;<\/mml:mi>)<\/mml:mo><\/mml:math>dependence we use the first result.<\/jats:p>","DOI":"10.22331\/q-2024-03-14-1284","type":"journal-article","created":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T13:41:55Z","timestamp":1710423715000},"page":"1284","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":3,"title":["Basic quantum subroutines: finding multiple marked elements and summing numbers"],"prefix":"10.22331","volume":"8","author":[{"given":"Joran","family":"van Apeldoorn","sequence":"first","affiliation":[{"name":"IViR and QuSoft, University of Amsterdam, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6817-2971","authenticated-orcid":false,"given":"Sander","family":"Gribling","sequence":"additional","affiliation":[{"name":"Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3627-3636","authenticated-orcid":false,"given":"Harold","family":"Nieuwboer","sequence":"additional","affiliation":[{"name":"Korteweg\u2013de 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"}]}],"member":"9598","published-online":{"date-parts":[[2024,3,14]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Srinivasan Arunachalam and Ronald de Wolf. Optimizing the number of gates in quantum search. Quantum Info. Comput., 17(3-4):251\u2013261, 2017. doi:10.26421\/qic17.3-4.","DOI":"10.26421\/qic17.3-4"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Jos\u00e9 A. Adell and P. Jodr\u00e1. Exact Kolmogorov and total variation distances between some familiar discrete distributions. Journal of Inequalities and Applications, 2006(1):1\u20138, 2006. doi:10.1155\/JIA\/2006\/64307.","DOI":"10.1155\/JIA\/2006\/64307"},{"key":"2","doi-asserted-by":"publisher","unstructured":"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\u2013110:17, 2021. arXiv:2011.12823, doi:10.4230\/LIPIcs.ICALP.2021.110.","DOI":"10.4230\/LIPIcs.ICALP.2021.110"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Patrick Rall. Quantum approximate counting, simplified. In Symposium on Simplicity in Algorithms, pages 24\u201332, 2020. doi:10.1137\/1.9781611976014.5.","DOI":"10.1137\/1.9781611976014.5"},{"key":"4","doi-asserted-by":"crossref","unstructured":"Michel Boyer, Gilles Brassard, Peter H\u00f8yer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4\u20135):493\u2013505, 1998. Earlier version in Physcomp'96. arXiv:quant-ph\/9605034.","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"5","doi-asserted-by":"crossref","unstructured":"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\u2013368. IEEE Computer Society, 1999.","DOI":"10.1109\/SFFCS.1999.814607"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, 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\u201374. American Mathematical Society, 2002. doi:10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P.","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"7","doi-asserted-by":"crossref","unstructured":"Richard Brent and Paul Zimmermann. Modern Computer Arithmetic, volume 18. Cambridge University Press, 2010.","DOI":"10.1017\/CBO9780511921698"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Ran Canetti, Guy Even, and Oded Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters, 53(1):17\u201325, January 1995. doi:10.1016\/0020-0190(94)00171-T.","DOI":"10.1016\/0020-0190(94)00171-T"},{"key":"9","doi-asserted-by":"publisher","unstructured":"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.","DOI":"10.1098\/rspa.2017.0551"},{"key":"10","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022."},{"key":"11","doi-asserted-by":"crossref","unstructured":"P. Diaconis and D. Freedman. Finite Exchangeable Sequences. The Annals of Probability, 8(4):745\u2013764, 1980. URL: https:\/\/www.jstor.org\/stable\/2242823.","DOI":"10.1214\/aop\/1176994663"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Christoph D\u00fcrr and Peter H\u00f8yer. A quantum algorithm for finding the minimum, 1996. doi:10.48550\/arXiv.quant-ph\/9607014.","DOI":"10.48550\/arXiv.quant-ph\/9607014"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Christoph D\u00fcrr, Mark Heiligman, Peter H\u00f8yer, and Mehdi Mhalla. Quantum Query Complexity of Some Graph Problems. SIAM Journal on Computing, 35(6):1310\u20131328, January 2006. doi:10.1137\/050644719.","DOI":"10.1137\/050644719"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Paul Dagum, Richard Karp, Michael Luby, and Sheldon Ross. An Optimal Algorithm for Monte Carlo Estimation. SIAM Journal on Computing, 29(5):1484\u20131496, January 2000. doi:10.1137\/S0097539797315306.","DOI":"10.1137\/S0097539797315306"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100(16), apr 2008. doi:10.1103\/physrevlett.100.160501.","DOI":"10.1103\/physrevlett.100.160501"},{"key":"16","doi-asserted-by":"publisher","unstructured":"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\u201335:23, 2022. arXiv:2109.15282, doi:10.4230\/LIPIcs.STACS.2022.35.","DOI":"10.4230\/LIPIcs.STACS.2022.35"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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\u2013358, Berlin, Heidelberg, 2002. Springer. doi:10.1007\/3-540-45841-7_28.","DOI":"10.1007\/3-540-45841-7_28"},{"key":"18","doi-asserted-by":"publisher","unstructured":"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\u2013219, 1996. arXiv:quant-ph\/9605043, doi:10.1145\/237814.237866.","DOI":"10.1145\/237814.237866"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Lov K. Grover. Quantum telecomputation, 1997. Bell Labs Technical Memorandum ITD97-31630F. doi:10.48550\/arXiv.quant-ph\/9704012.","DOI":"10.48550\/arXiv.quant-ph\/9704012"},{"key":"20","doi-asserted-by":"publisher","unstructured":"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\u201362, 1998. arXiv:quant-ph\/9711043, doi:10.1145\/276698.276712.","DOI":"10.1145\/276698.276712"},{"key":"21","doi-asserted-by":"publisher","unstructured":"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\u201350:17, 2021. doi:10.4230\/LIPIcs.ESA.2021.50.","DOI":"10.4230\/LIPIcs.ESA.2021.50"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Svante Janson. Tail bounds for sums of geometric and exponential variables. Statistics & Probability Letters, 135:1\u20136, 2018. doi:10.1016\/j.spl.2017.11.017.","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"23","unstructured":"Donald Ervin Knuth. The Art of Computer Programming, volume III. Addison-Wesley, 2nd edition, 1998. URL: https:\/\/www.worldcat.org\/oclc\/312994415."},{"key":"24","doi-asserted-by":"publisher","unstructured":"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\u20131215, 2023. doi:10.1137\/1.9781611977554.ch44.","DOI":"10.1137\/1.9781611977554.ch44"},{"key":"25","doi-asserted-by":"crossref","unstructured":"Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, 2002.","DOI":"10.1119\/1.1463744"},{"key":"26","doi-asserted-by":"publisher","unstructured":"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\u2013393, 1999. arXiv:quant-ph\/9804066, doi:10.1145\/301250.301349.","DOI":"10.1145\/301250.301349"},{"key":"27","doi-asserted-by":"publisher","unstructured":"B. Roos. Binomial Approximation to the Poisson Binomial Distribution: The Krawtchouk Expansion. Theory of Probability & Its Applications, 45(2):258\u2013272, 2001. doi:10.1137\/S0040585X9797821X.","DOI":"10.1137\/S0040585X9797821X"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Robert M. Young. 75.9 Euler's Constant. The Mathematical Gazette, 75(472):187\u2013190, 1991. doi:10.2307\/3620251.","DOI":"10.2307\/3620251"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-03-14-1284\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,11,14]],"date-time":"2024-11-14T09:07:58Z","timestamp":1731575278000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-03-14-1284\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,14]]},"references-count":29,"URL":"https:\/\/doi.org\/10.22331\/q-2024-03-14-1284","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,14]]},"article-number":"1284"}}