Deutsch–Jozsa：最迷你的量子加速

上一篇我们说，量子算法的精髓是"同时装下所有答案，再让对的浮出来"。听起来很美，可你心里一定嘀咕：这玩意儿真的能work吗？还是只是漂亮话？

这一篇，我们用一个最小、最干净的例子——Deutsch–Jozsa 算法——让你亲眼看一次"量子加速"是怎么发生的。它小到几乎没用，却足以让人"啊哈"。

一、先给经典电脑出一个小难题

想象一个"黑盒子"函数 f：你喂它一个输入（0 或 1），它吐出一个输出（0 或 1）。这个盒子内部怎么算的，你不知道，只能一个个试输入、看输出。

黑盒子只有两种可能的"性格"：

• 常数型：不管喂 0 还是 1，输出都一样（全 0 或全 1）；
• 平衡型：喂 0 给一个值，喂 1 给另一个值（一 0 一 1）。

你的任务：判断这个盒子是"常数型"还是"平衡型"？

经典电脑怎么做？它得试两次：喂一次 0，再喂一次 1，对比输出。两次，缺一不可。

二、量子版：一次就够

Deutsch–Jozsa 的惊人之处在于：用量子比特，只调用一次黑盒子，就能断定盒子是哪种性格。

诀窍正是我们熟悉的两招： 1. 用 H 门把输入比特变成叠加——于是一次调用，相当于同时问了"0 和 1 两种情况"； 2. 再用另一组门做干涉，让"常数"和"平衡"两种盒子在测量结果上呈现出完全不同的图案。

调用一次，测量，看图案，完事。

看，经典要 2 次，量子只要 1 次。在这个小问题上，量子把"必试两次"压成了"一次搞定"。

三、为什么这例子"小到几乎没用"

你可能会失望：不就省了一次调用吗？至于这么大张旗鼓？

关键在于思想实验的价值，不在实用性：

• 它第一次干净利落地证明，量子算法原则上可以比任何经典确定性算法用更少的"询问"得到答案；
• 它是后面那些"大算法"的雏形——Grover 的搜索、Shor 的分解，本质上都是把"叠加着问 + 干涉筛选"这套动作放大、做精致。

所以 Deutsch–Jozsa 像一节示范课：动作很简单，但把"量子为什么能加速"的机制，演得清清楚楚。

四、把"加速"说严谨一点

这里必须诚实：Deutsch–Jozsa 的加速是"查询次数"上的加速（2 次 → 1 次），而且前提是黑盒子是量子的（能接受叠加输入）。它不是"算得飞快"，而是"问得少"。

真正让人兴奋的，是这种机制的可扩展性：

• 当输入不是 1 个比特、而是 n 个比特（2ⁿ 种输入）时，经典最坏要试约 2ⁿ/2 + 1 次才能区分常数/平衡；
• 量子依然只要 1 次。

n 越大，差距越夸张。这从一个小玩具，变成了指数级的鸿沟。

五、下一篇，找那根针

Deutsch–Jozsa 证明了"加速存在"，但太玩具了。下一篇，我们讲一个真能派上用场的搜索算法——Grover：给你一个巨大的干草堆，里面藏一根针，经典要一根根翻，Grover 能快得多地把针揪出来。

如果今天只记住一句话，那就是：Deutsch–Jozsa 用最小的例子证明——量子可以"叠加着一次问完所有情况"，再用干涉让答案现形；加速虽小，机制却真。

下次见。