Abstract
Given an array a[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..r], i.e., argmin_i ∈ [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 Θ(√nq) for performing q = O(n) operations without preprocessing, compared to the classical Θ(n+q). As an application, we obtain a time-efficient quantum algorithm for k-minimum finding without the use of quantum random access memory.