量子查询的多项式方法

查询次数限制接受概率能表现的变量交互阶数；approximate degree 询问目标函数是否可被这种低阶行为逐点模拟。Dual witness 则挑出一个低阶行为全部看不见、目标函数却看得见的方向。算法、逼近和见证形成一条闭合证据链。

与量子 adversary 方法理路量子查询的正权 Adversary 方法Positive-weight quantum adversary method · Ambainis adversary method以非负输入对权矩阵的谱范数与单坐标可区分进度之比，证明量子查询下界。不同，多项式法压缩的是输入到接受概率的代数次数，而非输入对之间状态重叠的变化。二者可在同一问题上给不同强度；不存在“量子下界”这一标签下的自动互换。

先用四点例子完整走链。对 ${\mathrm{OR}}_2$ 和误差 $1/3$，取

它与常数多项式正交、一范数为 $1$，且与 OR 的相关性为 $1/2>1/3$，所以近似次数大于 $0$。若零查询量子算法存在，其接受概率 $p$ 必为常数，便有 $⟨\psi ,p⟩=0$；误差约束却强迫相关性差至多 $1/3$，与 $1/2$ 冲突。因此 $T\ge 1$。这个例子也有匹配的一次查询上界：均匀选择两个位置之一，读到 $1$ 就接受；读到 $0$ 则以概率 $1/3$ 接受。输入 $00$ 上错误为 $1/3$，输入 $01,10$ 上错误为 $(1/2)(2/3)=1/3$，输入 $11$ 上不出错。这是量子模型也可执行的经典随机协议，故 $Q_{1/3}({\mathrm{OR}}_2)=1$。它计算的是有界误差答案，不是把一位观察误当成零错误证书。

在渐近尺度上，已知定理给出

代入即得 $Q_{1/3}({\mathrm{OR}}_n)=\mathrm{\Omega }(\sqrt{n})$，与 Grover 上界匹配。近似次数下界的实质来自对称化后的一元多项式不等式，或等价的纯高次 dual witness；仅写“接受概率次数至多 $2T$”还没有证明 OR 的次数需求。

对 promise problem，多项式只需在 $D$ 上逼近，dual witness 也只能在 $D$ 上放质量。对 expected-query 算法，某些分支可能任意长，不能直接指定统一的次数 $2T$；需先截断并把截断失败计入误差。

方法适合已有 approximate-degree 或显式 dual polynomial 的函数，并能区分 exact、two-sided、one-sided 和 sign 等代数口径。低 approximate degree 只是下界不强，不能反向推出低查询算法；接受概率多项式还受非负性、归一化与可实现性约束。

不可普遍快进定理理路量子模拟的不可快进定理No-fast-forwarding theorem以范数一的加权路径Hamiltonian把隐藏输入奇偶传播到终点，证明每次稀疏访问只需常数次bit查询，从而得到最坏情形线性时间查询下界。把这条查询下界链用于 Hamiltonian 模拟：将输入位藏进稀疏加权路径的翻转标签，线性演化时间后的终点读出整个输入的奇偶性。每次稀疏 oracle 调用只需常数次位查询，PARITY 的次数下界便限制模拟查询数；必须把这个接口归约写出，不能只比较矩阵指数的形式。

多项式法可证明 collision、element distinctness 等问题的强下界，也可经 symmetrization 把高维输入降为 Hamming 重量的一元问题。但每次降维都必须保留 promise 点和误差区间，不能在整数点有界后无条件假设整个实区间同样有界。