量子查询模型

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

Workspace 允许保存路径标记、候选数据和辅助 qubit，但免费空间与免费本地计算不等于免费输入信息。两份输入若让少量 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以每个 promise 输入上的点态成功概率和最坏硬查询上限定义有界误差量子查询复杂度。允许每个合法输入有小失败概率，精确口径公理库精确量子查询复杂度Exact quantum query complexity · Exact quantum queries要求每个合法输入上以概率一给出函数值的最小最坏量子 oracle 调用数。则要求概率一正确；promise 外行为不受约束。

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