有界误差量子查询复杂度

形式陈述

设 $f:S\to\{0,1\}$ ， $S\subseteq\{0,1\}^n$ 。在量子查询模型中，对 $0\le\varepsilon<1/2$ ，定义

Q_\varepsilon(f) =\min_A\left\{T: \begin{array}{l} A\text{ 的每次执行至多查询 }T\text{ 次，且}\\ \Pr[A(x)=f(x)]\ge1-\varepsilon\quad\forall x\in S \end{array}\right\}.

常用简写 $Q_2(f)=Q_{1/3}(f)$ ；下标 2 表示 two-sided bounded error，不是平方。成本取每条测量分支、每个合法输入上的硬上限。若只控制期望查询数，必须另写 expected-cost 口径，不能沿用同一个 $Q_\varepsilon$ 而省略量词。

错误保证是 pointwise worst case：先固定任意合法 $x$ ，再对算法测量和内部随机性求概率。Promise 外 $x\notin S$ 可任意输出。Total function 对应完整 Boolean cube；partial function 的 oracle 仍可在所有字符串上定义，但正确性只在 $S$ 检查。

任意固定常数 $\varepsilon<1/2$ 可通过独立重跑和多数表决降到 $\delta$ 。Hoeffding 界表明重跑

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

次足够，查询成本乘 $k$ 。每次重跑都重新制备状态并末端测量；把同一次相干态重复“读取”不产生独立样本。

直觉

复杂度允许算法偶尔失败，却不允许选择一小群输入长期失败。量子振幅可以在正确子空间相长，但末端测量仍是概率事件；错误常数把几何上的可分离程度变成可比较的算法类。

固定 $1/3$ 只是 convention。常数从 $1/3$ 换到 $1/10$ 只改变常数倍查询，而把错误要求降到随 $n$ 指数小会付出额外因子。更重要的是，允许任何正错误会扩大协议集合；它与“概率一正确”的 exact 模型不是同一个对象。

例子与边界

考虑 promise 域

S=\{0^8\}\cup\{x\in\{0,1\}^8:|x|=1\},

目标为 $\operatorname{OR}(x)$ 。对唯一标记情形，均匀态中 good 振幅满足 $\sin\theta=1/\sqrt8$ 。做一次 Grover 迭代后，测得标记索引的概率为

\sin^2(3\theta) =\left(\frac{3}{\sqrt8}-\frac{4}{8\sqrt8}\right)^2 =\frac{25}{32}.

再查询测得的候选位进行验证：若它为 $1$ 输出 $1$ ，否则输出 $0$ 。总计两次 oracle 调用；在 $0^8$ 上验证总返回 $0$ ，成功率为 $1$ ，在唯一标记输入上成功率为 $25/32>2/3$ 。这是一条可逐步复算的 $Q_{1/3}\le2$ 上界。

若删去“至多一个 $1$ ”的 promise，同一个固定 Grover 迭代数不再统一可靠。例如 $|x|=4$ 时 $\theta=\pi/4$ ，一次迭代成功率为 $\sin^2(3\pi/4)=1/2$ ，低于 $2/3$ 。算法必须处理未知标记数，而不能把一个 promise 实例的概率当作 total OR 保证。

平均输入成功率也不足。若某分布几乎总取 $0^8$ ，恒输出 $0$ 的算法平均准确率可很高，却在每个唯一标记输入上必错；它不满足上述逐点定义。类似地，事后只报告“成功执行的查询数”会把失败分支成本藏掉。

推论与应用

固定错误常数后，Grover 搜索、quantum walk 和 general adversary tightness 通常都用 $Q_2$ 表述。引用渐近界时仍要保留函数是 total 还是 partial、输出是函数值还是搜索见证，以及查询成本是硬上限还是期望值。

精确算法自动满足本页的 $1/3$ 保证，所以 $Q_{1/3}(f)\le Q_E(f)$ ；反向不成立。错误放大能把正错误压低，却用有限次重复不能把它变成严格零错误。

参考资料

Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, “Quantum Lower Bounds by Polynomials,” Journal of the ACM 48(4), 2001, pp. 778–797.
Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415, 2019, Chapters 11–13.

形式陈述 ​

反向链接

形式陈述