Basic quantum subroutines: finding multiple marked elements and summing numbers

Abstract

We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(\sqrt{Nk})$ 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.

arXiv comment29 pages, accepted in Quantum

References in corpus (9)

• Quantum random access memory
• Tight bounds on quantum searching
• Quantum machine learning: a classical perspective
• A Quantum Algorithm for Finding the Minimum
• Quantum Approximate Counting, Simplified
• Quantum query complexity of some graph problems
• Quantum Sub-Gaussian Mean Estimator
• Fast quantum algorithms for numerical integrals and stochastic processes
• Quantum Telecomputation

Cited by in corpus (1)

• Quantum Data Structure for Range Minimum Query