Quantum data structure for range minimum query
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., 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 .
Fields of Study & Subjects
Quantum Computing Algorithms and Architecture
Complexity and Algorithms in Graphs
Quantum Information and Cryptography
Publication details
- Journal / source
- Journal of Computer and System Sciences
- Volume
- 157
- Pages
- 103756–103756
- Publication date
- 8 January 2026
- Language
- EN