文章总结： 本文详细解析了Deutsch算法作为首个展示量子计算优势的算法，通过叠加态输入、相位反冲和干涉测量三个关键步骤，仅用一次查询即可判断单比特黑盒函数是常数函数还是平衡函数，而经典算法需要两次查询。文章深入剖析了量子并行性、相位编码和干涉读出的核心机制，并指出该算法虽解决的是简化问题，但其揭示的量子算法模板为后续Deutsch-Jozsa、Grover、Shor等算法奠定了基础。 综合评分： 95 文章分类： 量子计算,算法解析,技术标准

---

【量子计算】Deutsch 算法：第一个量子优势

原创

Litt1eQ Litt1eQ

Coder小Q

2026年4月28日 08:31 山东

在小说阅读器读本章

去阅读

【量子计算】Deutsch 算法：第一个量子优势

上一篇我们把 Part 4 的赛场搭好了：要比较经典算法和量子算法，最干净的办法之一，是数一数它们向黑盒函数提了几次问题。可只说“量子更快”还远远不够。真正的问题是：它到底为什么能更快？更准确地说，量子态里的叠加、相位和干涉，究竟是怎样把两次经典查询压缩成一次量子查询的？[1][5]

Deutsch 算法就是回答这个问题的最小例子。它处理的任务小到只有一个输入比特，但也正因为小，我们可以把每一步都算出来，不必把关键机制埋在复杂符号里。读完这一篇，你应该能把它记成一句很具体的话：

❝

Deutsch 算法不是“同时读出两个函数值”，而是先用叠加把两个输入一起送进黑盒，再用相位反冲把函数值写进相位，最后用干涉把“相同还是不同”这个全局关系读出来。

这三步——叠加、把问题结构写进相位、再用干涉读出来——会在后面的 Deutsch-Jozsa、Grover 乃至 Shor 等算法里反复出现。所以这一篇虽然讲的是一个玩具问题，但它不是枝节，而是量子算法主线第一次真正落地的地方。[1][3]

0. 先看目的地：一次查询，确定区分两类函数

Deutsch 算法的完整电路非常短。第一个量子比特从  出发，第二个量子比特从  出发；两者先过一次 Hadamard 门，中间调用一次 Oracle ，最后只对第一个量子比特再做一次 Hadamard 并测量。[1]

如果测量结果是 ，那么函数是常数函数；如果测量结果是 ，那么函数是平衡函数。整个过程中，Oracle 只调用了一次。

这件事乍看有三个疑问。

第一，如果叠加态能把  和  两个输入一起送进去，为什么不直接把  和  一次性读出来？ 第二，为什么辅助量子比特偏偏要从  出发，而不是更自然的 ？ 第三，最后那个 Hadamard 门看起来像是在“把前面的叠加又撤销掉”，它为什么反而把答案显出来了？

这三个问题，其实就是这一篇的三条主线：量子并行性为什么还不够、相位反冲为什么关键、干涉为什么能把相位差翻译成测量结果。

1. 先把问题说清楚：我们到底要判断什么

Deutsch 问题研究的是函数

输入只能是  或 ，输出也只能是  或 。这样的函数一共只有四个：[1]

| 函数 | | | 类型 | | — | — | — | — | | | 0 | 0 | 常数 | | | 0 | 1 | 平衡 | | | 1 | 0 | 平衡 | | | 1 | 1 | 常数 |

这里“常数”的意思是两个输入给出同一个输出；“平衡”的意思是两个输入里恰好一个给出 ，另一个给出 。对于一位输入，这两个定义看起来很简单，但它们已经把“全局性质”和“单点取值”区分开了。我们不关心黑盒里到底装的是  的哪一个，我们只问：它属于哪一类？

这个区别非常重要。因为我们要的不是“知道所有函数值”，而是“知道两个函数值之间的关系”。换句话说，答案不是某个点上的数，而是  与  是相同还是不同。

1.1 经典算法为什么一定要问两次

假设你第一次查询的是 。

• 如果结果是 ，那么黑盒可能是 ，也可能是 。前者是常数，后者是平衡。你还不能判断。
• 如果结果是 ，那么黑盒可能是 ，也可能是 。前者是平衡，后者是常数。你还是不能判断。

如果你第一次查询的是 ，推理完全一样。无论先问哪个输入，只要只问一次，剩下的可能函数里总同时包含常数和平衡两类。所以经典确定性算法必须查询两次。[1]

这背后的原因可以压缩成一句以后还会反复出现的话：

❝

当问题要你判断的是“两个值之间的关系”时，经典逐点采样通常至少要先看到两个值。

Deutsch 算法的意义，就是要用一个最小电路告诉你：量子计算并不是绕过信息本身，而是改变信息被编码和读出的方式。

2. 量子 Oracle：为什么必须写成

上一篇已经建立了量子 Oracle 的标准形式：幺正性要求不允许把 Oracle 写成 （对常数函数这不可逆），正确做法是保留输入并对辅助量子比特做条件异或。[1][4]

其中  是模 2 加法。[1] 第一个量子比特保留输入，第二个量子比特按  决定是否翻转；再做一次  会回到原态，所以它确实是可逆的。

对于 Deutsch 问题，Oracle 的作用完全由四个函数决定。例如当辅助位初始化为  时，

• ，因为 ；
• ，因为 ；
• ，因为 ；
• ，因为 。

Oracle 并没有”告诉你一个答案”，而是以一个可逆门的方式，把函数结构嵌进了电路。后面所有基于 Oracle 的量子算法，真正操作的都不是抽象的函数 ，而是这个合法的量子门 。

3. 叠加态输入为什么还不够

知道了  的定义以后，很自然会想到：既然量子比特可以处在叠加态，那我们何不把  和  一起送进去？

如果把第一个量子比特准备成

把第二个量子比特先准备成 ，那么输入态就是

以平衡函数  为例，一次 Oracle 调用后得到

这已经不是简单的“一个输入对应一个输出”了，而是一个纠缠态。单次查询确实同时让  和  两个分支都经过了函数。[1]

但关键问题马上出现了：如果现在直接测量，你并不能同时看到  和 。你只会得到一个经典结果。对上面这个态而言，测到  和  的概率各是 。换句话说，量子并行性把多个分支都带进了电路，却没有让你把它们逐个读出来。

这就是很多初学者最容易误解的地方。量子算法的优势不是“同时算出很多答案，然后一次性全部打印出来”。如果只是这样想，测量一步就会把美好愿望打碎。

所以问题变成了：既然不能直接读取每个函数值，那能不能只把我们真正关心的东西留下来？这里我们真正关心的是“两个值相同还是不同”。Deutsch 算法的答案是：可以，但要把信息写进相位，而不是写进可直接测量的目标比特。

4. 相位反冲：把函数值写进相位，而不是写进答案位

Deutsch 算法之所以把第二个量子比特初始化为 ，并先过一个 Hadamard 门，不是偶然的。因为

而  恰好是会触发相位反冲的那个状态。[1][5]

4.1 先看一个基态输入

先别急着上叠加态。只看单个输入 ，配上辅助态 ：

按线性展开，

把  提出来，

现在分两种情况：

• 如果 ，后半部分就是 ；
• 如果 ，后半部分就是 。

所以可以统一写成

这条公式值得慢慢看。Oracle 明明定义成“对第二个量子比特做异或”，可当第二个量子比特处在  时，结果却是第二个量子比特保持不变，反倒是第一个量子比特前面多了一个相位因子 。这就是相位反冲（phase kickback）：函数值没有被存到辅助位里，而是“反冲”到了查询分支的相位上。[5]

4.2 用具体函数看一眼

先看常数函数 。因为 ，所以

没有任何分支获得负号。

再看平衡函数 。因为 ，所以

这时  分支多了一个负号。函数值的差异没有出现在目标比特上，而是出现在两个分支之间的相对相位里。

这一步和量子计算的关系非常深。后面你会看到，Grover 的相位 Oracle、Deutsch-Jozsa 的统一推导、Shor 里相位随函数值累积，核心都不是“把数值拷到某个寄存器”，而是“把结构刻进相位”。

4.3 把两个输入一起送进去

现在再把查询比特准备成叠加态 ：

通过 Oracle 后，

这时就出现了最关键的分类。

如果  是常数函数，那么 ，两个分支前面的符号相同，于是查询比特变成

如果  是平衡函数，那么 ，两个分支前面的符号相反，于是查询比特变成

也就是说，一次 Oracle 调用之后，我们并没有得到  和  这两个具体数；但我们得到了更适合这个任务的东西：

• 常数函数对应 ；
• 平衡函数对应 。

这两个态是正交的，可以被完美区分。到这里，问题已经几乎解决了。

最值得记住的总结是：

❝

Deutsch 算法一次查询拿到的不是两个函数值，而是“两个函数值是否同相”的信息。

5. 完整算法：把每一步都算出来

现在把前面分散的组件重新拼起来。Deutsch 算法从初态

开始。[1]

5.1 第一步：两个 Hadamard 门把初态变成

第一个量子比特经过 Hadamard，

第二个量子比特经过 Hadamard，

所以

这里第一个 Hadamard 的作用是制造“并行输入”，第二个 Hadamard 的作用是把辅助位调到会触发相位反冲的 。它们看起来都叫 Hadamard，但承担的任务并不一样。

5.2 第二步：一次 Oracle 调用把函数类型编码成  或

由上一节的推导，

因此：

• 若  为常数，；
• 若  为平衡，。

注意这里的  只是全局相位。整个态前面多一个整体负号，不会改变任何测量概率。[2]

5.3 第三步：最后一个 Hadamard 把相位差转成计算基差异

现在只对第一个量子比特再施加一次 Hadamard。它有两个最关键的作用：

所以：

• 常数函数时，查询比特从  变成 ；
• 平衡函数时，查询比特从  变成 。

第二个量子比特仍然是 ，但我们不测量它，因为答案已经全部体现在第一个量子比特里。

5.4 用一个具体函数完整跑一遍

用  来演示最清楚，因为它是平衡函数。

初态：

两次 Hadamard 之后：

通过  后，因为 ，

再对第一个量子比特施加 Hadamard：

测量第一个量子比特，结果必然是 。因此我们确定它是平衡函数。

对四个函数全部列出来，会得到一张很干净的验证表：

| 函数 | 类型 | Oracle 后查询比特 | 最后测量 | | — | — | — | — | | | 常数 | | | | | 平衡 | | | | | 平衡 | | | | | 常数 | | |

这个表说明得很直白：算法根本不在乎黑盒里具体是哪一个常数函数，也不在乎是哪一个平衡函数；它只保留对“类型”有用的信息，把对类型无关的细节压缩成了不可观测的全局相位。

6. 为什么最后一个 Hadamard 能把答案“读出来”

到这里你已经会算了，但还值得再往下追问一步：为什么第二个 Hadamard 如此关键？为什么它不是简单地“把前面做掉的叠加又还原回去”？

答案是：它不是在还原无信息的叠加，而是在把相对相位翻译成测量基里的差异。

看两个最简单的式子就够了：

Hadamard 矩阵是

于是

从干涉的角度看，这个过程非常直观。

• 对 ，两个分量同号，所以经过 Hadamard 后，在  通道里相加，在  通道里相消；
• 对 ，两个分量异号，所以在  通道里相消，在  通道里相加。

这就是“相位能不能被测到”的标准答案。相位本身不能直接读，但相位差可以通过后续干涉变成可测的概率差。Deutsch 算法最精炼地演示了这一点。

这和量子计算有什么关系？几乎是一切。后面的量子算法并不是靠神秘捷径跳过计算，而是不断重复这同一个模板：先让许多可能性共存，再把问题结构写进相位，最后设计一个干涉步骤，把对的答案放大、把错的答案抵消。

7. 局限性与意义：为什么这个小算法仍然值得学

先把局限说在前面。Deutsch 算法解决的问题极其人工：真实世界里，没人会专门拿一个只接受  和  的黑盒函数来问“它是常数还是平衡”。它带来的优势也很小，只是从两次查询降到一次查询。[1]

如果只从实用角度看，这确实不像一个“改变世界”的算法。

但它的重要性从来不在实用性，而在存在性。Deutsch 在 1985 年的工作第一次明确展示了：在一个具体的黑盒判定任务上，量子算法可以比经典确定性算法用更少的查询。[3] 这个任务很小，但它把“量子可能更快”从猜想变成了一个可计算、可验证、可逐步推导的事实。

更重要的是，它留下了三条后来所有量子算法都会继承的思想。

第一，叠加不是为了把所有答案直接读出来，而是为了让许多输入分支同时进入电路。 第二，相位是量子算法真正携带结构信息的地方，尤其是 phase kickback 这种把函数值写进相位的技巧。 第三，干涉不是附属现象，而是读出答案的核心装置；没有最后那一步干涉，前面的叠加和相位都只是隐藏在态里的内部结构。[1][5]

| 步骤 | 在 Deutsch 算法中的操作 | 作用 | 在后续算法中的对应 | | — | — | — | — | | 叠加 | 第一个  把  变成 ，让两个输入分支同时进入 Oracle | 创造并行性 | Deutsch-Jozsa、Simon、Grover 的均匀叠加初态 | | 相位反冲 | 目标比特初始化为 ； 把  写入查询比特相位 | 将函数全局性质编码进量子态的相位结构 | Grover 的相位 Oracle；Shor 的 QFT 相位累积 | | 干涉 | 第二个  把相位差转成概率差（，） | 让正确答案的概率幅相长、错误答案相消 | Grover 的扩散算子；Deutsch-Jozsa 的  测量 |

所以如果你以后要用一句话概括 Deutsch 算法，最准确的说法不是”第一个量子算法”，也不是”节省了一次查询”，而是：

❝

它是第一个把量子优势的工作机制完整展示出来的算法模板。

8. 小结：把本章的数学翻译回量子计算语言

现在可以把整篇文章压缩回一条清晰的链条：

1. 我们要判断的不是某个单点函数值，而是  和  的关系。

2. 经典算法逐点取样，所以确定性地回答这个问题必须查询两次。

3. 量子 Oracle 允许我们把两个输入分支一起送进去，但单靠叠加还不够，因为测量不能把两个函数值直接同时交给我们。

4. 把辅助量子比特准备成  后，Oracle 会触发相位反冲：

5. 于是一次查询之后，常数函数对应 ，平衡函数对应 。

6. 最后一个 Hadamard 把这两种相对相位结构转成  和 ，从而通过一次测量确定区分两类函数。

如果只保留一句能在后文反复调用的核心总结，那就是：

❝

量子算法的关键不在于“并行算了多少个值”，而在于“能否把问题的全局结构写进相位，并通过干涉读出来”。

这一篇的输入规模只有 ，所以量子优势还只是“2 次变 1 次”。下一篇的 Deutsch-Jozsa 算法会把同一个思路推广到  位输入：电路结构几乎不变，仍然是“Hadamard  Oracle  Hadamard”，但经典确定性最坏情况要问  次，而量子算法仍然只问一次。[1][4] 到那时可以更清楚地看到：Deutsch 算法不是一个孤立的小把戏，而是整个量子算法方法论的最小原型。

参考资料

1. Chris Bernhardt, Quantum Computing for Everyone. The MIT Press, 2019.
2. Leonard Susskind and Art Friedman, Quantum Mechanics: The Theoretical Minimum. Basic Books, 2014.
3. David Deutsch, “Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer,” Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences 400(1818), 97-117 (1985). https://doi.org/10.1098/rspa.1985.0070
4. David Deutsch and Richard Jozsa, “Rapid Solution of Problems by Quantum Computation,” Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences 439(1907), 553-558 (1992). https://doi.org/10.1098/rspa.1992.0167
5. IBM Quantum Learning, “Phase estimation procedure,” IBM Quantum Learning. https://quantum.cloud.ibm.com/learning/en/courses/fundamentals-of-quantum-algorithms/phase-estimation-and-factoring/phase-estimation-procedure

---

免责声明：

本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。

任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。

本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。

本文转载自：Coder小Q Litt1eQ Litt1eQ《【量子计算】Deutsch 算法：第一个量子优势》