文章总结： Deutsch-Jozsa算法是首个展示指数级量子优势的算法，用于判断一个n位输入的黑盒函数是常数函数还是平衡函数。经典确定性算法最坏需要2^(n-1)+1次查询，而量子算法仅需一次查询即可确定。该算法通过Hadamard门创建均匀叠加、Oracle将函数值编码为相位、再次使用Hadamard门实现干涉，最终通过测量是否全零来判断函数类型，其核心在于利用量子干涉提取函数的全局对称性而非局部信息。
综合评分： 95
文章分类： 量子计算

---

【量子计算】Deutsch-Jozsa 算法：第一次真正看到指数级量子优势

原创

Litt1eQ
Litt1eQ

Coder小Q

2026年4月29日 08:31
山东

在小说阅读器读本章

去阅读

【量子计算】Deutsch-Jozsa 算法：第一次真正看到指数级量子优势

上一篇我们用 Deutsch 算法看到了量子优势的最小版本：经典需要两次查询，量子只要一次。可那个例子毕竟只有一个输入比特，节省的也只是一次查询。它更像“量子优势确实存在”的证明，还不像一次真正让人有数量级震动的加速。[1][2]

这一篇要把同样的结构推广到  位输入。问题仍然很简单：黑盒函数到底属于哪一类？但当输入从 1 位变成  位以后，经典确定性算法的最坏查询次数会变成 ，而量子算法仍然只调用 Oracle 一次。[1][2][3] 这时我们第一次真正看到“指数级”和“常数级”之间的距离。

更重要的是，这篇文章不只是为了多学一个算法。Deutsch-Jozsa 把后面整条主线都摆到了桌面上：先用  做均匀叠加，再用 Oracle 把函数结构写进相位，最后再用  让这些相位发生干涉。Simon、Grover、QFT 乃至 Shor，都会反复回到这个骨架上。

0. 先看目的地：为什么这次是真的“指数级”

先把结果摆出来。对于承诺问题“函数是常数还是平衡”，输入规模为  时：

| 输入规模 | 经典确定性算法最坏情况 | Deutsch-Jozsa 量子算法 |
| — | — | — |
| | 2 次 | 1 次 |
| | 5 次 | 1 次 |
| | 513 次 | 1 次 |
| | 524289 次 | 1 次 |
| | 次 | 1 次 |

量子算法这里最值得记住的地方，不是“少问了很多次”，而是“无论  多大，查询次数都不增长”。这才是本章标题里“指数级”的真正含义。[1][3]

整个算法的电路结构其实和上一节几乎一样，只是单个 Hadamard 门换成了  个量子比特上的 Hadamard 张量积：

这张图里埋着两件事，整篇文章都会围着它们展开。

第一，左边和右边那两个  到底做了什么？为什么它们不是“普通地把每一位翻一翻”，而是整个算法真正的发动机？

第二，最后为什么只要看测量结果是不是全零 ，就能判断函数是常数还是平衡？

如果你读完整篇后只记住一句话，那应该是：

❝

Deutsch-Jozsa 算法不是一次性读出  个函数值，而是让这  个输入分支先一起带上相位，再让它们在  这个出口处发生建设性或破坏性干涉。

1. 从一位问题到  位问题：到底要判断什么

Deutsch 算法研究的是一位布尔函数 。现在我们把输入推广成  位：

这里  表示所有长度为  的二进制串。例如  时，输入一共有 8 个：

Deutsch-Jozsa 问题不是问“这个函数长什么样”，而是问它属于哪一类。题目给了一个很关键的 承诺问题（promise problem）条件：函数保证只会落在下面两类之一。[1][3]

• 常数函数（constant）：全部  个输入都映到同一个输出。
• 平衡函数（balanced）：恰好一半输入映到 ，另一半映到 。

这句话看似只是定义，其实已经决定了算法能不能成立。因为如果没有这个承诺，算法测到的结果就不再对应一个清晰的二分类结论。这一点我们后面还会回来强调。

先看一个具体例子。设 ，把输入写成 。那么下面两个函数分别代表两类最典型的情况：

| 输入 | 常数函数 | 平衡函数 |
| — | — | — |
| | 0 | 0 |
| | 0 | 0 |
| | 0 | 0 |
| | 0 | 0 |
| | 0 | 1 |
| | 0 | 1 |
| | 0 | 1 |
| | 0 | 1 |

这里  的意思是：把输入串的第一位直接当输出。由于前四个输入第一位是 0，后四个输入第一位是 1，所以它刚好一半输出 0，一半输出 1，因此是平衡函数。

1.1 经典算法为什么会卡在第  次

这一点最好不要只背结论。还是用  来看。

假设你按顺序查询：

如果这四次全都得到 1，你仍然不能判断。

• 这有可能是常数函数，因为常数 1 函数对所有 8 个输入都输出 1。
• 这也有可能是平衡函数，因为平衡函数完全可以在前 4 个输入上都给 1，在后 4 个输入上都给 0。

所以前 4 次查询都一样时，答案仍然悬而未决。直到第 5 次查询：

问题才会被真正分开。

• 如果第 5 次还是 1，那么前 5 个输入都输出 1，这不可能是平衡函数，只能是常数函数。
• 如果第 5 次变成了 0，那么它一定不是常数函数，只能是平衡函数。

因此  时，经典确定性算法最坏需要 5 次查询。把这个推理推广到一般的 ，就得到最坏情况为

原因完全一样：前  次查询即使全相同，仍然可能来自常数函数，也仍然可能来自平衡函数；只有第  次才能强行把两种可能分开。[1][2]

这一节和量子计算的关系可以压成一句话：

❝

Deutsch-Jozsa 问题要判断的是一种全局结构，而不是某个单点函数值；经典逐点查询之所以慢，正是因为它只能一点一点积累这个全局结构。

2.  个 Hadamard 门：先把“并行性”说准确

很多初学者在这里最容易出现一种看似自然、其实不准确的理解：既然输入有  种，那量子计算是不是“把这  个输入同时算一遍”，于是就直接赢了？

这种说法只说对了一半。

对的部分在于， 的确会把查询寄存器变成所有输入的均匀叠加。错的部分在于，这并不等于你可以把  个函数值一次性读出来。测量只会给出一个经典结果。真正让算法有用的，不是“同时算了很多分支”这件事本身，而是这些分支后面还能继续相干地干涉。

先从  算起。单个 Hadamard 门在  上的作用是

如果两个量子比特都从  出发，各自过一个 Hadamard 门，那么

把张量积一步一步展开：

也就是说，两个比特同时过 Hadamard 后，4 个可能输入全部出现了，而且概率幅完全相同。

这个规律在一般的  上就是

这里的  不是一个普通数字，而是所有长度为  的二进制串。比如：

• 时，这个和式里一共有 8 项；
• 时，一共有 1024 项；
• 时，一共有 1048576 项。

这正是量子算法里常说的“均匀叠加”。它不是模糊的“很多状态混在一起”，而是一个系数完全明确的向量。

不过，后面推导真正需要的还不只是这一个特殊情况。更一般地， 对任意基态  的作用可以写成

这里的  不是普通实数点积，而是按位相乘后再模 2 相加：

例如当  时，

所以对应系数是 。

这个公式现在看起来也许有点抽象，但后面它会告诉我们：第二次  并不是简单“把叠加撤销”，而是在按照一套精确的正负号规则重新加总所有分支。[1][2]

这一节最值得反复记住的总结是：

❝

 的作用不是替你读出  个答案，而是把  个输入先放进同一个相干叠加里，为后面的相位编码和干涉做准备。

3. Oracle 还是那个 Oracle，但相位反冲变成了  位版

现在把上一节的均匀叠加送进黑盒。量子 Oracle 的结构与上一篇相同，只是查询寄存器从 1 位扩展到了  位：[1][2]

这里  是  位查询寄存器， 是辅助量子比特， 表示异或。

3.1 一旦辅助位取成 ，函数值就会变成相位

和 4.2 一样，真正关键的不是辅助位本身，而是把它准备成

这时对任意  位基态  都有

也就是说：

• 如果 ，这一支不变；
• 如果 ，这一支前面多一个负号。

举个具体的两位例子。若 ，则

• 当  时，；
• 当  时，。

函数值并没有留在辅助位里，而是反冲成了查询分支前面的相位。这就是 相位反冲（phase kickback）。

3.2 把均匀叠加送进去，会得到一整张“相位图案”

当查询寄存器已经是均匀叠加

而辅助位是  时，一次 Oracle 调用后的整体状态变成

于是：

• 若  为常数 0，所有分支前面都是 ；

• 若  为常数 1，所有分支前面都是 ；

• 若  为平衡函数，恰好一半分支是 ，一半分支是 。

  

这一步和量子计算的关系，可以非常具体地说成：

❝

Oracle 真正交给后续电路的，不是一个个可直接读出的函数值，而是一张由  组成的相位图案。

4. 把整个算法完整跑一遍：先算一个  的例子

现在把所有零件装起来。Deutsch-Jozsa 算法从

出发，分成三步：

1. 前面的  把查询寄存器变成均匀叠加，底部的  把辅助位变成 ；
2. Oracle 把函数值写成各输入分支的相位；
3. 后面的  让这些相位重新干涉，然后测量查询寄存器。

先取一个最具体的平衡函数：

这就是两位版本的“看第一位”函数。

4.1 第 0 步到第 2 步：准备叠加，然后写入相位

初态是

经过第一层 Hadamard 后，

经过 Oracle 后，由于前两项对应函数值 0，后两项对应函数值 1，因此

4.2 第 3 步：第二次  不是“撤销”，而是干涉

对查询寄存器再施加一次 ：

所以最终状态是

测量查询寄存器，一定不会得到 ，因此我们判断它是平衡函数。

这里有一个很容易误解的点。Deutsch-Jozsa 并不是在说“平衡函数最后都会变成某个固定的非零串”。上面这个例子之所以刚好变成 ，是因为我们选的平衡函数比较特殊。算法真正保证的只有一件事：平衡函数不可能测到全零。

4.3 再看一个常数函数作对照

若 ，那么 Oracle 后的状态是

查询寄存器再经过  后，会回到

因此常数函数一定测到全零。

把两个例子并排看，会更直观：

到这里，判读规则已经很清楚了：

• 测量得到 ：函数是常数；
• 测量结果里只要有一个 1：函数是平衡。

这一节最值得记住的话是：

❝

Deutsch-Jozsa 算法把“常数还是平衡”翻译成了一个非常特殊的测量问题：全零态是不是还有振幅。

5. 为什么“全零代表常数”会精确成立

上一节已经让我们会算了，但还值得再追问一步：为什么这条判读规则不是“通常成立”，而是“严格成立”？

把一般的量子态推到最后一步。经过第一次  和 Oracle 以后，查询寄存器是

再施加一次 ，利用上一节的公式

就得到最终查询寄存器的状态：

这里外层求和遍历所有可能测量结果 ，内层求和则是在把所有输入分支重新加总。于是，某个输出串  的概率幅正是

5.1 我们真正关心的是

现在把  取成全零串 。由于对任意  都有 ，于是全零态的概率幅简化为

这就是整个算法的核心公式。[1][2][3]

它一下子把两类函数分开了：

如果  是常数 0，那么每一项都是 ，所以

如果  是常数 1，那么每一项都是 ，所以

虽然是 ，但它只是全局相位，测量概率仍然是

如果  是平衡函数，那么恰好一半项是 ，另一半项是 ，因此

这不是“差不多抵消”，而是精确抵消。

5.2 用一个  的数字例子看见这种抵消

设 ，并取平衡函数 。那就有 4 个输入满足 ，4 个输入满足 ，所以

而如果是常数 0 函数，则

这就是为什么最后测量全零，可以把两类函数完全分开。

这里顺便纠正一个常见但不够严谨的说法。你有时会听到“平衡函数经过第二次  后就会变成某个非零基态”。这对某些特殊函数成立，但不是一般规律。一般规律其实更准确，也更重要：

❝

对任意平衡函数，唯一被保证为零的是  的概率幅；其余非零串的振幅如何分布，要看具体函数的相位图案。

一旦抓住这一点，你就会发现 Deutsch 算法和 Deutsch-Jozsa 算法其实是同一件事的两个尺度：

• Deutsch 算法里只有两个输入分支，最后判断的是“落在  还是 ”；
• Deutsch-Jozsa 里有  个输入分支，但真正被保留下来的，仍然是“全零出口有没有振幅”这个问题。

两者的对应关系并排来看会更清楚：

| | Deutsch（） | Deutsch-Jozsa（ 位） |
| — | — | — |
| 叠加 | ，产生 2 个态 | ，产生  个态 |
| 相位编码 | （2 个相位因子） | （ 个相位因子） |
| 干涉读出 | 把相位差转成  vs | 把正负对消（平衡）vs 同向叠加（常数） |
| 测量判读 | 结果 0 → 常数，结果 1 → 平衡 | 全零 → 常数，非全零 → 平衡 |

6. 这份优势的边界：为什么它重要，但也不能被夸大

到这里，有一个很自然的问题必须诚实回答：既然经典确定性算法最坏要  次，那经典随机算法能不能做得更好？

答案是：可以。[1]

一种非常直接的随机策略是：

1. 随机挑选  个不同输入去查询；
2. 只要结果里同时出现了 0 和 1，就立刻知道函数是平衡的；
3. 如果  次结果全部相同，就猜它是常数。

如果函数其实是平衡的，那么这  次查询结果仍然全部相同的概率不会超过

例如取 ，错误概率就满足

也就是说，经典随机算法用常数次查询，就能把错误率压到千分之一以下。

所以 Deutsch-Jozsa 算法展示的最严格结论应该这样表述：

❝

在“函数保证常数或平衡”的承诺条件下，Deutsch-Jozsa 对经典确定性查询复杂度给出了指数级分离；如果允许经典算法带小概率出错，这个分离就不再是指数级。

这不是给算法“泼冷水”，恰恰相反。把边界说清楚，才能知道它真正重要的地方在哪里。

第一，它把量子算法里最核心的三件事第一次完整地摆在了一起：均匀叠加、相位反冲、干涉读出。

第二，它引入了  这个后面几乎所有算法都会反复调用的工具。

第三，它告诉我们：量子算法擅长的，不是把所有局部答案逐个打印出来，而是把问题里真正有用的全局结构，通过干涉放大成一个可测的结果。[2][3]

还要再强调一次承诺条件的重要性。如果函数既不是常数也不是平衡，例如  个输入里有三分之二输出 0、三分之一输出 1，那么算法仍然会给出某个测量结果，但这个结果已经不能再被解释成“常数”或“平衡”的明确判决。也就是说，Deutsch-Jozsa 的正确性不是对任意布尔函数成立，而是建立在题目承诺之上的。

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

现在可以把整篇文章压缩回一条主线。

Deutsch-Jozsa 问题要判断的不是某个输入点的函数值，而是一个全局性质：函数到底是常数还是平衡。经典确定性算法只能逐点排除，所以最坏情况需要  次查询。量子算法则走了另一条路：先用  把所有输入一起准备进均匀叠加，再让 Oracle 把函数值写成每个输入分支前面的相位，最后用第二次  让这些相位在全零态上发生干涉。常数函数时，所有分支同向叠加；平衡函数时，正负各半，恰好抵消。因此只需一次查询，就能通过“是否测到全零”完成判断。

如果还要再压成一句可以反复调用的话，那就是：

❝

Deutsch-Jozsa 算法读出的不是函数值本身，而是函数在相位层面留下的全局对称性。

 这个结构并不会停在“常数还是平衡”这里。Simon 算法会把同样的骨架用在更有内容的问题上：它不再判断简单二分类，而是从干涉图案里提取一个隐藏的异或周期——到那时， 就不只是“制造均匀叠加”了，而会成为提取隐藏结构的读出工具。

参考资料

1. Chris Bernhardt, Quantum Computing for Everyone. The MIT Press, 2019.
2. Robert S. Sutor, Dancing with Qubits: How Quantum Computing Works and How It Can Change the World. Packt, 2019.
3. 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

---

免责声明：

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

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

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

本文转载自：Coder小Q Litt1eQ
Litt1eQ《【量子计算】Deutsch-Jozsa 算法：第一次真正看到指数级量子优势》