Deutsch–Jozsa：一次查询看全局

黑箱里藏着一个函数 $f:\{0,1\}^n\to\{0,1\}$。你每次只能问一个输入，它回你 0 或 1；它保证要么是常数（全 0 或全 1），要么是平衡（一半输入给 0，一半给 1）。你要判断是哪一种。

经典的最坏情况有多坏

确定性经典算法最坏要问 $2^{n-1}+1$ 次。理由很朴素：你问了 $2^{n-1}$ 个输入，答案全一样，仍然不能排除剩下那一半全是另一个值——函数可能恰好是平衡的。再问一个，才敢下结论。

量子算法只调用一次 神谕。注意「一次」的含义：它没有读到 $2^n$ 个函数值，只拿到了一个比特的判定——常数还是平衡。

这个差距限定在「确定性、零错误」的查询模型里。允许小概率出错时，经典随机抽几个点也能把错误压得很低；它证明的是查询模型里的分离，不是全面碾压。

下面的线路演示相位怎么被踢回控制位。先点预设「相位回踢」，再用「下一步」逐格走完这 5 个门。

把答案写进相位

先把输入寄存器放到均匀叠加 $\frac{1}{\sqrt{2^n}}\sum_x |x\rangle$，目标位准备成 $|-\rangle$。神谕是 $U_f:|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$。

当目标位处在 $|-\rangle$ 上，$f(x)=0$ 时它不变，$f(x)=1$ 时它多一个负号。这就是相位踢回：函数的取值没有写进目标位，而是以 $(-1)^{f(x)}$ 的形式留在了输入寄存器的 振幅 里。

接着给每个输入比特再加一个 H 门。常数函数的所有振幅同号，叠加后互相加强，测量只能得到全零；平衡函数一半正一半负，全零那一项的振幅正好抵消，测量必然得到某个非零串。一次查询、一层 干涉，判定就出来了。

这也解释了它为什么只给一个比特：相位 里编码的是 $f$ 的全局对称性，不是逐点的值。要把真值表读出来，仍然需要指数多的信息。