.png){kind=icon}
.png){kind=icon}
Return
Quantum data structure for range minimum query
.png){kind=icon}
OA
AI
DOI：10.1016/j.jcss.2026.103756.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 is an element of[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 (Theta) over tilde(root nq) for performing q = O(n) operations without preprocessing, compared to the classical (Theta) over tilde (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. (c) 2026 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Quantum computing
Quantum algorithms
Quantum data structures
Range minimum query
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
J
IF:
0.9
Papers:
51
Citations:
4.5K
Organization
View more organizations