Basic quantum subroutines: finding multiple marked elements and summing numbers

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 \&\#x2061;(k)$ in the query complexity.We then consider the problem of finding a multiplicative $\mathrm{\&\#x03B4;}$ -approximation of $s=\underset{i=1}{\overset{N}{\&\#x2211;}}{v}_i$ where $v=(v_i)\&\#x2208;[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\&\#x2212;\mathrm{\&\#x03C1;}$ , using $O(\sqrt{N\log \&\#x2061;(1/\mathrm{\&\#x03C1;})/\mathrm{\&\#x03B4;}})$ quantum queries (under mild assumptions on $\mathrm{\&\#x03C1;}$ ). This quadratically improves the dependence on $1/\mathrm{\&\#x03B4;}$ and $\log \&\#x2061;(1/\mathrm{\&\#x03C1;})$ compared to a straightforward application of amplitude estimation. To obtain the improved $\log \&\#x2061;(1/\mathrm{\&\#x03C1;})$ dependence we use the first result.