精确量子查询复杂度

量子测量通常带概率，但正交状态仍可被确定地区分。Exact 算法的任务是让所有 0-输入终态进入一个子空间、所有 1-输入终态进入正交子空间；每一类内部的状态不必相同。干涉可以用较少查询计算关系，却不能留下任何“很小但非零”的错误振幅。

误差放大只让错误趋近零，不会在有限次重复后自动等于零。故 exact 不是把 bounded-error 中的常数换成更小常数，而是改变可接受协议集合；多项式表示也从近似约束变成逐点精确约束。

对 total parity

把坐标两两配对。对第 $(2j-1,2j)$ 对，初始化索引态

和回答态 $|-⟩$。一次 bit 查询后，两项分别带 $(-1{)}^{x_{2j-1}}$ 与 $(-1{)}^{x_{2j}}$；在和、差基测量便确定这两个 bit 的 xor。把所有配对 xor 经典相加；若 $n$ 为奇数，再直接查询最后一位。因此

下界复用查询多项式定理理路查询下界的多项式方法Polynomial method for query lower bounds · Query polynomial method将 T-query 算法的接受概率表示为低次多项式，再用精确次数或近似次数排除过少查询。：$T$ 次量子查询的接受概率次数至多 $2T$，而 parity 的精确多项式次数为 $n$。于是 $2T\ge n$，整数化后

经典确定性算法需要 $n$ 次查询；任一未读位都能翻转 parity。这给出全函数上的精确量子优势：查询数由 $n$ 降到 $\lceil n/2\rceil$。

边界还包括定义域。若只在某个 promise 子集计算 parity，精确多项式只需在该子集匹配，次数下界可能下降。若最终输出允许多个合法答案，则对象是 relation，不再由上述布尔输出投影直接描述。

精确算法的正确性证明要验证不同输出对应的终态子空间正交。分析电路时，应明确整体相位的参考和 oracle 的控制方式；统计成本时，还要计入逆 oracle 调用。这些模型约定决定了所展示的区分操作能否按声称的预算实现。

精确多项式次数给出通用下界，但最多通过 $2T$ 损失因子二，也未必总是紧。更强 exact 下界可能需要 adversary、sum-of-squares 或问题专用结构；不能把低次精确多项式自动反演成同阶量子算法。