arXiv · quant-ph· Niranka Banerjee, Akinori Kawachi·· 8 天前精选
链表搜索的量子查询复杂度分析
Quantum Query Complexity for List Search
arXiv:2609.38736v1阅读论文 PDF ↗
仅依据论文摘要整理；未读取全文，实验条件、证明与基准细节请核对原文。
作者：Niranka Banerjee, Akinori Kawachi
首次提交：2026-09-30 09:20
研究任务与主要进展
Banerjee 与 Kawachi 在论文《Quantum Query Complexity for List Search》中证明，在公开起点、successor oracle 和至多一个标记顶点的链表模型下，决策与搜索版本的量子查询复杂度均为 Θ(min{ℓ,(Nℓ)^{1/4}})。
阶段、条件与复现 · 深读核对
- 任务输出与输入访问模型是什么？
- 在什么假设、规模与资源条件下成立？
- 与哪种经典基线比较，是否计入编码与读出？
这些是阅读核对问题；材料未说明的条件保留未知。请结合上方论文版本、资料范围与原文核验。
本站判断
该研究将链表搜索转化为量子查询复杂度问题，刻画了地址空间对查询代价的影响，并在 N<ℓ^3 时给出严格小于经典遍历代价的量子查询复杂度。结论的适用范围依赖公开起点、successor oracle 至多一个标记顶点等模型设定；当前材料仅为论文摘要，未涉及实现或实验验证。
来源：arXiv · quant-ph · arxiv.org