有界误差量子查询复杂度

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

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

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

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

考虑 $n=8$，承诺输入要么全为 $0$，要么恰有一个 $1$，要求判断是哪一种。先在八个索引上制备均匀叠加，再执行一次 Grover 迭代公理库Grover 搜索查询复杂度Grover search query complexity · Unstructured quantum search以二维振幅旋转在无结构空间寻找标记项，并由 BBBV 下界刻画其平方根查询复杂度最优性。。

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

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

为什么不能直接宣布解决了八位的任意 OR？若有四个 $1$，则 $\theta =\pi /4$，一次迭代后的命中概率是 ${\sin }^2(3\pi /4)=1/2$，达不到 $2/3$。同一算法在承诺内有效，在承诺外失去保证。对任意标记数的搜索，需要合适的迭代次数选择或其他处理，而不是固定重复一次。

最后的验证查询也承担单侧错误保证：全零时，任意测得的索引都被验证否决；单标记时，只有测中标记才能接受。如果省掉验证、只把“测出了一个索引”当作存在性证据，那么全零时同样总会测出某个索引，算法就必错。因而搜索到候选位置与判定存在性是两项不同义务，查询账必须覆盖后者。

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

设一个算法每次使用至多 $T$ 次查询，对每个合法输入的错误率至多 $\epsilon <1/2$。重新初始化并独立运行 $k$ 次，最后取多数票。Hoeffding 型界给出

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

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

重复降低的是概率，并没有在有限次运行后把非零错误变成零。按本页的固定硬上限约定，$Q_{\epsilon }$ 在 $\epsilon =0$ 的端点对应精确量子查询复杂度公理库精确量子查询复杂度Exact quantum query complexity · Exact quantum queries要求每个合法输入上以概率一给出函数值的最小最坏量子 oracle 调用数。 $Q_E$；有些文献把 $Q_0$ 留给另一类零误差模型，引用记号时需要区分。定义直接给出 $Q_{1/3}(f)\le Q_E(f)$，不保证两者同阶。

怎样证明查询已经足够少 ​

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

量子查询多项式方法公理库量子查询的多项式方法Polynomial method for quantum query complexity · Quantum query polynomial lower bound复用接受概率的二倍查询次数上界，以近似次数及其对偶见证推出量子查询下界。利用一个结构事实：$T$ 次查询后的接受概率，在布尔输入上可写成次数至多 $2T$ 的实多重线性多项式。如果函数无法被更低次数的多项式逐点近似，就得到查询下界。对手方法公理库量子查询的正权 Adversary 方法Positive-weight quantum adversary method · Ambainis adversary method以非负输入对权矩阵的谱范数与单坐标可区分进度之比，证明量子查询下界。则跟踪答案不同的输入所产生状态之间的可区分性，限制一次查询能推进多少。

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