量子查询的正权 Adversary 方法

形式陈述 ​

取整数 $n\ge 1$、有限非空字母表 $\mathrm{\Sigma },E$、非空 $D\subseteq {\mathrm{\Sigma }}^n$，设 $f:D\to E$。采用有界误差复杂度的符号查询版本理路有界误差量子查询复杂度Bounded-error quantum query complexity · Quantum query complexity在每个合法输入上错误率至多为给定常数、且每条执行分支满足查询硬上限的量子 oracle 调用复杂度。：一次 oracle 调用返回一个完整符号的相干编码。对每个坐标 $i$ 定义差异矩阵

正权 adversary matrix 是以合法输入为行列的非零实对称矩阵 $\mathrm{\Gamma }$，满足逐项非负 $\mathrm{\Gamma }[x,y]\ge 0$，且 $f(x)=f(y)$ 时 $\mathrm{\Gamma }[x,y]=0$。注意“逐项非负”不等于 positive semidefinite。定义

其中 $\Vert \cdot \Vert$ 是矩阵的谱范数理路矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力，并区分算子范数、Frobenius 范数与谱半径。 $\Vert \cdot {\Vert }_2$，$\circ$ 是 Hadamard product。若 $f$ 为常函数，非零矩阵的可行集为空，另约定 ${\mathrm{Adv}}^{+}(f)=0$。否则任何允许的非零项都连接两个不同输入，至少一个坐标不同，故分母为正。对任意固定 $0\le \epsilon <1/2$，

给出有界误差量子查询下界理路有界误差量子查询复杂度Bounded-error quantum query complexity · Quantum query complexity在每个合法输入上错误率至多为给定常数、且每条执行分支满足查询硬上限的量子 oracle 调用复杂度。。

证明的进度量可写得更明确。由谱定理理路有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基；实数情形对应自伴算子。及逐项非负性，可选非负单位向量 $v$，使 $\mathrm{\Gamma }v=\Vert \mathrm{\Gamma }\Vert v$：取达到最大绝对 Rayleigh 商的向量并逐项取绝对值，商不会减小。令

初态与输入无关，故 $W_0=\Vert \mathrm{\Gamma }\Vert$。对 $f(x)\ne f(y)$，将终态按输出投影分解并应用Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积，且等号精确刻画线性相关。，得到 $|⟨{\psi }_x^T|{\psi }_y^T⟩|\le 2\sqrt{\epsilon (1-\epsilon )}$。非负权重于是给 $|W_T|\le 2\sqrt{\epsilon (1-\epsilon )}\Vert \mathrm{\Gamma }\Vert$。按查询索引拆分各输入态后，只有 $x_i\ne y_i$ 的项会改变；对查询前后的两项分别用算子范数界，可得 $|W_{t+1}-W_t|\le 2\underset{i}{max}\Vert \mathrm{\Gamma }\circ {\mathrm{\Delta }}_i\Vert$。相加即给

这里的系数在 $\epsilon <1/2$ 时为正；一次完整符号查询也满足相同的逐坐标界。

这不是经典决策树对手理路对手下界方法Adversary lower-bound method · Adversary argument以全局一致的延迟回答维持多个候选输入，证明有限查询无法区分所需输出的方法。。经典方法在线选择一致回答；量子 adversary 固定整个输入对矩阵并分析一族同时演化的量子态，不能让“对手”在运行中观察测量随机性后改输入。