Quantum Data Structure for Range Minimum Query

Given an array $a[\mathrm{1..}n]$, the Range Minimum Query (RMQ) problem is to maintain a data structure that supports RMQ queries: given a range $[l,r]$, find the index of the minimum element among $a[l\mathrm{.}\mathrm{.}r]$, i.e., ${\mathrm{argmin}}_{i\in [l,r]}a[i]$. In this paper, we propose a quantum data structure that supports RMQ queries and range updates, with an optimal time complexity $\tilde{\mathrm{\Theta }}(\sqrt{nq})$ for performing $q=O(n)$ operations without preprocessing, compared to the classical $\tilde{\mathrm{\Theta }}(n+q)$. As an application, we obtain a time-efficient quantum algorithm for $k$-minimum finding without the use of quantum random access memory.