量子查询模型

经典查询在某一时刻选定一个索引并得到一个可复制答案；量子查询把索引振幅同时送进同一个 $O_x$。Oracle 并未一次吐出全部 $n$ 个 bit：测量只能从最终状态提取有限结果，真正优势来自各索引分支携带的相位经过后续 unitary 相消或相长。

Workspace 允许保存路径标记、候选数据和辅助 qubit，但免费空间与免费本地计算不等于免费输入信息。对输入 $x,y$，同一个输入无关 unitary 保持两态内积：$⟨U{\psi }_x|U{\psi }_y⟩=⟨{\psi }_x|{\psi }_y⟩$。它能重新安排已有信息，却不能单独使两种输入更可区分；真正改变内积的是两输入对应的不同 oracle。量子下界因此集中限制一次查询能使可区分度增加多少。

考虑 $n=2$ 的 parity。把回答 qubit 从 $|1⟩$ 经 Hadamard 变成

并令索引为 $(|1⟩+|2⟩)/\sqrt{2}$。一次 bit 查询产生 phase kickback：

若 $x_1\oplus x_2=0$，索引态是 $(|1⟩+|2⟩)/\sqrt{2}$ 乘一个不可观测的整体相位；若 parity 为 $1$，它是 $(|1⟩-|2⟩)/\sqrt{2}$ 乘整体相位。测量这两个正交基向量便以一次查询精确得到 parity。经典确定性坐标算法必须读两位，因为只见一位时，另一位的两种补全给出不同答案。

这条轨迹不表示一次量子查询“读出了两位”。测量只揭示一个关系 $x_1\oplus x_2$；无法随后同时恢复 $x_1,x_2$。若把 oracle 改成测量并返回经典 $x_i$，分支相位会被破坏，算法退回经典自适应查询。

模型还忽略门数、容错、制备精度与物理噪声。一个查询上界可能使用巨大的输入无关 unitary，故不自动是快速电路。反之，下界只在声明的 oracle 接口成立；若一次查询能返回区间和、哈希或多个坐标，原界没有可移植性。

固定这一形式后，复杂度差异只来自允许的错误协议和完成任务所需的查询数。有界误差公理库有界误差量子查询复杂度Bounded-error quantum query complexity · Quantum query complexity在每个合法输入上错误率至多为给定常数、且每条执行分支满足查询硬上限的量子 oracle 调用复杂度。允许每个合法输入有小失败概率，精确口径公理库精确量子查询复杂度Exact quantum query complexity · Exact quantum queries要求每个合法输入上以概率一给出函数值的最小最坏量子 oracle 调用数。则要求概率一正确；promise 外行为不受约束。

同一模型也支撑两类下界。Polynomial method 跟踪振幅对 $x_i$ 的代数次数，adversary method 跟踪不同输入状态间的内积变化。二者都依赖输入只经 $O_x$ 进入；允许 $U_t$ 查看 $x$ 会同时摧毁两条证明链。