出处已验证第 3 级
Deutsch-Jozsa算法
Deutsch-Jozsa算法仅用一次查询确定布尔函数是常数还是平衡的，比经典确定性算法提供指数级加速。
这是什么意思
确定黑盒函数是常数还是平衡的。经典最坏需要2^(n-1)+1次查询，量子只需1次。利用量子并行和干涉。生活类比
像检查硬币是否公平。
像检查密封投票箱。
常见误解
- 加速是相对确定性经典算法。
- 不告诉你函数计算什么。
要点总结
- 1次预言查询决定常数vs平衡。
- 首个证明量子优势的算法。
- 使用叠加、相位反冲和干涉。
检验你的理解
需要多少次预言查询？
- A.n
- B.2^n
- C.1
- D.log(n)
查看答案
答案: C. 1
原因: 只需1次预言查询。
先修概念
一次文献: Deutsch & Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. A 439, 553 (1992), doi:10.1098/rspa.1992.0167