Deutsch–Jozsa 查询算法

算法没有逐项学习 $F(z)$，而是把整张真值表的正负相位总和放进一个特定振幅。末次 Hadamard 相当于 Fourier 变换：零频系数正是函数符号 $(-1{)}^{F(z)}$ 的平均值。Promise 把这个平均值限制为 $\pm 1$ 或 $0$，于是一次测量能够无误差地区分。

若函数既非 constant 也非 balanced，零频振幅可取二者之间的值，单次测量不再给确定答案。量子优势来自 promise 把需要判断的全局统计量离散成正交可分情况，不是一次查询可输出 $N$ 个函数值。

取 $m=2$，按 $00,01,10,11$ 排列输入。Constant 表 $0000$ 产生符号向量 $(1,1,1,1)$；Hadamard 后全部振幅集中在 $y=00$。

再取 balanced 函数 $F(z)=z_1$，真值表为 $0011$，查询后的索引态是

它正是 $H^{\otimes 2}|10⟩$，故逆向 Hadamard 后必测得 $10$，算法输出 balanced。四项相位相加为零也可直接复算 ${\alpha }_{00}=0$。

经典确定性算法在最坏情形需 $N/2+1=2^{m-1}+1$ 次查询。若前 $N/2$ 个回答全相同，未查询部分既可全部相同而补成 constant，也可全部相反而补成 balanced；再问一次才必能打破其中一个补全。依次查询 $N/2+1$ 个位置也足够，因为 balanced 表不可能有更多同值项。

这个指数差距只比较精确量子与确定性经典查询。经典 bounded-error 随机算法从不同位置抽取 $k$ 次：constant 永远同值；balanced 样本全同的概率至多约 $2^{1-k}$，所以常数错误只需常数个样本。把确定性下界说成随机下界，会抹掉协议集合的关键差异。

Deutsch–Jozsa 是 oracle 干涉的校准例：ancilla 初始化为 $|-⟩$、一次查询、末次逆 Hadamard和零频振幅四步都能逐项核算。若 oracle 只返回经过测量的经典 bit，符号叠加被破坏，轨迹不成立。

它也提醒复杂度陈述必须同时带输入规模 convention。这里函数输入有 $m$ bits，但 oracle 隐藏的是含 $N=2^m$ 项的真值表；经典界写成 $2^{m-1}+1$，也就是对表长 $N$ 的 $N/2+1$，两种参数不能混报。