Quantum Data Structure for Range Minimum Query

• URL: http://arxiv.org/abs/2601.13195v1
• Date: Mon, 19 Jan 2026 16:19:44 GMT
• Title: Quantum Data Structure for Range Minimum Query
• Authors: Qisheng Wang, Zhean Xu, Zhicheng Zhang,
• Abstract summary: We propose a quantum data structure that supports RMQ queries and range updates.<n>We obtain a time-efficient quantum algorithm for $k$-minimum finding without the use of quantum random access memory.
• Score: 30.186099880107964
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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., $\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 finding without the use of quantum random access memory.

Related papers

• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  A Multinomial Logit (MNL) model is composed of a finite universe of items $[n]=1,..., n$, each assigned a positive weight.<n>A query specifies an admissible subset -- called a slate -- and the model chooses one item from that slate with probability proportional to its weight.<n>This query model is also known as the Plackett-Luce model or conditional sampling oracle in the literature.
  arXiv  Detail & Related papers  (2026-01-07T22:07:44Z)
• Quantum Search on Computation Trees [0.0]
  We show a generalization of the quantum walk algorithm for search in backtracking trees by Montanaro (ToC)<n>This framework provides an easy and convenient way to re-obtain a number of other quantum frameworks like variable time search, quantum divide & conquer and bomb query algorithms.
  arXiv  Detail & Related papers  (2025-05-28T14:35:18Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• On the exact quantum query complexity of $\ ext{MOD}_m^n$ and $\ ext{EXACT}_{k,l}^n$ [4.956977275061968]
  We present an exact quantum algorithm for computing $textMOD_mn$. We show exact quantum query complexity of a broad class of symmetric functions that map $0,1n$ to a finite set $X$ is less than $n$.
  arXiv  Detail & Related papers  (2023-03-20T08:17:32Z)
• Basic quantum subroutines: finding multiple marked elements and summing numbers [1.1265248232450553]
  We show how to find all $k$ marked elements in a list of size $N$ using the optimal number $O(sqrtN k)$ of quantum queries.
  arXiv  Detail & Related papers  (2023-02-20T19:11:44Z)
• Quantum divide and conquer [6.527258283771695]
  Divide-and-conquer framework is used extensively in classical algorithm design. We describe a quantum divide-and-conquer framework that, in certain cases, yields an analogous recurrence relation $$C_Q(n) leq sqrta, C_Q(n/b) + O(Ctextrmaux_Q(n))$$ that characterizes the quantum query complexity.
  arXiv  Detail & Related papers  (2022-10-12T17:14:28Z)
• Multidimensional Quantum Walks, with Application to $k$-Distinctness [0.5064404027153093]
  We give a new upper bound of $widetildeOleft(n3/4-1/4(2k-1)right)$ on the time complexity.<n>We show how to solve the welded trees problem in $O(n)$ queries and $O(n2)$ time using this new technique.
  arXiv  Detail & Related papers  (2022-08-29T10:51:56Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• Quantum Algorithm for Lexicographically Minimal String Rotation [5.905222176603487]
  Lexicographically minimal string rotation (LMSR) is a problem to find the minimal one among all rotations of a string in the lexicographical order. We propose an $O(n3/4)$ quantum query algorithm for LMSR.
  arXiv  Detail & Related papers  (2020-12-17T03:13:45Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.