Quantum data structure for range minimum query

Qisheng Wang, Zhean Xu, Zhicheng Zhang

TL;DR

This paper introduces a novel quantum data structure for the Range Minimum Query (RMQ) problem, achieving an optimal query complexity of $\Theta(\sqrt{nq})$ for $q$ operations on an array of size $n$. Crucially, this quantum solution does not require Quantum Random Access Memory (QRAM), a significant practical advantage.

What Problem Does This Paper Address?

The Range Minimum Query (RMQ) problem is a fundamental task in computer science: given an array, efficiently find the index of the minimum element within any specified range. This problem has wide-ranging applications in areas like text processing and graph algorithms. While classical solutions exist, they often have a time complexity of $O(n + q \log n)$ or $O(n + q \log n / \log \log n)$ for $q$ operations. The authors investigate whether quantum computing can offer a significant speedup for RMQ, particularly in the context of dynamic updates to the array. A key challenge in quantum algorithms is the frequent reliance on QRAM, which is currently expensive and difficult to implement. This paper aims to develop a QRAM-free quantum data structure for RMQ that achieves a better time complexity than classical methods.

Methods

The paper proposes a quantum data structure for RMQ that leverages a segment tree framework. To achieve QRAM-free operation and improved efficiency, they introduce two novel techniques:

  • Top-down completion: Instead of pre-processing the entire segment tree, nodes are created and initialized on demand as operations are performed. This is done using a quantum minimum finding algorithm.
  • Lazy node creation: This technique ensures that nodes are created and initialized only when they are actually needed during a query or modification. This is managed through a quantum pushdown procedure.

The core quantum primitive used is a quantum minimum finding algorithm, which is applied to initialize nodes. The overall algorithm is a hybrid quantum-classical approach, where quantum computations are used for specific tasks (like finding minimums), and classical computations manage the overall structure and logic.

Datasets

Not discussed in the paper. The paper deals with an abstract array of elements from a totally ordered set, not specific datasets.

Key Insights and Ideas

  • Breaking the classical barrier: The paper demonstrates that quantum computing can indeed break the $O(n+q)$ barrier for RMQ with updates, achieving a $\Theta(\sqrt{nq})$ query complexity. This is a significant theoretical advancement.
  • QRAM-free quantum algorithms: The development of an efficient quantum RMQ data structure without QRAM is a major practical contribution. This makes the proposed algorithm more feasible for near-term quantum devices.
  • Novel segment tree techniques: The introduction of "top-down completion" and "lazy node creation" are key innovations that allow the quantum algorithm to efficiently manage the segment tree structure without full pre-processing.
  • Application to k-minimum finding: The quantum RMQ data structure is used to derive a QRAM-free quantum algorithm for the k-minimum finding problem, which is itself a crucial subroutine in many other quantum algorithms.

Key Results

  • Optimal Quantum RMQ: The paper establishes an optimal quantum query complexity of $\Theta(\sqrt{nq})$ for RMQ with $q$ operations on an array of size $n$. This is achieved by a quantum data structure that supports initialization, queries, and range modifications.
  • Time Complexity: The proposed quantum algorithm has a time complexity of $O(\sqrt{nq} \log(q \log n / \varepsilon) \log n)$, where $\varepsilon$ is the error parameter. This is significantly faster than classical algorithms for certain ranges of $n$ and $q$.
  • Quantum k-minimum finding: A QRAM-free quantum algorithm for k-minimum finding is presented with query complexity $O(\sqrt{nk} \log(k \log n / \varepsilon))$ and time complexity $O(\sqrt{nk} \log(k \log n / \varepsilon) \log n)$.

Limitations and Future Work

  • Logarithmic factors: The authors pose a question about whether the logarithmic factors in the query/time complexity can be further reduced, suggesting that adopting modern classical data structures might be a path forward.
  • Multidimensional RMQ: The paper mentions that multidimensional RMQ is an area of active research in classical computing and suggests that exploring quantum speedups for these problems would be an interesting direction.
  • Generalizing quantum data structures: The authors hope that their work on reducing QRAM requirements will inspire other quantum algorithms that can operate without QRAM.

Summary updated

BibTeX
@article{wang2026quantum,
  author = {Qisheng Wang and Zhean Xu and Zhicheng Zhang},
  title = {{Quantum data structure for range minimum query}},
  journal = {J. Comput. Syst. Sci.},
  year = {2026},
  doi = {10.1016/j.jcss.2026.103756},
}
Figure