Basic quantum subroutines: finding multiple marked elements and summing numbers

Joran van Apeldoorn, Sander Gribling, Harold Nieuwboer

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 comple…