给定一个数组a[1..n]，范围最小值查询（RMQ）问题旨在维护一个支持RMQ查询的数据结构：给定范围[l,r]，找出子数组a[l..r]中最小元素的索引，即arg min_{i∈[l,r]} a[i]。本论文提出了一种支持RMQ查询和范围更新的量子数据结构，其时间复杂度达到最优的Θ~(√nq)——在执行q=O(n)次操作且无需预处理的情况下，相较经典算法的Θ~(n+q)实现加速。作为应用案例，该工作还提出了一种无需量子随机存取存储器（QRAM）的高效量子k-最小值查找算法。
作者所在地：
VIP可见
作者单位：
VIP可见
期刊参考：
登录可见
页数/图表：
登录可见
提交arXiv：
2026-01-19 16:19
