量子查询模型

形式陈述 ​

取整数 $n\ge 1$ 与非空合法域，设偏布尔函数公理库布尔函数Boolean function以有限 Boolean cube 为定义域、输出单个真假值的函数，并区分偏函数、支持变量与限制操作。 $f:S\to \{0,1\}$，其中 $S\subseteq \{0,1{\}}^n$；total function 是 $S=\{0,1{\}}^n$ 的情形。算法的索引、回答位与工作空间组成一个复合量子系统公理库复合量子系统Composite quantum system · Bipartite quantum system复合量子系统以各子系统空间的张量积为状态空间，并用联合密度算子区分乘积态、可分态与纠缠态。，有限维状态空间写成

$$\mathcal{H}={\mathcal{H}}_I\otimes {\mathcal{H}}_B\otimes {\mathcal{H}}_W.$$

索引寄存器有基 $\{|i⟩:i\in [n]\}$，回答寄存器基为 $\{|0⟩,|1⟩\}$，${\mathcal{H}}_W$ 是任意有限维 workspace。纯态公理库量子纯态Quantum pure state · Pure quantum state · 纯态量子纯态由复内积空间的单位向量表示，忽略整体相位；量子比特的纯态是二维情形，一般混态则用密度算子描述。用范数为一的复向量表示，并忽略整体相位；可逆步骤是保持内积的酉矩阵公理库正交矩阵与酉矩阵Orthogonal matrix · Unitary matrix · 酉矩阵在实或复内积空间中保持内积的方阵，其逆分别等于转置或共轭转置。。输入 $x$ 只通过 bit oracle

$$O_x|i,b,w⟩=|i,b\oplus x_i,w⟩$$

进入计算。一次调用无论索引是单个 $i$ 还是叠加 $\sum _i{\alpha }_i|i⟩$，都计一次查询。

一个 $T$-query 算法由与 $x$ 无关的初态 $|{\psi }_0⟩$ 和 unitaries $U_0,\dots ,U_T$ 给出，最终态为

$$|{\psi }_x⟩=U_T{O}_x{U}_{T-1}\cdots O_x{U}_0|{\psi }_0⟩.$$

最后用二结果投影测量 $\{{\mathrm{\Pi }}_0,{\mathrm{\Pi }}_1\}$ 输出，其中 ${\mathrm{\Pi }}_a^{†}={\mathrm{\Pi }}_a={\mathrm{\Pi }}_a^2$、${\mathrm{\Pi }}_0+{\mathrm{\Pi }}_1=I$；接受概率是

$$p(x)=\Vert {\mathrm{\Pi }}_1|{\psi }_x⟩{\Vert }^2.$$

若直接采用POVM公理库正算子值测度（POVM）Positive operator-valued measure · POVM · 正算子值测度有限结果 POVM 是一组和为恒等算子的半正定效应算子，它通过迹公式规定各测量结果的概率。 $\{E_0,E_1\}$，接受概率应写为 $⟨{\psi }_x|E_1|{\psi }_x⟩$，而不是 $\Vert E_1|{\psi }_x⟩{\Vert }^2$；要求这两种写法对所有输入态都一致，当且仅当 $E_1$ 为投影；某个特定态上的相等并不足以推出这一点。更一般的混态、POVM 或中途测量可借助额外 workspace 做量子态纯化公理库量子态纯化Quantum state purification · Purification of a quantum state量子态纯化将一个混态表示成较大系统中纯态的约化态，最小辅助空间维数等于原态的秩。或将测量延迟到末尾。具体说，把测量操作的Kraus 分支公理库Kraus 表示Kraus representation · Operator-sum representation · 算子和表示有限维线性映射完全正当且仅当它能写成 Kraus 算子和，保持迹则等价于这些算子的完备性恒等式。相干地保存到辅助寄存器，再以它控制后续输入无关操作，最终一起测量即可；这保留输出分布，不是提前知道测量结果。

若原算法某些分支提早停止，统一为 $T$ 个查询时刻还要让已停止分支执行无效查询。标准 bit oracle 的回答位可以放在 $|+⟩$，因为 $X|+⟩=|+⟩$，此时 oracle 不改变该分支；用输入无关的受控交换把实际回答位暂存即可。因此每分支硬上限为 $T$ 的算法可写成上述形式。若硬上限只在合法域内保证，先把原算法强制在第 $T$ 次查询后停止，再做上述补齐；这不改变合法输入的行为。只有期望次数界的算法不能如此直接补齐。所有 $U_t$、初态和测量都不得依赖未知 $x$；否则算法可把答案偷偷写入“免费”步骤。

该模型沿用坐标查询模型公理库查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。的成本问题，却把一次读取改成相干的可逆访问。受控相位 oracle公理库量子查询中的相位 OraclePhase oracle in quantum query complexity · Phase-kickback oracle用输入 bit 控制计算基相位，并在受控接口下精确说明它与标准 bit oracle 的一查询双向转换。在明确接口下与上述 bit oracle 保持常数一的查询等价，转换条件不能省略。

有限字母表的符号查询 ​

当一个坐标存储整个符号时，取有限非空字母表 $\mathrm{\Sigma }$、有限非空输出集 $E$、非空 $D\subseteq {\mathrm{\Sigma }}^n$ 及函数 $f:D\to E$。固定公开单射编码 $\mathrm{enc}:\mathrm{\Sigma }\to \{0,1{\}}^b$，其中 $b=max\{1,\lceil {\log }_2|\mathrm{\Sigma }|\rceil \}$，将回答寄存器改为 $b$ 个 qubit，并提供

$$O_x|i,z,w⟩=|i,z\oplus \mathrm{enc}(x_i),w⟩.$$

异或使它在完整回答空间上成为自逆酉算子；一次调用读取一个符号，仍只计一次。输出改用 $E$ 标记的有限结果 POVM，其余输入无关步骤和硬查询预算保持原约定。回答寄存器的均匀态对每个异或平移不变，所以停止分支也能执行无效查询。

这一符号接口支撑有限字母表的对手界公理库量子查询的正权 Adversary 方法Positive-weight quantum adversary method · Ambainis adversary method以非负输入对权矩阵的谱范数与单坐标可区分进度之比，证明量子查询下界。及元素互异性。若另一文献以模 $|\mathrm{\Sigma }|$ 加法写值查询，可先查询一个干净辅助寄存器，执行所需可逆更新，再用逆查询清理；两个方向的模拟各至多用两次查询。模加查询的逆可用回答寄存器取负、查询、再取负实现。因而两种完整值接口在常数因子内等价，但不能把长度 $b$ 的符号拆成 $b$ 个独立 bit 查询后仍照搬原成本。前文与受控相位接口的一查询等价专指布尔 bit 情形。

直觉

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

Workspace 允许保存路径标记、候选数据和辅助 qubit，但免费空间与免费本地计算不等于免费输入信息。对输入 $x,y$，同一个输入无关 unitary 保持两态内积：$⟨U{\psi }_x|U{\psi }_y⟩=⟨{\psi }_x|{\psi }_y⟩$。用迹距离公理库迹距离Trace distance · Quantum trace distance迹距离是两个密度算子之差的迹范数的一半，恰好刻画单份量子态在最优测量下的可区分程度。衡量一般状态的可区分度时，共同酉操作同样保持距离。它能重新安排已有信息，却不能单独使两种输入更可区分；真正改变内积的是两输入对应的不同 oracle。量子下界因此集中限制一次查询能使可区分度增加多少。

例子与边界

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

$$|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}},$$

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

$$O_x\frac{|1⟩+|2⟩}{\sqrt{2}}|-⟩=\frac{(-1{)}^{x_1}|1⟩+(-1{)}^{x_2}|2⟩}{\sqrt{2}}|-⟩.$$

若 $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 接口成立；若一次查询能返回区间和、哈希或多个坐标，原界没有可移植性。

推论与应用

普通门如何嵌入寄存器、为何先 $U$ 后 $V$ 对应矩阵 $VU$，以及经典测量控制与量子受控门如何区分，见量子电路公理库量子电路Quantum circuit用固定寄存器上的酉门、测量和经典控制表示有限量子操作序列，并明确基顺序、矩阵乘法与测后更新。。本页只对 oracle 调用计费，不能把这项约定推广成一般电路的门数成本。

量子相位估计公理库量子相位估计Quantum phase estimation · QPE用受控酉幂将特征相位写入控制寄存器，再以逆 Fourier 变换读出，推导精确情形、有限概率分布与实际查询成本。使用另一种显式接口：给定特征态和受控酉幂。若这些幂由基本受控 $U$ 重复实现，$m$ 条控制线需要 $2^m-1$ 次基本调用；这与“直接提供 $m$ 个幂黑盒”是不同的查询账。把该算法放进本页的布尔输入模型时，还要逐项实现受控访问并计算内部 $O_x$ 次数。

固定这一形式后，复杂度差异只来自允许的错误协议和完成任务所需的查询数。有界误差公理库有界误差量子查询复杂度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$ 会同时摧毁两条证明链。

自测：将索引基 $|1{⟩}_I,|2{⟩}_I$ 分别编码为一个 qubit 的计算基 $|0⟩,|1⟩$；这里 $1,2$ 是输入坐标标签，$0,1$ 是编码后的测量结果标签。分别对输入 $00,01,10,11$ 执行例中的一次查询，并在这个编码下对索引 qubit 施加 Hadamard。忽略整体相位后，输出依次应为 $0,1,1,0$；回答位始终保持 $|-⟩$。若将索引寄存器在查询前测量，原先依靠相对相位的这条计算轨迹便不再成立。

参考资料

• Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf, “Quantum Lower Bounds by Polynomials,” FOCS 1998 会议版；期刊版 Journal of the ACM 48(4), 2001, pp. 778–797，黑盒访问与振幅表示。
• Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
• Michael A. Nielsen and Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010, Chapters 2 and 6.