量子预言机

量子预言机（oracle）是把待解问题的输入封装成可调用幺正变换的黑盒，算法对”如何计算 $f$“不做什么假设，只统计调用次数。常见形式：

• 比特预言机：$U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$；
• 相位预言机：$U_f|x⟩=(-1{)}^{f(x)}|x⟩$（可经相位反冲互相转换）；
• 标记式：Grover 算法 的 $U_O=2|x_0⟩⟨x_0|-I$，把目标态相位翻转。

要点

• 预言机模型把”输入的读入成本”与”算法的查询成本”分离：查询复杂度只计后者。真实端到端成本还要计入电路合成与QRAM 式数据加载（见量子数据编码 的批判性讨论）。
• 上下界技术配套：多项式方法与对抗方法（Span Program）在预言机模型下给出严格的查询下界；量子行走 的加速（如碰撞与元素唯一性）也以预言机调用数计价。
• 密码学用法：把密码函数当预言机攻击（量子密码分析 的 Q2 模型讨论）。

关联词条

• 概念：量子查询复杂度、相位反冲、量子并行性
• 算法：Grover 算法、量子密码分析

取材：量子计算概述、振幅放大。

参考文献

• D. Deutsch. Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer. Proc. R. Soc. Lond. A 400, 97 (1985). —— 预言机模型的起点.
• Nielsen & Chuang.《量子计算与量子信息》第 1 章（量子预言机）与第 6 章.