量子查询复杂度

在预言机模型下，算法成本只计黑盒调用次数，称为查询复杂度。它是量子算法理论中最成熟的实验室：Shor 的加速来自代数结构而非查询优势，而 Grover 型平方加速、行走型 $N^{1/3}$ 加速等都在查询模型下有匹配的下界。

要点

• 下界技术：多项式方法（测量概率是查询次数的低次多项式）与对抗方法（进度度量）；二者可由 Span Program 统一——span program 的” witness 尺度”同时给出算法与下界。
• 代表性结果：无结构搜索 $\Theta (\sqrt{N})$（Grover，最优）；碰撞问题 $\Theta (N^{1/3})$；元素唯一性 $\Theta (N^{2/3})$；顺序搜索 的常数因子优势；OR 复合函数的 $\sqrt{N}$ 谱加速。
• 模型边界：查询最优不等于端到端最优（读入输入可能本身昂贵），也不排除查询模型外的经典算法（见 Tensor PCA 中对模型假设的讨论）。
• 与复杂度类 BQP 的关系：查询模型给出 BQP 相对 P 的”可证”分离场景（如 Simon 算法 相对预言机）。

关联词条

• 概念：量子预言机、振幅放大、量子行走
• 算法：Boolean 公式求值、碰撞与元素唯一性

取材：振幅放大、查询复杂度与图算法 各词条的模型讨论。

参考文献

• A. Ambainis. Quantum Lower Bounds by Quantum Arguments. J. Comput. Syst. Sci. 64, 750 (2002). arXiv:quant-ph/0002066
• Nielsen & Chuang.《量子计算与量子信息》第 4 章（查询模型与下界方法）.