CS Paper Radar

Towards Quantum Range Query for Spatial-Temporal-Semantic Trajectory Data

Hao Li, Zhihang Liu, Liwei Zou, Jinlin Wu, Wufan Zhao

cs.DB ·submitted 2026-08-28 08:33 UTC · v1
published

Abstract

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_B N). 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 times) to 64.70 times. 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.

Closest papers

Nearest neighbours by meaning across the whole index.

Hardness of Pathfinding in a Welded Tree

cs.CC quant-ph ·2026-09-17 ·David Miloschewsky, Supartha Podder
theory similarity 0.69
Abstract · 55 pages, 4 figures

Starting from the entrance of a welded tree, a quantum walk algorithm can find its exit vertex exponentially faster than any classical algorithm. However, it has been an open question whether any quantum algorithm is able to efficiently find a path from the entrance to the exit. We answer this by proving an exponential quantum query lower bound for finding such path. Specifically, for trees of height $n$, any quantum query algorithm requires at least $Ω(2^{n/24})$ queries in order to succeed with constant probability. Our proof uses the compressed permutation oracle technique in order to construct databases which track the graph information an algorithm has learned and forgotten, and show that no efficient quantum algorithm can build an entrance-to-exit path in these records.

0.29

QuarkDB: A Hybrid Database System for Quantum Data Management

cs.DB cs.AR ·2026-11-16 ·Wenrui Zhang, Yu Wang, Xiao Zhang
similarity 0.67
Abstract · 14 pages, 12 figures, Submitted to ICDE2027

Emerging quantum applications like quantum communication generate large volumes of high-dimensional quantum data, requiring efficient data analysis and storage. However, classical database systems often struggle to meet requirements such as quantum processing or version management. This paper presents QuarkDB designed for efficient quantum data management. QuarkDB establishes a unified object model for relational and quantum data and defines the syntax of Quantum Structured Query Language. To support efficient quantum data management, QuarkDB integrates three key components: (1) a Hybrid Query Engine with cost-based hybrid plan selection over classical and quantum operators, (2) an Execution Engine with a three-level instructions intermediate representation, QuarkDB-IR, to support quantum execution and reduce quantum processing costs, and (3) a Storage Engine supporting quantum data version management, state reconstruction and data reuse. Compared with classical databases such as SQLite and PostgreSQL or quantum databases like Qute, our QuarkDB achieves query-latency speedups ranging from 2.14x to 25.86x speedup under extensive real-world workloads.

0.20

Improving Join Order Optimization on Gate-Based Quantum Computers via Structured Parameter Initialization

cs.DB ·2026-08-21 ·Divya Shekar, Ruokun Wu, Dhanvi Bharadwaj, Gokul Subramanian Ravi, Lin Ma
published similarity 0.60
Abstract · VLDB 2026 Workshop:QC&DKM 2026 - 2nd Workshop on Quantum Computing and Data/Knowledge Management

Join Order Optimization (JOO) is one of the most computationally expensive tasks in relational query optimization due to the exponential growth of possible join plans with increasing query size. Recent work has explored quantum and quantum-inspired approaches for solving JOO by reformulating the problem as a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for optimization using quantum hardware. However, many existing approaches have limited scalability on current gate-based quantum devices. In addition, little work has investigated the role of initialization strategies in improving the performance of gate-based quantum optimization for database workloads. In this work, we investigate gate-based quantum join order optimization using the Quantum Approximate Optimization Algorithm (QAOA) initialized with Scalable Parameter Initialization for QAOA (SPIQ). SPIQ is used to efficiently identify high-quality initial points in the quantum solution landscape for QAOA executed on a gate-based quantum computer. We evaluate the interaction between QUBO encoding, SPIQ initialization, and gate-based optimization on small-scale join ordering problems involving 3 and 4 relations. Our results show that structured initialization improves optimization stability and increases convergence toward high-quality join plans compared to uninformed initialization approaches. Across these small-scale, simulation-based instances, SPIQ increases the sampling frequency of the optimal join order by up to approximately 5$\times$ and yields final-state energies significantly lower than a randomly initialized QAOA. Overall, this work enhances existing gate-based quantum optimization while providing an initial proof of concept for applying SPIQ initialization to database query optimization workloads.

0.24

A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds

cs.CC quant-ph ·2026-09-30 ·Paul Beame, Blake Holman, Niels Kornerup
theoryhot direction similarity 0.59
Abstract · 46 pages, submitted to QIP 2027. New version fixes the displayed abstract and makes some minor corrections to fix the parameters used in res…

Time and space (memory) are two of the most important measures of cost in computation, even more so for quantum computation. Yet, our tools for proving unconditional quantum tradeoffs between time and space are surprisingly limited. The first quantum time-space tradeoff lower bounds were proven for sorting by Klauck, Špalek and de Wolf. Unfortunately, their method is limited to proving output-oblivious lower bounds (i.e. the lower bounds only apply to algorithms with a non-adaptive output schedule) and other methods have yielded nothing beyond output-oblivious lower bounds for sorting. Here, we prove the first fully general quantum time-space tradeoff lower bound for sorting. We do so by introducing a novel method based on the noise operator to add to the analysis toolkit for proving quantum query and time-space tradeoff lower bounds. By combining our resulting quantum noise stability bound with quantum recording query methods, we prove an $Ω(n^{4/3} (\log \log n)/(S^{1/3} \log n))$ lower bound on the number of queries that a fully general quantum algorithm with at most $S$ qubits of memory requires to sort $n$ numbers from $[n^2]$. Applying our noise operator argument involves purely classical reasoning, which makes it particularly simple to use. We also use it to prove that, for any strongly universal (pairwise independent) hash function family $H$ from $n$ bits to $m$ bits, almost all hash functions in $H$ require any algorithm with at most $S$ qubits of memory to make $Ω(nm/S)$ quantum queries to input $x$ in order to compute $h(x)$, even with very small success probability. Previously, Mansour, Nisan, and Tiwari had shown a matching classical lower bound for computing $h(x)$ with both $h$ and $x$ as inputs using their hash mixing lemma. Our noise operator method allows us to use a related property of hash functions to prove our quantum lower bounds.

0.27

Quantum Query Advantage Requires Space

cs.CC quant-ph ·2026-09-04 ·Minbo Gao, Zhengfeng Ji, Ziyi Xie
publishedtheory similarity 0.59
Abstract · 21 pages, update introduction and fix grammar mistakes

Hao, Huang, and Liu (STOC'26) recently showed that optimal quantum query complexity may require large workspace even for short-output problems, and asked whether a quantum query advantage over classical computation can itself require space. We resolve this question by exhibiting an explicit total Boolean function with quantum query complexity $Q=\widetildeΘ(M)$, and randomized query complexity $R=Θ(M^{21/20})$, whereas, for every fixed $0<η<1/100$ and $S\le O(M^{1/100-η})$, its $S$-space quantum query complexity satisfies $Q_S=ω(M^{21/20})$. Consequently, $$ Q<R<Q_S, $$ so the unrestricted quantum query advantage disappears under sufficiently small workspace. The separation is obtained through a one-bit filtered-parity construction and a space-sensitive quantum lower bound based on compressed-oracle capacity and a new parity-to-capacity inequality, which may be of independent interest.

0.59

Gate-level Implementation and Resource Analysis of Lackadaisical Quantum Walk Search

cs.ET quant-ph ·2026-08-17 ·Amit Saha, Debanjan Kola, Nishanka Das, Amlan Chakrabarti
similarity 0.59
Abstract · 27 pages, 15 figures

Lackadaisical quantum walks (LQW) extend discrete-time quantum walks (DTQW) by introducing weighted self-loops, enabling improved spatial-search performance through controlled localization of the walker. Despite substantial theoretical progress, practical gate-level implementations suitable for quantum hardware remain largely unexplored, limiting evaluation under realistic architectural constraints, noise, and resource requirements. In this work, we present a gate-level implementation framework for lackadaisical quantum walk search. The proposed construction encodes the position and coin spaces into qubit registers, and realizes the walk dynamics through oracle, coin, and flip-flop shift operations. We validate the circuit by reproducing the expected search behavior for single and multiple marked vertices and by analyzing the effect of the self-loop weight on the success probability. We further evaluate the implementation under realistic noisy settings using superconducting hardware's noise models. Logical resource analysis shows that, for grids ranging from $8\times8$ to $64\times64$, the transpiled gate count increases from $3.63\times10^{5}$ to $4.38\times10^{6}$ and the circuit depth from $2.13\times10^{5}$ to $2.56\times10^{6}$. Finally, fault-tolerant resource estimates based on a surface-code model using the Microsoft Quantum Resource Estimator demonstrate the substantial space-time trade-off associated with magic-state production. The results establish a practical circuit-level pathway for implementing the LQW search and provide a basis for evaluating its performance.

0.29

A Quantum Lower Bound for Triangle Finding

cs.DS quant-ph ·2026-11-04 ·Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou
theory similarity 0.59
Abstract · 37 pages

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.

0.48

On Multi-Constrained Path Finding utilizing Grover Search and Decoded Quantum Interferometry

cs.NI quant-ph ·2026-11-11 ·Dmitrii Chemodanov
theory similarity 0.58
Abstract

Finding a path whose totals under several additive metrics all fall inside prescribed ranges is weakly NP-complete. We ask what two quantum algorithms can do for it, against strong classical baselines. For directed acyclic graphs (DAGs) we give a Grover search whose state preparation builds the uniform superposition over all source-to-destination paths with one qubit per arc and no ancilla. We prove it correct, give its exact gate count, and show that measured strings form an error- detecting code whose distance is a girth-like graph parameter. We complete the oracle and count its gates: one search on our largest instance, 136 arc qubits and 262,144 paths, needs about 4.4 x 10^5 Toffoli gates, while classical dynamic programming decides the same instance with 18,754 labels. Grover search needs O(sqrt(N/M)) oracle calls for M good paths among N . Classical meet-in-the-middle matches this exponent in the worst case, and known quantum algorithms with quantum memory beat it. For a staged fabric with node-independent linear weights, maximizing the number of satisfied metrics is max-LINSAT, and with power- of-index weights it is Optimal Polynomial Intersection, where no known polynomial-time classical algorithm matches decoded quantum interferometry (DQI). We verify this translation in simulation and run two small binary instances on IBM Heron processors, which keep 67 % and 15 % of the ideal gain over uniform sampling.

0.23