有界误差量子查询复杂度

形式陈述

Oracle、合法输入和两个量词

O_x|i,b,w\rangle=|i,b\oplus x_i,w\rangle, \qquad i\in\{1,\ldots,n\}.

其中 $i$ 指定位置， $b$ 是回答比特， $w$ 是其余工作状态。把回答比特置为 $|{-}\rangle=(|0\rangle-|1\rangle)/\sqrt2$ ，一次调用就会把索引分量乘上 $(-1)^{x_i}$ ，得到相位查询的效果；这解释了两种常见写法的联系。

取整数 $n\ge1$ ，设 $f:S\to\{0,1\}$ ，其中非空 $S\subseteq\{0,1\}^n$ 是合法输入集合。对 $0\le\varepsilon<1/2$ ，定义

Q_\varepsilon(f)=\min\left\{T: \begin{array}{l} \text{存在量子算法 }A\text{，对每个 }x\in S\text{ 都满足}\\ \Pr[A^{O_x}=f(x)]\ge1-\varepsilon,\\ \text{且该输入上的每条执行分支至多调用 oracle }T\text{ 次} \end{array}\right\}.

一个量词约束每个输入上的成功概率，另一个约束每条执行分支的查询硬上限。不能把前者换成随机输入的平均成功率，也不能把后者换成期望查询次数。允许中间测量或自适应控制时，这一区分尤其重要。

常用 $Q_2(f)$ 表示 $Q_{1/3}(f)$ ，下标 $2$ 指有界双侧误差的传统记号。当 $S=\{0,1\}^n$ 时是全函数；否则是带承诺的偏函数。算法只对 $S$ 中的输入承担正确性要求，但 oracle 对其他 bit 串仍是合法操作，产生的接受概率仍在 $[0,1]$ 。[1]

对有限字母表的符号查询接口，也用同一公式定义 $f:D\subseteq\Sigma^n\to E$ 的 $Q_\varepsilon(f)$ ，其中输出比较改为 $E$ 中的标签相等，一次完整符号查询计一。引用带符号输入的复杂度时必须声明采用这一接口，不能默认按编码 bit 计费。

有限搜索关系 $R\subseteq D\times E$ 则把成功事件改为 $(x,A^{O_x})\in R$ ，并要求每个合法输入至少有一个允许答案；查询硬上限与逐输入错误量词不变。例如在含标记项的承诺下，Grover 搜索只需返回任意一个标记索引。多值函数仍规定唯一正确标签，关系允许多个答案；后文针对函数的多项式或 adversary 定理不能仅凭这一误差定义推广到任意关系。

定义中先选择一个算法，再要求它处理所有合法输入，不能为每个 $x$ 单独选算法。后者只需把 $f(x)$ 写进程序就可零查询，抹掉了未知输入带来的困难。若 $S$ 同时包含输出 $0$ 和输出 $1$ 的输入，任何零查询算法的输出分布与 $x$ 无关，因而在其中一类输入上错误至少为 $1/2$ ；所以此时 $Q_\varepsilon(f)\ge1$ 。

直觉

把“读取输入”单独计费

一个长度为 $n$ 的比特串藏在黑盒中，算法不能直接查看，只能调用 oracle 读取信息。经典查询通常指定一个位置；量子查询允许索引寄存器处于叠加态，再利用后续干涉组织这些信息。有界误差量子查询复杂度问的是：对每个合法输入都保持足够高的正确率，至少需要调用黑盒多少次？

这里统计的是查询次数，不是程序总运行时间。构造量子门、处理工作寄存器以及实现 oracle 本身可能很昂贵，但标准查询模型把与输入无关的计算放在查询成本之外。这是一种刻意隔离信息获取成本的模型。[1]

例子与边界

一个可以算清楚的承诺问题

考虑 $n=8$ ，承诺输入要么全为 $0$ ，要么恰有一个 $1$ ，要求判断是哪一种。先在八个索引上制备均匀叠加，再执行一次 Grover 迭代。

当恰有一个标记位置时，令 $\sin\theta=1/\sqrt8$ 。初态在标记方向上的振幅为 $\sin\theta$ ，一次迭代把它转成 $\sin3\theta$ 。由三倍角公式，

\sin3\theta =3\sin\theta-4\sin^3\theta =\frac{5}{2\sqrt8}, \qquad \sin^2 3\theta=\frac{25}{32}.

测量得到候选索引后，再查询一次该位置，只有读到 $1$ 才回答“存在”。Grover 迭代中的相位标记用一次 oracle，最后验证再用一次，总共两次查询。全零输入上永远回答“不存在”；单标记输入上以 $25/32>2/3$ 的概率回答“存在”。因此，该承诺问题的 $Q_{1/3}$ 至多为 $2$ ；这个构造本身没有证明下界。

这段构造使用了承诺中的标记数限制。若八位输入有四个 $1$ ，则 $\theta=\pi/4$ ，一次迭代后的命中概率为 $\sin^2(3\pi/4)=1/2$ ，达不到 $2/3$ 。处理任意标记数时，需要重新选择迭代策略。

测量索引寄存器总会给出某个位置，包括全零输入。因此候选位置本身还不是存在性证据；最后一次读取候选位，才把搜索结果转成“仅在确实找到 $1$ 时接受”的单侧判定。

推论与应用

常数误差为什么通常不影响阶数

设一个算法每次使用至多 $T$ 次查询，对每个合法输入的错误率至多 $\varepsilon<1/2$ 。重新初始化并独立运行 $k$ 次，最后按独立重复的多数规则输出。多值输出时取获得严格过半票的标签；不存在时任选一个固定标签。正确标签只要超过半数就必被选中，Hoeffding 界因而给出

\Pr[\text{多数票错误}] \le \exp\bigl(-2k(1/2-\varepsilon)^2\bigr).

因此，为把错误率降至 $0<\delta<1/2$ ，取

k=O\!\left(\frac{\log(1/\delta)}{(1/2-\varepsilon)^2}\right)

即可，总查询硬上限为 $kT$ 。当起始和目标误差都是固定的正数且严格小于 $1/2$ 时，额外开销只是常数倍。若起始优势 $1/2-\varepsilon$ 随 $n$ 缩小，这个倍数就不再是常数。

重复降低的是概率，并没有在有限次运行后把非零错误变成零。按本页的固定硬上限约定， $Q_\varepsilon$ 在 $\varepsilon=0$ 的端点对应精确量子查询复杂度 $Q_E$ ；有些文献把 $Q_0$ 留给另一类零误差模型，引用记号时需要区分。定义直接给出 $Q_{1/3}(f)\le Q_E(f)$ ，不保证两者同阶。

怎样证明查询已经足够少

给出算法只证明上界；要说明最优，还得证明任何允许的算法都不能更省查询。对全函数 $\operatorname{OR}_n$ ，有 $Q_{1/3}(\operatorname{OR}_n)=\Theta(\sqrt n)$ ：搜索算法给出上界，量子查询下界排除更快的黑盒方法。[1]

量子查询多项式方法利用一个结构事实： $T$ 次查询后的接受概率，在布尔输入上可写成次数至多 $2T$ 的实多重线性多项式。如果函数无法被更低次数的多项式逐点近似，就得到查询下界。对手方法则跟踪答案不同的输入所产生状态之间的可区分性，限制一次查询能推进多少。

这些方法比较的是模型内的算法。不能把一次叠加查询理解为“测量后得到所有 $n$ 位”，也不能把较少查询直接换算为实际设备上的同倍加速；量子优势来自对有限可读出信息的相干组织。

参考资料

[1] Ronald de Wolf，Quantum Computing: Lecture Notes，Grover 搜索、量子查询下界与广义对手界各章：oracle 模型、成功概率和查询复杂度。

[2] Robert Beals 等，Quantum Lower Bounds by Polynomials，Journal of the ACM 48(4)，2001，778–797：接受概率的次数界与多项式下界方法。

形式陈述 ​

Oracle、合法输入和两个量词 ​

把“读取输入”单独计费 ​

一个可以算清楚的承诺问题 ​

常数误差为什么通常不影响阶数 ​