精确量子查询复杂度

量子测量通常带概率，但正交状态仍可被确定地区分。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。这是真实的 exact 量子优势，却只有因子二，不应由 Deutsch–Jozsa 的 promise 指数分离推断所有 total functions 都有同样现象。

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

Exact 算法是检查模型 convention 的好校准器：整体相位是否有参考、oracle 是否受控、查询逆 oracle 是否收费，都会决定两个终态能否真正正交。只报告“振幅接近 1”仍是 bounded error，不是 exact 证明。

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