一次查询能揭示什么?
量子算法并不能通过测量叠加态获得函数的每个取值。然而,它可以安排可逆预言机产生的相位,使后续干涉图样回答某个特定的整体问题。Deutsch–Jozsa 算法就是一个清晰例子:它只调用一次预言机,就能精确区分两类受到承诺的 Boolean 函数。这个结论离不开承诺和查询模型。
定义 2.1.1
(常值函数与平衡函数)
设 、,。常值函数在每个输入处取相同值。平衡函数在恰好 个输入处分别取每个值。任务是在保证输入函数属于这两种情形之一的条件下判断是哪种。对承诺之外的函数,此任务没有指定正确答案。
定义 2.1.2
(可逆预言机与查询)
标准可逆预言机作用于输入寄存器和一个目标量子比特:
对每个固定的 ,它要么保持目标不变,要么翻转目标,因此置换计算基,是酉算子。一次查询计作使用一次 ;构造该预言机的物理成本不计入查询次数。这个承诺不意味着任意 都有小规模电路。
从可逆查询获得相位
令 、。由于 ,
目标回到同一状态,输入分支则获得相位。这个相位回授由可逆预言机的线性性得到,并不是在所有输入上测量 。
准备 ,对每个量子比特施加 ,调用一次 ,再对第一寄存器施加 。使用二进制内积 和恒等式
最终态为
测量第一寄存器,当且仅当结果为 时输出“常值”。
常见错误
(用 而不是 作目标)
若目标为 ,预言机给出 ,即把 记录在目标中,而不是产生相位。最后的 Hadamard 门之后,第一寄存器中 的分量为 ,其长度平方为 ,其中 分别是取值 的输入个数。对平衡函数这个值是 ,所以有一半的机会测得 ,判定规则失效。目标必须制备为 ,即先制备 再施加 。
定理 2.1.3
(承诺下的精确判定)
算法使用一次预言机查询,对每个常值或平衡的 都以概率一给出正确答案。
证明
(全零结果处的振幅)
在 处,振幅为 。若 常值, 或 ,因此测量以概率一给出 。若 平衡,正项与负项抵消,故 ,永远不会测得 。因此输出规则在两个承诺情形中均正确。
证明透视
干涉实际计算了什么
第一组 Hadamard 门准备相等振幅;预言机按 改变它们的符号;最后的 Hadamard 门在每个输出位置相加带符号的贡献。在 处,额外的点积符号全为一,所以其振幅是 的平均值。承诺判定只需要这个汇总量。电路不会在一次测量中揭示整个真值表。
例题 2.1.4
(两个比特的平衡函数与常值函数)
当 、 时,四个输入中恰有两个取值一。最终第一寄存器为 ,因此必然输出“平衡”。对常一函数,最终第一寄存器为 ;负号是全局相位,所以必然输出“常值”。
例题 2.1.5
(一个本身是特征(character)的平衡函数)
令 、。它在四个输入中恰有两个取值一,所以是平衡的。振幅按两个比特分解:
第一个因子在 时为 ,否则为 ;第二个因子在 时为 ,否则为 。因此 ,其余振幅全为零。测量返回 ,所以输出“平衡”,与预期一致。这个函数就是 的隐藏字符串函数。
常见错误
(负振幅仍然是常值情形)
对常一函数,。有些读者因这个负号而认为函数“不是常值”。测量概率取决于 ,所以 必然出现;负号是全局相位,对结果没有影响。
承诺改变了什么?
反例模式
承诺之外,输出不能完成分类
令 , 仅在 处取一。它既非常值也不平衡。这里 ,因此测量得到 的概率为 ,得到非零字符串的概率为 。如果只允许“常值”和“平衡”两个标签,无论算法输出哪一个都不能正确描述这个函数。精确保证只适用于承诺输入;它并未声称每个 Boolean 函数都属于这两类之一。
对任意 ,得到 的概率为 。它衡量两种输出值的不平衡量的平方。概率为零蕴含平衡,但在承诺之外,单次测得非零结果本身并不能证明恰好平衡。
下面的互动图会为你编辑的真值表精确计算第一寄存器的每个振幅 ,让你看到 的振幅就是 的平均符号,以及在承诺之外有何不同。
0ⁿ 的振幅就是 f 的平均符号
选择 n 及 f 的真值表。对每个量子比特作 H、以目标 |−⟩ 作一次查询,再对第一寄存器作 Hⁿ 后,y 的振幅为 A_y = (1/N) Σₓ (−1)^(f(x) + x·y)。切换各项,并比较 0ⁿ 的振幅与承诺。
每个 f(x) 按钮把该项在 0 与 1 之间切换。
| 输入 x | f(x) | (−1)^f(x) |
|---|---|---|
| 00 | +1 | |
| 01 | −1 | |
| 10 | −1 | |
| 11 | +1 |
| 结果 y | Σₓ 符号 | A_y | Pr(y) = A_y² | 概率条形 |
|---|---|---|---|---|
| 00 | 0 | 0 | 0 | |
| 01 | 0 | 0 | 0 | |
| 10 | 0 | 0 | 0 | |
| 11 | 4 | 1 | 1 |
- N = 2ⁿ
- 4
- f = 0 的输入数
- 2
- f = 1 的输入数
- 2
- Pr(0ⁿ)
- 0
- ((0 的个数 − 1 的个数)/N)²
- 0
- Σ Pr(y)
- 1
- 承诺状态
- 平衡
- 输出“常值”的概率
- 0
- 输出正确的概率
- 1
n = 2; Pr(0ⁿ) = ((2 − 2)/4)² = 0; 承诺: 平衡. 输出正确的概率: 1.
输出规则:当且仅当结果为 0ⁿ 时输出“常值”
为何只需要平均符号
在 y = 0ⁿ 处,每个点积 x·y 都是 0,所以 A₀ = (1/N) Σₓ (−1)^f(x) =(f = 0 的个数 − f = 1 的个数)/N。
若 f 常值,则 A₀ = ±1,故 0ⁿ 以概率 1 出现(整体符号无法观测)。若 f 平衡,两种符号的个数相等,故 A₀ = 0。
在承诺之外,A₀ 可以非零而又不等于 ±1。0ⁿ 的概率为零蕴含平衡;但单一个非零的测量结果本身并不证明精确平衡。
由于 Hⁿ 与 U_f 都是酉算子,概率总和恒为 1;表中以精确分数验证。
n 限于 3,使每个振幅都是精确分数。此图只计一次预言机查询,不计构造 U_f 的成本。
经典查询的比较
命题 2.1.6
(确定性精确查询复杂度)
在承诺之下,任何始终正确的确定性经典算法,在某个输入函数上至少需要 次查询;而 个不同的查询已经足够。
证明
(对手一律回答零)
对前 个不同查询全部回答零。这些答案既与常零函数相容,也与一个平衡函数相容:只需在尚未查询的输入中选 个赋值为一。重复查询不会提供新信息。因此,在这条回答记录上,算法不能在至多 次查询后安全停止。查询 个不同输入则足够:如果两种值都出现,函数平衡;如果全部相同,平衡函数不可能产生这些答案。
这是精确的确定性比较,不是对有界误差随机经典算法的指数分离。例如,无放回地均匀抽取 个不同输入;若两种值都出现则判为“平衡”,否则判为“常值”。对常值函数总是正确。对平衡函数,错误概率为
其中当 时规定 。只要该比值非零, 中的每个因子都至多为 。因此,输入足够多时,固定错误容忍度只需常数次随机经典查询。量子算法在此预言机模型中有一次查询的精确优势;这本身不能证明某个具体计算问题存在指数级的有界误差运行时间分离。
例题 2.1.7
(八个输入上的随机测试)
令 ,即 ,并抽取 个不同输入。当 时,平衡函数的错误概率为 ,低于上界 。当 时为 。当 时 ,错误概率为 :平衡函数的五个不同输入不可能全取同一值。这是随机测试变为精确的边界情形,代价是和确定性下界一样的 次查询。
一个相关的隐藏字符串问题
改为假设 ,其中 未知。这是不同的承诺,包含 。
命题 2.1.8
(隐藏字符串的一次查询恢复)
对 ,同一相位查询电路在一次查询后以确定性方式测得 。任何始终能找到 的确定性经典算法,在最坏情况下至少需要 次二值查询,即使查询可以自适应选择也是如此。
证明
(振幅按坐标分解)
同一相位查询电路具有振幅
最后的等式来自按坐标分解求和:若 中有任一位为一,对应输入位的两种取值便使各项抵消。因此一次测量以确定性方式返回整个字符串 。至于经典下界,深度为 的决策树至多有 条回答记录,而算法必须区分 个可能字符串,所以 。
这就是 Bernstein–Vazirani 算法。此比较统计的是预言机查询次数,而不是实现预言机的成本。
概念视角代数
振幅是 Walsh–Hadamard 变换
记 。则 就是归一化符号向量 的 Walsh–Hadamard 变换,即从点 到特征 的酉基变换。在这个描述下,上面的几种情形是同一个陈述。 是 的平均值,所以常值的 把全部权重放在 ,平衡的 在那里没有权重;特征 则把全部权重放在 。由于变换是酉的,对每个 都有 :从 移走的权重必然落在别处。
练习与解答
快速检查
(当 、、 时,写出相位预言机对 和 的作用。最终第一寄存器测得什么?)
解答 · 答案
两个分支分别获得相位 和 。查询后第一寄存器为 ,施加 后变成 ,测得 。
快速检查
(当 ,令 仅在 处取一。计算测得 的概率,并解释为什么承诺判定定理不适用。)
解答 · 答案
三个相位符号为正、一个为负,故 ,概率为 。该函数既非常值也不平衡。
快速检查
(当 ,确定性经典算法在四个不同输入处都看到零。在承诺下,它能否已经以确定性方式区分常值和平衡函数?)
解答 · 答案
不能。 时,四个零既可扩展为常零函数,也可通过将全部四个未见输入赋值为一,扩展为平衡函数。
快速检查
(对 和隐藏字符串 ,隐藏字符串算法测得什么?为什么其他所有振幅都为零?)
解答 · 答案
以确定性方式测得 。若 ,则 至少有一位为一;相应输入位的两个取值在相位和中相互抵消。