Quantum Data Structure for Range Minimum Query

Abstract

Given an array $a[\mathrm{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., ${\mathrm{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 $\tilde{\Theta }(\sqrt{nq})$ for performing $q=O(n)$ operations without preprocessing, compared to the classical $\tilde{\Theta }(n+q)$. As an application, we obtain a time-efficient quantum algorithm for $k$-minimum finding without the use of quantum random access memory.

24 pages, 2 tables, 1 figure, 5 algorithms

References in corpus (13)

• Quantum algorithm for solving linear systems of equations
• Quantum random access memory
• Quantum machine learning: a classical perspective
• Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
• Quantum query complexity of some graph problems
• Quantum SDP-Solvers: Better upper and lower bounds
• Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
• Nested Quantum Walks with Quantum Data Structures
• Tower: Data Structures in Quantum Superposition
• Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
• Quantum Algorithm for Lexicographically Minimal String Rotation
• Preparing Many Copies of a Quantum State in the Black-Box Model
• Basic quantum subroutines: finding multiple marked elements and summing numbers