A Quantum Algorithm for Finding $k$-Minima

Kohei Miyamoto, Masakazu Iwamura, Koichi Kise

We propose a new finding $k$-minima algorithm and prove that its query complexity is $\mathcal{O}(\sqrt{kN})$, where $N$ is the number of data indices. Though the complexity is equ…