Basic quantum subroutines: finding multiple marked elements and summing numbers

Quantum 8, 1284 (2024).

https://doi.org/10.22331/q-2024-03-14-1284

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.