Source-linked AI summary
Towards Quantum Range Query for Spatial-Temporal-Semantic Trajectory Data
Hao Li, Zhihang Liu, Liwei Zou, Jinlin Wu, Wufan Zhao
TL;DR
Exact trajectory range queries can bottleneck downstream analysis as archives grow. QRQ combines classical index pruning with quantum access to candidate slots, returning answers in superposition. Across three datasets, it reports speedups from 2.03× to 64.70×, with the advantage depending on geometry and query scale.
Problem
Classical tree-based range queries must visit overlapping nodes and enumerate k hits, so query cost depends on the indexed points within the range.
Source: §1 · p. 1Method
QRQ combines classical geometric pruning with QRAM access to candidate slots in superposition, using quantum variants of R-tree, TB-tree, and KD-tree.
Source: §1 · p. 2, §2.1 · p. 2, §2.3 · p. 2Results
Takeaways & Limitations
Because QRQ keeps answers in superposition, it can feed downstream quantum analytics and serve as a retrieval primitive for LLM- and GeoFM-composed queries.
Source: §4 · p. 4Quantum advantage requires sufficient target-result volume; at N = 65,000 or 0.1% selectivity, speedups on dense T-Drive can fall below 1×.
Source: §3 · p. 4
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Trajectory range queries return the exact segments intersecting a spatiotemporal window, supporting mobility and environmental applications. QRQ adapts quantum range-query techniques to trajectory indexes and reports speedups across three datasets.
1 INTRODUCTION
- Range queries identify the exact trajectory segments intersecting a spatiotemporal window, and their efficiency can bottleneck mobility analysis and related applications.The paper identifies mobility analysis, congestion forecasts, and environmental-transport reconstructions as downstream uses.Source: §1 · p. 1
- Classical tree indexes return exact range-query results, but their O(log N + k) cost includes visiting overlapping nodes and enumerating k matching segments.Overlapping bounding rectangles can force additional child visits even when much of each box lies outside the query.Source: §1 · p. 1
- Quantum range-query approaches use superpositions to avoid inspecting every candidate, while prior quantum-tree methods assume one-dimensional keys with disjoint routing intervals.Prior methods can extract marked candidates after a containment or intersection witness.Source: §1 · pp. 1–2
- QRQ implements quantum variants of R-tree, TB-tree, and KD-tree for trajectory range queries, reporting speedups from 2.03× to 64.70× across three datasets.Its node slots, including padding slots, are read in superposition through QRAM.Source: §1 · p. 2
2 METHODOLOGY
The method combines classical index pruning with quantum superposition over a compact candidate cover. It uses QRAM-based tree operations and post-selection to return exact query answers in superposition.
2.1 Problem Formulation
- The classical answer set contains indexed record-key pairs whose key coordinates fall within the query window bounds.A trajectory record combines temporal, spatial, and semantic components, and its index key may use a space-filling embedding or quantized attribute concatenation.Source: §2.1 · p. 2
- A classical control plane uses routing bounds and node occupancy to prune candidates before a quantum data plane accesses their stored relations and payloads.This separation avoids an unstructured search across all N records.Source: §2.1 · p. 2
2.2 Quantum Index Representation
- QRAM oracles expand node identifiers to children and load leaf payloads, while a predicate oracle marks entries satisfying every query dimension.Measuring the predicate flag yields the target state with probability k/m, with expected post-selection time O(m/k).Source: §2.2 · p. 2
2.3 Quantum Range Query
- Index geometry shapes the variants' candidate ratios: KD-tree partitions can reduce the frontier for balanced, low-dimensional data, while correlated dimensions can degrade performance.The stated operational complexity is O(h + q + hm/k), reducing to O(log_B N) for bounded frontiers and constant selectivity.Source: §2.3 · p. 3
- QRQ prunes disjoint nodes, accepts fully contained nodes, and expands partial intersections before preparing and filtering candidate entries in superposition.The candidate cover is dense, and packed occupancy keeps expected post-selection trials O(1); the three implementations use R-tree, TB-tree, and KD-tree variants.Source: §2.3 · pp. 2–3
3 RESULTS
Across three trajectory datasets, QRQ variants report I/O speedups, with gains shaped by dataset geometry and query scale.
3 RESULTS
- Primary evaluations used N=1,048,576 segments, 1% target selectivity, and 10,000 queries across GeoLife, T-Drive, and GDP Drifter.The datasets span long-extent human mobility, a dense urban road network, and sparse basin-scale ocean tracks.Source: §3 · p. 3
- 2.03×–64.70× I/O speedups were reported across all 27 QRQ configurations.Table 1 presents QRQ speedup performances.Source: §3 · p. 3, Table 1 · p. 4
- Sparse GDP Drifter data yielded peak speedups up to 64.70× for space-time KD-trees, while dense GeoLife and T-Drive MBR overlap produced 2.03×–4.82× space-query speedups.Containment witnesses in sparse data let quantum scans process fully covered subtrees without enumerating individual leaves.Source: §3 · pp. 3–4
- Speedup increased with dataset size, but dense T-Drive fell below 1× at N=65,000 or 0.1% selectivity; sparse drifter data retained advantages under strict selectivity.The quantum advantage requires enough target-result volume to amortize post-selection overhead.Source: §3 · p. 4, Figure 3 · p. 4
4 CONCLUSION
QRQ keeps the packed R-tree, TB-tree, and KD-tree unchanged while changing the access path and returning exact segment-window query results in superposition. Across three datasets, speedups ranged from 2.03× to 64.70×; the paper identifies index geometry and query scale as governing factors.
4 CONCLUSION
- QRQ leaves packed R-tree, TB-tree, and KD-tree indexes unchanged, using QRAM-read node slots and returning exact segment-window answers as a superposition.The walk stops at the first containment or intersection witness.Source: §4 · p. 4
- 2.03×–64.70× speedups were reported across GeoLife, T-Drive, and GDP Drifter, with quantum advantage governed by index geometry and query scale rather than data volume alone.Sparse, wide-extent data can amortize post-selection quickly, whereas overlapping urban MBRs delay it.Source: §4 · p. 4
- Extending index keys to semantic attributes is identified as future work, while superposition outputs are proposed as a retrieval primitive for LLM and GeoFM queries.The paper also states that superposition answers can feed downstream quantum analytics directly.Source: §4 · p. 4