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.
Journal reference
Journal of Computer and System Sciences, 157: 103756, 2026
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., argmini∈[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 Θ(nq) for performing q=O(n) operations without preprocessing, compared to the classical Θ(n+q). As an application, we obtain a time-efficient quantum algorithm for k-minimum finding without the use of quantum random access memory.
Quantum computing is a popular topic in computer science, which has recently attracted many studies in various areas such as machine learning and network. However, the topic of quantum data structures seems neglected. There is an open problem in the database area: Can we improve existing data structures by quantum techniques? Consider a dataset of key-record pairs. Given an interval as a query range, a classical B+ tree can report all the records with keys within this interval, which is called a range query, in O(log N + k) time, where N is the total number of records and k is the output size. It is asymptotically optimal in a classical computer but not efficient enough in a quantum computer, because it is expected that the execution time and the output size are linear in a quantum computer. In this paper, we propose the quantum range query problem. Different from the classical range queries, a quantum range query returns the results in quantum bits, which has broad potential applications due to the foreseeable advance of quantum computers and quantum algorithms. To the best of our knowledge, we design the first tree-like quantum data structure called the quantum B+ tree. Based on this data structure, we propose a hybrid quantum-classical algorithm to do the range search. It answers a static quantum range query in O(log_B N) time, which is asymptotically optimal in quantum computers. Since the execution time does not depend on the output size (i.e., k, which could be as large as O(N)), it is significantly faster than the classical data structure. Moreover, we extend our quantum B+ tree to answer the dynamic and d-dimensional quantum range queries efficiently in O(log^2_B N) and O(log^d_B N) time, respectively. Our experimental results show that our proposed quantum data structures achieve up to 1000x improvement in the number of memory accesses compared to their classical competitors.
Abstract Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and performs an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts.
Finding the minimum value in an unordered database is a common and fundamental task in computer science. However, the optimal classical deterministic algorithm can find the minimum value with a time complexity that grows linearly with the number of elements in the database. In this paper, we present the proposal of a quantum algorithm for finding the minimum value of a database, which is quadratically faster than its best classical analogs. We assume a Quantum Random Access Memory (QRAM) that stores values from a database and perform an iterative search based on an oracle whose role is to limit the searched values by controlling the states of the most significant qubits. A complexity analysis was performed in order to demonstrate the advantage of this quantum algorithm over its classical counterparts. Furthermore, we demonstrate how the proposed algorithm would be used in an unsupervised machine learning task through a quantum version of the K-means algorithm.
Range query is a fundamental task in geospatial data search and many other downstream applications. Classic range queries often rely on tree-based spatial indexes, of which the query speed depends on the number of indexed points k within the queried range. For instance, a classical B+ tree answers a range query in O(log N + k). For a long time, this speed has long been considered asymptotically optimal in classic database systems, until the recent emergence of quantum computing, where a quantum B+ tree may requires only O(log BN). This paper presents Quantum Range Query (QRQ) via a hybrid quantum-classic algorithm to return the range query results in quantum superpositions. In this context, QRQ is designed to accelerate classic range query on spatial-temporal-semantic trajectory geodata using quantum algorithms. Specifically, QRQ develops quantum variants of R-tree, TB-tree and KD-tree, where the physical slots of a node, including unused padding slots, are treated as an array that a quantum random-access memory (QRAM) can read in superpositions. Evaluations on three common trajectory datasets, namely GeoLife, T-Drive, and GDP Drifter, and 10, 000 queries per setting, the QRQ speedup at 1% target selectivity ranges from 2.03 × to 64.70 ×. More importantly, QRQ shows a great potential in optimizing existing trajectory range query, so it becomes the shared primitive on which human mobility analysis, and later searches specified by large language models (LLMs) and geo-foundation models (GeoFMs), can rest.
The minimum cut problem in an undirected and weighted graph G is to find the minimum total weight of a set of edges whose removal disconnects G. We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If G has n vertices and edge weights at least 1 and at most τ, we give a quantum algorithm to solve the minimum cut problem using O~(n3/2τ) queries and time. Moreover, for every integer 1≤τ≤n we give an example of a graph G with edge weights 1 and τ such that solving the minimum cut problem on G requires Ω(n3/2τ) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where Ω(n2) queries to the adjacency matrix are needed in the worst case even to decide if an unweighted graph is connected or not. In the adjacency array model, when G has m edges the classical randomized complexity of the minimum cut problem is Θ~(m). We show that the quantum query and time complexity are O~(mnτ) and O~(mnτ+n3/2), respectively, where again the edge weights are between 1 and τ. For dense graphs we give lower bounds on the quantum query complexity of Ω(n3/2) for τ>1 and Ω(τn) for any 1≤τ≤n. Our query algorithm uses a quantum algorithm for graph sparsification by Apers and de Wolf (FOCS 2020) and results on the structure of near-minimum cuts by Kawarabayashi and Thorup (STOC 2015) and Rubinstein, Schramm and Weinberg (ITCS 2018). Our time efficient implementation builds on Karger's tree packing technique (STOC 1996).
We consider the problem of finding the minimum element in a list of length N using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least α by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than α, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time O~(N(1+Δ)), where Δ is an upper-bound on the number of elements within the interval α, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of N known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution O(ε)-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from O(N2) to O(N), in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is O~(N(1+Δ)), with the same O(logN) sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.