{"id":"arxiv/2601.13195","url":"https://arxiv.org/abs/2601.13195","tags":["quant-ph","cs.DS"],"score":0,"title":"Quantum Data Structure for Range Minimum Query","domain":"quant-ph","source":"arxiv","authors":["Qisheng Wang","Zhean Xu","Zhicheng Zhang"],"reviews":0,"subject":"quant-ph","summary":"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., $\\operatorname{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 $\\widetilde Θ(\\sqrt{nq})$ for performing $q = O(n)$ operations without preprocessing, compared to the classical $\\widetildeΘ(n+q)$. As an application, we obtain a time-efficient quantum algorithm for $k$-minimum…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-19","reactions":{}}