Quantum data structure for range minimum query

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., arg min 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 Θ ˜ ( n q ) for performing q = O ( n ) operations without preprocessing, compared to the classical Θ ˜ ( n + q ) . 1 As an application, we obtain a time-efficient quantum algorithm for k -minimum finding without the use of quantum random access memory .