量子顺序搜索

在 Grover 算法中我们研究过一个极端：对数据库的结构一无所知，$N$ 个条目里藏着一个目标，量子搜索把 $\Theta (N)$ 次查询降到 $\Theta (\sqrt{N})$，获得平方根加速。本词条研究另一个极端：数据库完全有序——$N$ 个条目已经从小到大排好，要把一个新元素 $x$ 插到正确的位置上，唯一的信息来源是”拿 $x$ 与表中第 $i$ 个元素比较”。这就是有序搜索 (ordered search) 问题，即二分搜索 (binary search) 的量子版本。

经典答案早已写进每一本算法教材：二分搜索用 $\lceil {\log }_2(N+1)\rceil$ 次比较，而且这是最优的（第 2 节给出两个证明）。因此量子算法再怎么好，也只能改善 ${\log }_{2}N$ 前面的常数因子——量级上不可能重演 Grover 式的平方根飞跃。乍看之下这个问题”不值得量子化”，事实恰恰相反，它成了量子查询复杂度中精确常数研究得最透彻的试验场：

• 1999 年，Farhi、Goldstone、Gutmann 与 Sipser 给出第一个超越二分搜索的量子算法，查询数约为 $0.53{\log }_{2}N$（Zoo 编号 39）；
• Høyer、Neerbek、Shi（以及后来 Childs–Lee 的最优化处理）用对抗方法证明：任何量子算法至少需要 $\frac{\ln 2}{\pi }{\log }_{2}N-O(1)\approx 0.221{\log }_{2}N$ 次查询（Zoo 编号 219、24）；
• 2006 年，Childs、Landahl、Parrilo 把”找算法”本身变成一个半定规划 (semidefinite program, SDP) 问题，数值搜索出小规模精确模块，再递归拼接成任意规模算法，把上界推进到 $4{\log }_{605}N+O(1)\approx 0.433{\log }_{2}N$（Zoo 编号 103）；
• 2007 年，Ben-Or 与 Hassidim 用 adaptive learning 把期望查询数降到 $\frac{1}{3}{\log }_{2}N$ 以下（Zoo 编号 10）。

一句话总结现状：有序搜索的量子查询复杂度是 $\Theta (\log N)$，精确口径下渐近常数 $c$ 落在 $0.221\dots \le c\le 0.433\dots$ 之间，至今没有闭合。

这个问题的方法论价值不亚于其结论。如何证明一个小量子线路是某个问题的最优解？如何系统地搜索好的小线路，而不是靠灵感手拼？本词条要讲的答案是：把”存在一个 $Q$ 次查询的算法”翻译成一组关于半正定矩阵的线性约束（一个 SDP 可行性问题），然后一边用对称性把它压缩到可解的规模，一边用递归把小模块拼成大算法；下界侧则用对抗矩阵的谱范数比值。上界与下界在 SDP 的语言里遥相呼应，这也是本词条（查询复杂度、span program 与性质测试）反复出现的主题。

前置知识：的 Grover 算法（相位 oracle、查询模型、反射与旋转的语言）。半定规划方面，本词条自含所需的一点点内容：读者只需接受”变量是半正定矩阵、约束是线性等式”就是一个可以数值求解的问题。

1. 问题的精确表述

1.1 插入位置：$N+1$ 种答案

设表中元素严格递增：

$y_0<y_1<\cdots <y_{N-1},$

并引入哨兵 $y_{-1}=-\infty$、$y_N=+\infty$。约定 $x$ 不等于任何 $y_i$（若可能与某个 $y_i$ 相等，先花一次比较把该情形剔除即可，不影响渐近行为）。于是存在唯一的插入位置

$t\in \{0,1,\dots ,N\},y_{t-1}<x<y_t,$

任务是确定 $t$。注意答案共有 $N+1$ 种——这个"$+1$"贯穿全文：它既出现在经典下界 $\lceil {\log }_2(N+1)\rceil$ 中，也是后文矩阵的尺寸。

1.2 比较是阈值函数

与 $y_i$ 的一次比较只能问”$x$ 是否大于 $y_i$“，其答案由 $t$ 完全决定。推导只用到插入位置的定义：

$x>y_i⟺x\text{ 高于 }{y}_i⟺i\le t-1⟺i<t.$

也就是说，知道 $t$ 就知道所有比较的答案；反之，比较是仅有的信息来源。这提示我们把输入抽象为阈值 $t$、把比较抽象为 oracle，进入查询复杂度模型：算法看不见数据本身，只能通过 oracle 提问，我们只数提问次数。

1.3 阈值 oracle 与相位形式

把”$x$ 应插到排序表哪里”改写为未知阈值 $t\in \{0,\dots ,N\}$。定义位串（查询位置 $i\in \{0,\dots ,N-1\}$）

$$z_i^{(t)}=\{\begin{array}{ll}0,& i<t,\\ 1,& i\ge t.\end{array}$$

$z^{(t)}$ 是一条阶跃函数：前 $t$ 个位置为 $0$，其后全为 $1$。oracle 可用相位形式

$$O_t|i⟩=(-1{)}^{z_i^{(t)}}|i⟩,$$

即对”阈值右侧”的基矢翻转相位。由第 1.2 节，比较的答案 $[x>y_i]=1-z_i^{(t)}$，与 $z_i^{(t)}$ 逐位互补；互补意味着相位整体差一个全局因子 $-1$，对任何测量概率无影响，故两种约定等价。以下统一采用 $z$ 约定（与文献一致）。

例 1（$N=3$ 的四个 oracle）。阈值 $t\in \{0,1,2,3\}$，位置 $i\in \{0,1,2\}$：

$t$	$z^{(t)}=(z_0,z_1,z_2)$	相位向量
0	$(1,1,1)$	$(-,-,-)$
1	$(0,1,1)$	$(+,-,-)$
2	$(0,0,1)$	$(+,+,-)$
3	$(0,0,0)$	$(+,+,+)$

两个直接可验证的特征值得记住：

• 支撑嵌套（链结构）：$\{i:z_i^{(0)}=1\}\supseteq \{i:z_i^{(1)}=1\}\supseteq \cdots \supseteq \{i:z_i^{(N)}=1\}=\varnothing$。这 $N+1$ 条相位模式不是彼此独立的，而是首尾相衔的一条链；
• 汉明距离：$z^{(s)}$ 与 $z^{(t)}$ 不同的位置恰好是 $\min (s,t)\le i<\max (s,t)$，共 $|s-t|$ 个。相邻阈值（$|s-t|=1$）的 oracle 只在一个位置上不同——它们是”最难区分”的输入对。

经典算法每次比较最多把候选区间二分，因此最坏至少 $\lceil {\log }_2(N+1)\rceil$ 次，binary search 达到该界（第 2 节证明）。量子查询可以在多个 $i$ 的叠加上同时施加相位，但如例 1 所示，不同阈值 oracle 的相位模式高度相关（嵌套链、相邻者几乎相同），所以不会像无结构搜索那样获得平方根加速——第 4 节把这个直觉讲透，第 8 节给出证明。

1.4 查询算法与复杂度的三种口径

量子查询算法按如下方式运行。寄存器分为查询寄存器（基矢 $|i⟩$，$i=0,\dots ,N-1$）与工作寄存器（任意维数，存放辅助信息）。初态与输入无关；随后输入无关的酉变换与 oracle 调用交替进行。记第 $q$ 次查询前的算法态为 $|{\psi }_t^{(q)}⟩$（它依赖输入 $t$），则

$$|{\psi }_t^{(0)}⟩=|\mathrm{init}⟩,|{\psi }_t^{(q+1)}⟩=U^{(q)}{O}_t|{\psi }_t^{(q)}⟩,$$

其中每个 $U^{(q)}$ 都是输入无关的酉。查询复杂度是 $O_t$ 的调用次数（$U^{(q)}$ 的门数不计）。按对”成功”的记账方式，有三种口径：

1. 精确、最坏情形：对每个输入都零误差地输出 $t$，查询数按最坏输入计；
2. 有界误差：每个输入的错误概率至多 $\epsilon$，仍按最坏输入计；
3. 期望：对某个输入分布（通常取均匀）平均的查询数。

这三种口径的数值不能直接比较大小（第 8.4 节详细讨论）。另需提醒（与本词条导言一致）：查询模型不计实现各个 $U^{(q)}$ 的代价，查询优势不等于无条件的时间优势。

2. 经典世界：二分搜索与两个下界

2.1 二分搜索

算法：维护一个候选区间（初始为全部 $N+1$ 个阈值），每次比较区间中点位置的元素，由第 1.2 节，答案告诉我们 $t$ 在中点左侧还是右侧，区间长度大约减半；区间缩到 1 时输出。最坏情形的比较次数是 $\lceil {\log }_2(N+1)\rceil$。

引理 1（决策树下界，最坏口径）。任何确定性比较算法在最坏输入下至少做 $\lceil {\log }_2(N+1)\rceil$ 次比较。

证明。比较算法是一棵二叉决策树：每个内点一次比较、有两个孩子；每个叶子输出一个答案。要正确，$N+1$ 个答案各需至少一片叶子，故叶子数 $\ge N+1$；深度为 $d$ 的二叉树至多 $2^d$ 片叶子，于是 $2^d\ge N+1$，即 $d\ge \lceil {\log }_2(N+1)\rceil$。Q.E.D.

2.2 随机化也逃不掉：熵下界（期望口径）

允许随机化、按期望计数，能否把经典的常数压低？答案是几乎不能：

引理 2（期望口径的熵下界）。对均匀分布的阈值 $t$，任何零误差的随机化比较算法的期望比较次数至少 ${\log }_2(N+1)$。

证明。分三步。

第一步（前缀码的熵界）：固定随机串 $r$ 后算法是确定性的自适应策略，其答案序列 $a_1{a}_2\cdots a_T$（$T$ 为停止时刻）天然自终止——算法一旦停止序列即结束，因此任何两个可能的答案序列都互不为对方前缀，构成前缀码。对长度为 ${\ell }_w$ 的前缀码与码字上的分布 $p$，Kraft 不等式给出 $K:={\sum }_w{2}^{-{\ell }_w}\le 1$；令 $q_w:=2^{-{\ell }_w}/K$，由 KL 散度非负（${\sum }_w{p}_w{\log }_2\frac{p_w}{q_w}\ge 0$）得

$$H(p)\le \sum _w{p}_w{\log }_2\frac{1}{q_w}=\sum _w{p}_w({\ell }_w+{\log }_{2}K)\le \mathbb{E}[\ell ].$$

第二步：记 $A$ 为（随机的）答案序列、$R$ 为随机串。零误差意味着对每个固定的 $r$，$t$ 是答案序列的确定性函数 $t=f_r(A)$；由”函数不增熵”（$H(f(X))\le H(X)$，因为函数把不同取值合并、熵只会变小），$H(t|R=r)\le H(A|R=r)$。对 $r$ 取平均得 $H(t|R)\le H(A|R)$。

第三步：$t$ 与 $R$ 独立，所以 $H(t|R)=H(t)={\log }_2(N+1)$，而

$$H(A|R)=\sum _r{p}_{r}H(A|R=r)\le \sum _r{p}_r\mathbb{E}[T|R=r]=\mathbb{E}[T],$$

其中不等号对每个固定的 $r$ 用第一步。串起来：$\mathbb{E}[T]\ge {\log }_2(N+1)$。Q.E.D.

经典瓶颈的根源至此清楚了：一次比较至多传递一比特（给定 $t$ 与查询位置，答案唯一确定），而答案携带 ${\log }_2(N+1)$ 比特。二分搜索在两种口径下都达到（或几乎达到）下界——经典世界没有余地。量子能否突破”每次一比特”？能，但只能按常数因子突破（第 7.2 节会看到 $4$ 次查询区分 $605\approx 2^{9.24}$ 种可能，平均每次约 $2.31$ 比特），且无法突破对数量级（第 8 节）。

3. 历史脉络：为什么这个问题值得十年接力

有序搜索本身就是最重要的基本操作之一（索引查找、字典插入、数据库 merge），但它在量子算法史上的地位更多来自方法论：

• 手工时代（1999）。Farhi–Goldstone–Gutmann–Sipser 系统地研究了插入问题的量子版本，利用问题的自相似性手工构造精确算法并递归拼接，得到约 $0.53{\log }_{2}N$ 的查询数。这是最早一批”比较型问题上量子只赢常数”的精确刻画，也首次把”最优常数”本身当成研究对象。
• 下界时代（2001）。Høyer–Neerbek–Shi 用对抗方法（adversary method）证明 $0.221{\log }_{2}N$ 量级的下界，确认量级不可改善；其后 Childs–Lee 把”如何选对抗权重”本身写成最优化问题（同样可 SDP 化），复核并推广了该构造。
• 机器时代（2006）。Childs–Landahl–Parrilo 意识到：小规模精确算法的存在性可以写成 SDP，于是”设计算法”从灵感活变成了计算活——数值搜索给出 $(q,M)=(4,605)$ 的模块，拼接后上界降到 $0.433{\log }_{2}N$。
• 口径时代（2007）。Ben-Or–Hassidim 换了记账口径：允许随机化并按期望计数，用 adaptive learning 把期望查询数压到 $\frac{1}{3}{\log }_{2}N$ 以下，说明”常数”一词必须连同口径一起声明。

本词条按”上界侧的机器方法”为主线（第 5–7 节），下界侧（第 8 节）作为镜像。两侧的工具都是半定规划，这一点在第 8 节末尾再回收。

4. 直觉：一刀、链与干涉

在进入形式化推导之前，我们用平实语言讲清楚三件事：量子查询在这里到底做了什么；为什么没有 Grover 式的统一旋转角；量子的余地究竟在哪里。

4.1 一次查询只”切一刀”

经典地，在位置 $i$ 比较一次，等于把候选集合 $\{0,\dots ,N\}$ 切成两半：$\{t\le i\}$ 与 $\{t>i\}$（第 1.2 节）。量子地，算法可以让查询寄存器处于叠加 ${\sum }_i{\alpha }_i|i⟩$，oracle 一次性对一段后缀施加相位翻转——看起来信息量大得多。但衡量”两个候选 $s,t$ 被这次查询区分了多少”时，位置 $i$ 的贡献只是相对相位 $(-1{)}^{z_i^{(s)}\oplus z_i^{(t)}}$，而由第 1.3 节，它仅在 $i$ 落在 $s,t$ 之间（$\min (s,t)\le i<\max (s,t)$）时非平凡。换句话说：

无论振幅多么”量子”，一次查询在”区分输入对”的意义上仍然只切一刀；相邻阈值之间只有一个位置非平凡，所以相邻对最难分开。

第 5.5 节的例 2 会把这句话变成一个精确的矩阵等式：一次量子查询对 Gram 矩阵的影响恰好等于”以某个概率分布在某个位置做一次经典比较”的影响。

4.2 与 Grover 的对比：为什么没有统一的旋转角

回忆 Grover 加速的机制：全部输入信息凝聚为一个内积 $⟨x_0|s⟩=\frac{1}{\sqrt{N}}$，演化被限制在二维不变子空间，$N$ 个不同的 oracle 在这个平面上步调一致（同一个旋转角 $2\theta$），于是 $\frac{\pi }{4}\sqrt{N}$ 次迭代把振幅相干地转满。有序搜索里不存在这种一致性：$N+1$ 个 oracle 构成嵌套链（例 1），相邻者只差一个位置的相位；在任何低维子空间上它们的相对相位模式都各不相同，没有”每查询拉开同样角度”的公共平面可言。与此同时，算法必须把答案写进 $N+1$ 个两两正交的末态——要把约 ${\log }_2(N+1)$ 比特导出到测量结果里。两个因素合起来提示：加速只能是常数因子。这一节是直觉而非证明；对数下界的证明在第 8 节。

4.3 量子的余地：多刀之间的干涉

一次查询 = 一刀，但轮与轮之间的酉变换可以让不同的切口发生干涉。量子查询态 ${\sum }_i{\alpha }_i|i⟩$ 让 oracle 同时翻转一段后缀的相位；随后的酉变换把不同候选阈值送往不同方向，使下一刀切在”更有信息量”的叠加上——不同候选阈值的相位边界于是产生不同的干涉模式。第 5 节的 Gram 矩阵正是把这件事变成全局优化：每一步应该把哪些候选状态拉开多少，同时不违反”一次查询只能施加一个阶跃相位”的约束。第 6–7 节的数值解告诉我们：精心设计的干涉能让每次查询平均换取约 $2.31$ 比特（$4$ 次查询区分 $605\approx 2^{9.24}$ 种可能），远超经典的 $1$ 比特——优势是真的，但每查询的信息量仍是常数，对数量级纹丝不动。

5. 把整个量子算法装进 Gram 矩阵

本节是上界侧的核心：证明”存在 $Q$ 次查询的精确算法”等价于”存在一组半正定矩阵满足若干线性等式”。思路是只跟踪 $N+1$ 个输入对应的算法态之间的两两内积——因为输入无关的酉不改变内积，唯一能改变内积的是查询，而查询的作用可以逐位置显式写出。

5.1 状态与 Gram 矩阵

沿用第 1.4 节的记号。oracle 写成 $O_t={\sum }_i(-1{)}^{z_i^{(t)}}|i⟩⟨i|\otimes I$（若查询寄存器有 $\{0,\dots ,N-1\}$ 之外的基矢，规定 $O_t$ 在其上为恒等；这些位置对应的相位差恒为 $+1$，对下文所有求和只是多加一项”无操作”，不影响推导）。对每个阈值 $t$ 和 $0\le q\le Q$，令 $|{\psi }_t^{(q)}⟩$ 是第 $q$ 次查询前的算法状态。把两两内积组成 Gram 矩阵

$$G_{st}^{(q)}=⟨{\psi }_s^{(q)}|{\psi }_t^{(q)}⟩,s,t\in \{0,\dots ,N\}.$$

$G^{(q)}$ 是 $(N+1)\times (N+1)$ 的半正定矩阵（任何矢量族的 Gram 矩阵半正定：对复向量 $c$，$c^{†}Gc=\Vert {\sum }_t{c}_t|{\psi }_t⟩{\Vert }^2\ge 0$）。由于初态与输入无关，

$$G^{(0)}=J(J\text{ 为全 }1\text{ 矩阵}).$$

引理 3（输入无关酉保持 Gram 矩阵）。对任何酉 $U$，$⟨{\psi }_s|U^{†}U|{\psi }_t⟩=⟨{\psi }_s|{\psi }_t⟩$，即输入无关酉前后的 Gram 矩阵相同。

证明。$U^{†}U=I$，直接代入。Q.E.D.

意义：算法的自由部分（酉）对 Gram 矩阵完全透明；只需追踪查询如何改变 $G$。于是”算法存在性”这个问题里，酉被彻底消元，只剩每一步查询前后的 $N+1$ 个态的内积结构。

5.2 按查询位置分解

把每个态按查询寄存器的基分解（工作寄存器部分记为 $|\phi ⟩$）：

$$|{\psi }_t^{(q)}⟩=\sum _i|i⟩\otimes |{\phi }_{t,i}^{(q)}⟩,|{\phi }_{t,i}^{(q)}⟩:=(⟨i|\otimes I)|{\psi }_t^{(q)}⟩.$$

对每个位置 $i$，定义块矩阵

$$(G_i^{(q)}{)}_{st}:=⟨{\phi }_{s,i}^{(q)}|{\phi }_{t,i}^{(q)}⟩.$$

引理 4。每个 $G_i^{(q)}⪰0$，且 ${\sum }_i{G}_i^{(q)}=G^{(q)}$。

证明。半正定：对任意复向量 $c$，

$$c^{†}{G}_i^{(q)}c=\sum _{s,t}{\bar{c}}_s{c}_t⟨{\phi }_{s,i}^{(q)}|{\phi }_{t,i}^{(q)}⟩=⟨\sum _t{c}_t|{\phi }_{t,i}^{(q)}⟩,\sum _t{c}_t|{\phi }_{t,i}^{(q)}⟩⟩\ge 0.$$

求和：${\sum }_i(G_i^{(q)}{)}_{st}={\sum }_i⟨{\phi }_{s,i}^{(q)}|{\phi }_{t,i}^{(q)}⟩=⟨{\psi }_s^{(q)}|{\psi }_t^{(q)}⟩$，最后一步是因为查询寄存器的基矢两两正交，交叉项 $⟨i|j⟩=0(i\ne j)$ 全部清零。Q.E.D.

5.3 查询如何更新 Gram 矩阵

定义相位差矩阵（以阈值对为索引）

$$(D_i{)}_{st}=(-1{)}^{z_i^{(s)}\oplus z_i^{(t)}}.$$

由第 1.3 节，$(D_i{)}_{st}=-1$ 当且仅当 $i$ 落在 $s,t$ 之间；$D_i$ 是元素为 $\pm 1$ 的对称矩阵、对角线全 $+1$。注意 $D_i$ 只依赖问题（阈值阶跃结构），不依赖算法。

定理 5（查询更新规则）。一次查询把 $G^{(q)}$ 变为

$${\tilde{G}}^{(q)}=\sum _i{G}_i^{(q)}\circ D_i,$$

其中 $\circ$ 是 Hadamard（逐元素）积；随后的输入无关酉不改变它，故 $G^{(q+1)}={\tilde{G}}^{(q)}$。

证明。逐个内积计算。查询后、酉之前，两个态是 $O_s|{\psi }_s^{(q)}⟩$ 与 $O_t|{\psi }_t^{(q)}⟩$：

$$\begin{array}{rl}⟨{\psi }_s^{(q)}|O_s^{†}{O}_t|{\psi }_t^{(q)}⟩& =\sum _{i,j}(-1{)}^{z_i^{(s)}}(-1{)}^{z_j^{(t)}}⟨i|j⟩⟨{\phi }_{s,i}^{(q)}|{\phi }_{t,j}^{(q)}⟩\\ & =\sum _i(-1{)}^{z_i^{(s)}+z_i^{(t)}}(G_i^{(q)}{)}_{st},\end{array}$$

第二步用了 $⟨i|j⟩={\delta }_{ij}$。由于 $z\in \{0,1\}$，$z_i^{(s)}+z_i^{(t)}$ 与 $z_i^{(s)}\oplus z_i^{(t)}$ 同奇偶，故 $(-1{)}^{z_i^{(s)}+z_i^{(t)}}=(D_i{)}_{st}$。（第一个等号里 $O_t$ 自伴：它是对角相位矩阵。）再由引理 3，其后的酉保持这些内积。Q.E.D.

5.4 精确求解的刻画：一个 SDP 可行性问题

定理 6。存在 $Q$ 次查询的精确算法 $⟺$ 存在半正定矩阵族 $\{G_i^{(q)}{\}}_{i,q}$（$i=0,\dots ,N-1$，$q=0,\dots ,Q-1$）满足以下线性约束（记 $G^{(q)}:={\sum }_i{G}_i^{(q)}$）：

1. $G^{(0)}=J$（初始内积全为 $1$）；
2. 对 $q=0,\dots ,Q-1$：${\sum }_i{G}_i^{(q)}\circ D_i=G^{(q+1)}$；
3. ${\sum }_i{G}_i^{(Q-1)}\circ D_i=I$（末态两两正交）。

变量是半正定矩阵、约束是线性等式——这正是半定规划的可行性问题。

证明。

（$\Rightarrow$ 必要性）给定算法，取真实的中间态与真实分解：$G^{(q)}$ 是态的 Gram 矩阵，$G_i^{(q)}$ 是逐位置块。引理 4 给出半正定性与 ${\sum }_i{G}_i^{(q)}=G^{(q)}$；$G^{(0)}=J$ 因为初态输入无关；定理 5 给出约束 2。约束 3 即 $G^{(Q)}=I$：精确成功要求不同输入的末态可被完美区分，而两个态可完美区分当且仅当正交（正交时投影测量即可；不正交时任何测量都有非零错误率——这是第 5.6 节引理 8 取 $\epsilon \to 0$ 的情形）。

（$\text{Left}$ 充分性，重构算法）分四步。

• 第一步（分解出态矢量）。对每个 $G_i^{(q)}$ 做谱分解 $G_i^{(q)}=X_i^{†}{X}_i$（$X_i$ 为 $r_i\times (N+1)$ 矩阵，$r_i=\mathrm{rank}{G}_i^{(q)}$）。取 $|{\phi }_{t,i}^{(q)}⟩:=$ $X_i$ 的第 $t$ 列，则 $⟨{\phi }_{s,i}^{(q)}|{\phi }_{t,i}^{(q)}⟩=(X_i^{†}{X}_i{)}_{st}=(G_i^{(q)}{)}_{st}$。
• 第二步（拼出每层的态族）。令 $|{\psi }_t^{(q)}⟩:={\sum }_i|i⟩\otimes |{\phi }_{t,i}^{(q)}⟩$。由引理 4 的计算，$⟨{\psi }_s^{(q)}|{\psi }_t^{(q)}⟩={\sum }_i(G_i^{(q)}{)}_{st}=G_{st}^{(q)}$。再由定理 5 的计算（反向使用），查询后态族 $\{O_t|{\psi }_t^{(q)}⟩{\}}_t$ 的 Gram 矩阵是 ${\sum }_i{G}_i^{(q)}\circ D_i=G^{(q+1)}$——与下一层态族 $\{|{\psi }_t^{(q+1)}⟩{\}}_t$ 的 Gram 矩阵逐项相等。
• 第三步（补上酉）。需要的是把 $\{O_t|{\psi }_t^{(q)}⟩{\}}_t$ 送到 $\{|{\psi }_t^{(q+1)}⟩{\}}_t$ 的输入无关酉。这正是下面的酉扩张引理。
• 第四步（起止两端）。起点：$G^{(0)}=J$ 说明 $⟨{\psi }_s^{(0)}|{\psi }_t^{(0)}⟩=1$ 对所有 $s,t$ 成立，即所有 $|{\psi }_t^{(0)}⟩$ 都是同一个单位矢量（至多差相位 $e^{i{\theta }_t}$；相位不同的单位矢量内积的模长为 $1$，而这里内积精确等于 $1$，故相位也相同）。取它为 $|\mathrm{init}⟩$。终点：$G^{(Q)}=I$ 说明末态两两正交归一，在包含这组态的基上做投影测量即可读出 $t$。Q.E.D.

引理 7（酉扩张）。设 $\{|a_t⟩{\}}_{t=0}^N$ 与 $\{|b_t⟩{\}}_{t=0}^N$ 是（可视为同一）希尔伯特空间中的两组矢量，且对所有 $s,t$ 有 $⟨a_s|a_t⟩=⟨b_s|b_t⟩$。则存在酉算子 $U$ 使 $U|a_t⟩=|b_t⟩$ 对所有 $t$ 成立。

证明。定义 $V({\sum }_t{c}_t|a_t⟩):={\sum }_t{c}_t|b_t⟩$。良定义：若 ${\sum }_t{c}_t|a_t⟩=0$，则

$$\Vert \sum _t{c}_t|b_t⟩{\Vert }^2=\sum _{s,t}{\bar{c}}_s{c}_t⟨b_s|b_t⟩=\sum _{s,t}{\bar{c}}_s{c}_t⟨a_s|a_t⟩=\Vert \sum _t{c}_t|a_t⟩{\Vert }^2=0,$$

故 ${\sum }_t{c}_t|b_t⟩=0$，$V$ 在表示不唯一时也给同一结果。等距：同一计算给出 $⟨Vx|Vy⟩=⟨x|y⟩$。于是 $V$ 是 $\mathrm{span}\{a_t\}\to \mathrm{span}\{b_t\}$ 的等距，两个子空间维数相同；把 $V$ 任意扩张为整个空间的酉（必要时在直和上补维数相同的零空间）。Q.E.D.

两点提醒。其一，重构所需的工作寄存器维数约为 ${\sum }_i\mathrm{rank}{G}_i^{(q)}$，随 $N$ 增长——在只计查询数的模型里无妨，但再次强调查询优势不等于时间优势。其二，SDP 的变量数是 $(N+1{)}^2\times N\times Q$ 量级，对大 $N$ 不可解；第 6 节用对称性把它压下来。

5.5 三个小例子：单查询的极限

例 2（一次查询 = 切矩阵的凸组合）。第一次查询前所有态相同：$|\mathrm{init}⟩={\sum }_i|i⟩\otimes |w_i⟩$，故 $(G_i^{(0)}{)}_{st}=⟨w_i|w_i⟩=:p_i$ 与 $s,t$ 无关，即 $G_i^{(0)}=p_{i}J$，其中 $p_i\ge 0$、${\sum }_i{p}_i=\Vert \mathrm{init}{\Vert }^2=1$。代入定理 5（并注意 $J\circ D_i=D_i$，因为 $D_i$ 的元素全是 $\pm 1$）：

$$G^{(1)}=\sum _i{p}_i{D}_i.$$

解读：一次量子查询——无论振幅如何叠加、是否与工作寄存器纠缠——对两两内积的影响，与”以概率 $p_i$ 在位置 $i$ 做一次经典比较”完全一样（经典随机比较的区分度矩阵恰是同一凸组合）。量子的余地只能来自多轮之间：酉 $U^{(q)}$ 把第 $q$ 刀的相位结构搬运、重组，使第 $q+1$ 刀落在更聪明的叠加上。这就是第 4.1 节”一刀”论断的精确形式。

例 3（$N=2$：一次查询不够）。阈值 $\{0,1,2\}$，位置 $\{0,1\}$，三个位串 $z^{(0)}=(1,1)$、$z^{(1)}=(0,1)$、$z^{(2)}=(0,0)$。由例 2，$G_{st}^{(1)}=p_0(D_0{)}_{st}+p_1(D_1{)}_{st}$。逐对计算（用”$D_i$ 在位置 $i$ 两侧的输入对上取 $-1$”）：

• 对 $(0,2)$：两个位置都分居两侧 $\Rightarrow (D_0{)}_{02}=(D_1{)}_{02}=-1\Rightarrow G_{02}^{(1)}=-(p_0+p_1)=-1$；
• 对 $(0,1)$：只有位置 $0$ 分居两侧 $\Rightarrow G_{01}^{(1)}=p_1-p_0$；
• 对 $(1,2)$：只有位置 $1$ 分居两侧 $\Rightarrow G_{12}^{(1)}=p_0-p_1$。

精确求解需要 $G^{(1)}=I$，特别需要 $G_{02}^{(1)}=0$；但它是 $-1$，与 $p$ 的选取无关。所以任何单查询算法都必然失败。另一方面两次比较（先比 $y_0$）足以精确求解，故 $N=2$ 时精确量子查询数 $=2=$ 经典值——量子优势要到更大的 $N$ 才出现。

例 4（均匀叠加给出”三角形核”）。取 $|\mathrm{init}⟩=\frac{1}{\sqrt{N}}{\sum }_i|i⟩\otimes |w⟩$（$|w⟩$ 归一），则 $p_i=\frac{1}{N}$。对 $s<t$，$D_i$ 取 $-1$ 的位置恰是 $i\in [s,t)$，共 $t-s$ 个：

$$G_{st}^{(1)}=\frac{(N-(t-s))-(t-s)}{N}=1-\frac{2(t-s)}{N}.$$

一次查询后的”距离核”是线性的：相邻对（$t-s=1$）几乎不被分开（$1-\frac{2}{N}$），最远对（$t-s=N$）被推到 $-1$——模长仍为 $1$，只是差了相位，照样不正交。作为自洽性检查，这样构造出的 $G^{(1)}$ 必然半正定（它是真实态族的 Gram 矩阵）；例如 $N=2$ 时矩阵 $\left(\begin{array}{ccc}1& 0& -1\\ 0& 1& 0\\ -1& 0& 1\end{array}\right)$ 的特征值为 $\{0,1,2\}$，确实半正定。

5.6 有界误差：measurement feasibility

精确版要求末态两两正交（$G^{(Q)}=I$）。允许误差至多 $\epsilon$ 时，末态不必正交，只需存在一个测量把它们区分开：把 POVM $\{E_t\}$（$E_t⪰0$、${\sum }_t{E}_t=I$）一并当作 SDP 变量，把成功条件 $⟨{\psi }_t|E_t|{\psi }_t⟩\ge 1-\epsilon$ 写成半定约束。这一组约束在文献中称为 measurement feasibility 表述。为了理解它”放宽了多少”，给出一个便于手算的必要条件：

引理 8。若存在误差 $\le \epsilon$ 的算法，则对一切 $s\ne t$ 有 $|G_{st}^{(Q)}{|}^2\le 4\epsilon (1-\epsilon )$。

证明。只看二分问题”输入是 $s$ 还是 $t$“（先验各半）。两纯态最小错误判别的 Helstrom 公式（量子信息标准结果）说：任何测量区分 $|{\psi }_s⟩,|{\psi }_t⟩$ 的平均成功率至多为 $\frac{1}{2}(1+\sqrt{1-|⟨{\psi }_s|{\psi }_t⟩{|}^2})$。另一方面，用算法的测量并把效果并成二值 $\{E_s,I-E_s\}$：由 $E_s⪯I-E_t$ 与成功条件，

$$⟨{\psi }_s|E_s|{\psi }_s⟩\ge 1-\epsilon ,⟨{\psi }_t|E_s|{\psi }_t⟩\le 1-⟨{\psi }_t|E_t|{\psi }_t⟩\le \epsilon ,$$

平均成功率至少 $\frac{1}{2}[(1-\epsilon )+(1-\epsilon )]=1-\epsilon$。两相比较：$1-\epsilon \le \frac{1}{2}(1+\sqrt{1-|G_{st}{|}^2})$，即 $\sqrt{1-|G_{st}{|}^2}\ge 1-2\epsilon$，两边平方整理得 $|G_{st}{|}^2\le 1-(1-2\epsilon {)}^2=4\epsilon (1-\epsilon )$。Q.E.D.

于是有界误差版本就是把"$G^{(Q)}=I$"放宽为”非对角内积足够小”（配合测量变量的精确形式）；取 $\epsilon \to 0$ 也顺带补上了定理 6 中”必须正交”的论证。

6. 对称性：把 SDP 压到可解的规模

6.1 困难与对策

第 5 节的 SDP 有 $N+1$ 个输入标签，变量数是 $(N+1{)}^2\times N\times Q$ 量级——$N$ 稍大就无法求解。对策是利用问题的对称性。直线上排列的阈值没有严格的平移对称（位置 $0$ 与位置 $N-1$ 是边界，平移会撞墙），因此先把有序问题嵌入一个带周期/反射对称的扩展问题：把阈值放到圆周上（输入带循环指标），规模只放大常数倍，且解出扩展问题即可解出原问题；嵌入的具体记账见 Childs–Landahl–Parrilo 原文。本词条只需要对称性的两条数学后果，它们的证明（第 6.2、6.3 节）是自含的。

圆周版 oracle 是”固定弧长的阶跃”：输入为弧的起点 $t\in {\mathbb{Z}}_L$（$L$ 为圆周长），$z_i^{(t)}=1[(i-t)\mathrm{mod}L<m]$（弧长 $m$ 固定）。它满足平移等变性

$$z_i^{(t+1\mathrm{mod}L)}=z_{i-1\mathrm{mod}L}^{(t)},$$

验证：$(i-(t+1))\mathrm{mod}L=((i-1)-t)\mathrm{mod}L$，两边同时落在 $[0,m)$ 与否是一回事。这条等变性保证：把所有阈值平移一格等价于把所有查询位置平移一格，SDP 的约束集合在”平移”作用下不变——这正是下面凸平均引理的适用前提。

6.2 凸平均引理（对称化为什么合法）

引理 9（群平均）。设可行集 $\mathcal{F}$ 由线性等式约束与半正定约束定义，有限群 $\Sigma$ 线性作用在变量空间上且保持 $\mathcal{F}$ 不变（$x\in \mathcal{F},\sigma \in \Sigma \Rightarrow \sigma \cdot x\in \mathcal{F}$）。则对任何 $x\in \mathcal{F}$，平均 $\bar{x}:=\frac{1}{|\Sigma |}{\sum }_{\sigma \in \Sigma }\sigma \cdot x$ 仍属于 $\mathcal{F}$，且是 $\Sigma$ 的不动点。

证明。半正定锥是凸锥，故 $\bar{x}⪰0$（半正定约束保持）。对线性等式 $g(x)=0$：由 $g$ 线性与每个 $\sigma \cdot x$ 可行，$g(\bar{x})=\frac{1}{|\Sigma |}{\sum }_{\sigma }g(\sigma \cdot x)=0$。不动点：对 $\tau \in \Sigma$，$\tau \cdot \bar{x}=\frac{1}{|\Sigma |}{\sum }_{\sigma }(\tau \sigma )\cdot x=\frac{1}{|\Sigma |}{\sum }_{\rho }\rho \cdot x=\bar{x}$（$\sigma \mapsto \tau \sigma$ 是群的重排）。Q.E.D.

这一步正是 Gram/SDP 表述的价值所在：线路的集合不是凸的，但线路的 Gram 描述是凸的。“把算法对称化”在 SDP 世界里只是一次凸组合；若直接对线路做平均（把酉平均起来），一般既得不到酉也保不住精确性。

推论。对带平移对称的扩展问题，可行解可以取成平移不变的：所有 $G^{(q)}$ 都是循环矩阵（$G_{st}$ 只依赖 $(s-t)\mathrm{mod}L$）。再加反射对称（阈值次序取逆），解还可取成实的、只依赖 $\pm (s-t)$。就原问题而言，这正是”Gram 矩阵近似只依赖 $s-t$“——循环化在扩展问题中是精确的，回到直线问题时只在端点附近有边界效应。

6.3 循环矩阵与 Laurent 多项式

引理 10。设 $C$ 是 $L\times L$ 循环矩阵：$C_{st}=c_{(s-t)\mathrm{mod}L}$。则 Fourier 向量 $f_{\omega }$（分量 $(f_{\omega }{)}_s={\omega }^s/\sqrt{L}$，${\omega }^L=1$）是 $C$ 的特征向量，特征值为

$$\lambda (\omega )=\sum _{d=0}^{L-1}{c}_d{\omega }^{-d}.$$

特别地，Hermitian 循环矩阵（$c_{-d\mathrm{mod}L}={\bar{c}}_d$）半正定 $⟺$ 对所有 $L$ 次单位根 $\omega$ 有 $\lambda (\omega )\ge 0$。

证明。直接计算（代换 $d=(s-t)\mathrm{mod}L$，即 $t=(s-d)\mathrm{mod}L$，求和遍历 ${\mathbb{Z}}_L$）：

$$(C{f}_{\omega }{)}_s=\sum _t{c}_{(s-t)\mathrm{mod}L}{\omega }^t=\sum _d{c}_d{\omega }^{(s-d)\mathrm{mod}L}={\omega }^s\sum _d{c}_d{\omega }^{-d},$$

末步用了 ${\omega }^{(s-d)\mathrm{mod}L}={\omega }^{s-d}$（因 ${\omega }^L=1$）。故 $C{f}_{\omega }=\lambda (\omega )f_{\omega }$。循环矩阵可被 Fourier 基整体对角化，其半正定性等价于全部特征值非负，而对角元 $c_0$ 为实、其余系数共轭对称时特征值 $\lambda (\omega )={\sum }_d{c}_d{\omega }^{-d}$ 是实数。Q.E.D.

意义：$\lambda (\omega )$ 是 Laurent 多项式 $p(x)={\sum }_d{c}_d{x}^d$ 在单位圆点 $x={\omega }^{-1}$ 处的取值。于是”PSD”这一矩阵约束化成”Laurent 多项式（的系数）非负”型约束：每个 Gram 矩阵的变量从 $(N+1{)}^2$ 个内积压缩到约 $L$ 个 Fourier 系数，SDP 的规模从”随 $N$ 平方”降到”随 $N$ 线性”，小块问题彻底可解。

6.4 数值搜索小块模块

现在可以系统地问：给定候选数（块长）$M$ 与查询数 $q$，是否存在一个精确区分 $M$ 个有序阈值的 $q$ 查询算法？流程是：

1. 写出第 5 节的 SDP（输入标签只有 $M$ 个）；
2. 用第 6.2–6.3 节的对称化把变量压成 Fourier 系数；
3. 用数值 SDP 求解器找可行点；
4. 按定理 6 的重构（谱分解 + 引理 7）从 Gram 分解显式恢复各步酉矩阵。

警告（不可省略的一步）。SDP 求解器返回浮点数，而”浮点可行”不等于”精确可行”：约束要求等式精确成立、矩阵精确半正定。要宣称一个精确算法，必须把数值解高精度化——把条目舍入为小分母有理数（或代数数）——然后代回约束做精确验证，或者给出严格的对偶证书。不能只把浮点 SDP 状态当作精确算法的证明。原文献对其 $(q,M)=(4,605)$ 模块正是这样处理的。

7. 递归拼接：从模块到任意 $N$

7.1 构造

若一个 $q$ 查询子程序能确定阈值落在 $M$ 个有序子区间中的哪一个，就把长度 $N$ 的列表按比例分成 $M$ 块：

1. 用该子程序找出正确块；
2. 在块内递归使用同一程序；
3. 直到候选只剩一个位置。

三点实现说明。（i）递归后问题形状不变：找到正确块后，任务变成”在更小的有序候选集合里定位阈值”，而比较仍然通过位置进行、答案仍由第 1.2 节的阈值逻辑给出——块内位置与全局阈值的关系和原始问题一模一样。（ii）子程序查询位置的对应：子程序是针对”$M$ 个有序候选”设计的，它查询的”位置”应对应当前候选集合的分界点；只要对应保持单调（分界点次序不乱），oracle 给出的阶跃相位模式就与子程序所设一致——这正是第 1.2 节"$x>y_i⟺i<t$"的推理在块结构上的重演。（iii）分块不必整除：把大小为 $n$ 的候选集合分成 $M$ 块、每块至多 $\lceil n/M\rceil$ 个（末块可小），块数仍固定为 $M$，子程序照常适用；这样每层候选数精确地缩到 $\lceil n/M\rceil$ 倍，不产生随深度累积的额外查询。

7.2 查询数：逐项分析与参数平衡

定理 11。上述递归给出

$$Q(N)\le q{\log }_{M}N+O(1)=\frac{q}{{\log }_{2}M}{\log }_{2}N+O(1).$$

证明。记 $n_d$ 为 $d$ 层之后的候选数：$n_0=N+1$，$n_{d+1}\le \lceil n_d/M\rceil \le n_d/M+1$。断言：只要 $M^d\le N$ 就有 $n_d\le 2N/M^d$。归纳：$n_{d+1}\le \frac{2N/M^d}{M}+1=\frac{2N}{M^{d+1}}+1\le \frac{2N}{M^{d+1}}$，末步用了归纳前提 $M^{d+1}\le N$ 故 $1\le N/M^{d+1}$。取底部门槛 $M_0$（常数，例如 $M_0=2$：一两次查询收尾），并令 $d^{\ast }$ 为满足 $2N/M^d\le M_0$ 的最小整数——由断言，此时 $n_{d^{\ast }}\le M_0$，递归在 $d^{\ast }$ 层内结束，而

$$d^{\ast }\le {\log }_M\frac{2N}{M_0}+1={\log }_{M}N+O(1).$$

每层恰好 $q$ 次查询（子程序内部固定），总计 $q({\log }_{M}N+O(1))+O(1)=q{\log }_{M}N+O(1)$（$q$ 是常数）。最后用换底公式把 ${\log }_{M}N$ 化为 $\frac{{\log }_{2}N}{{\log }_{2}M}$：由 $(2^{{\log }_{2}M}{)}^{{\log }_{M}N}=2^{{\log }_{2}N}$ 两边取 ${\log }_2$ 即得。Q.E.D.

复杂度表达式逐项拆开：

• $q$：一个模块内部的查询数，由第 6 节的 SDP 数值搜索决定，是构造的输入而非推导的产物；
• $1/{\log }_{2}M$：每查询的”候选缩减率”——$M$ 越大（单个模块能区分的有序候选越多），每层的 $q$ 次查询摊得越薄；
• ${\log }_{2}N$：问题的信息量尺度（$N+1$ 种答案）；
• $O(1)$：底部门槛收尾与顶层的常数项——注意深度里的"$+O(1)$"乘上常数 $q$ 后仍是 $O(1)$。

参数平衡：若手里有一族可行模块 $(q,M)$，应选使 $\frac{q}{{\log }_{2}M}$ 最小者；比较两个模块即比较 $q{\log }_2{M}^{\prime }$ 与 $q^{\prime }{\log }_{2}M$。作为算术练习（并不断言其存在）：一个 $q=3$、$M=128$ 的模块会给出常数 $\frac{3}{7}\approx 0.429<0.433$——这说明记录在案的 $(4,605)$ 未必是终点，继续搜更好的模块仍有明确收益。

数值：Childs–Landahl–Parrilo 的模块。SDP 找到 $q=4$、$M=605$ 的精确模块。计算常数：

$${\log }_{2}605=\frac{\ln 605}{\ln 2},605=512\times 1.18164\dots ,$$ $${\log }_{2}605=9+{\log }_{2}1.18164\dots =9+\frac{\ln 1.18164\dots }{\ln 2}\approx 9+\frac{0.16698}{0.69315}\approx 9.241,$$ $$Q(N)\le 4{\log }_{605}N+O(1)=\frac{4}{9.241}{\log }_{2}N+O(1)\approx 0.433{\log }_{2}N+O(1).$$

它比早期约 $0.53{\log }_{2}N$ 的 invariant algorithm 更好（查询数约省 $18\%$，以 $0.53$ 计），但仍只改变常数。换一个角度读这个数字：$4$ 次查询区分 $605\approx 2^{9.24}$ 种可能，平均每次查询传递 $\frac{9.24}{4}\approx 2.31$ 比特——量子把”每次一比特”的经典铁律提高了约 $2.3$ 倍，却无法改变 $\log N$ 的量级。

8. 对抗下界：为什么仍是 $\Omega (\log N)$

8.1 对抗方法的逻辑

令 adversary 矩阵 $\Gamma$ 以阈值 $s,t$ 为索引：实对称、对角线为零（可以非负，也可以变号），它的每个元素 ${\Gamma }_{st}$ 是我们指派给输入对 $(s,t)$ 的”未区分程度”。一次查询位置 $i$ 只能区分那些阈值分别位于 $i$ 两侧的输入对，即用

$$({\Delta }_i{)}_{st}=1[z_i^{(s)}\ne z_i^{(t)}]$$

过滤 $\Gamma$。对抗比值

$$\frac{\Vert \Gamma \Vert }{{\max }_i\Vert \Gamma \circ {\Delta }_i\Vert }$$

给出查询下界。精确地说：

定理 12（谱对抗界，引用不证）。对任何实对称、零对角的 $\Gamma$，任何误差 $\le \epsilon$ 的量子算法的查询数至少为

$$(1-2\epsilon )\frac{\Vert \Gamma \Vert }{{\max }_i\Vert \Gamma \circ {\Delta }_i\Vert };$$

特别地，精确算法至少需要 $\frac{\Vert \Gamma \Vert }{{\max }_i\Vert \Gamma \circ {\Delta }_i\Vert }$ 次查询。证明见对抗方法的标准文献；本词条的 Boolean 公式求值一讲会在 SDP 对偶视角下统一处理这类界。

三个因子各自的含义：

• 分子 $\Vert \Gamma \Vert$（$\Gamma$ 的谱范数）：把所有输入对的”关联结构”拆完所需的总工作量；
• $\Gamma \circ {\Delta }_i$：只有分居 $i$ 两侧的输入对保留权重，其余被 Hadamard 积清零——这正是”一次查询只切一刀”（第 4.1 节）的矩阵化；
• 分母 ${\max }_i\Vert \Gamma \circ {\Delta }_i\Vert$：单次查询至多推进的量。

于是”选一个好的 $\Gamma$“就是：让总工作量尽量大（分子大），同时任何一刀切掉的部分都尽量小（分母小）。

8.2 手算例子：$N=3$ 的路径权重

取最自然的一组权重——只连接相邻阈值：${\Gamma }_{st}=1$ 当 $|s-t|=1$，否则为 $0$（即 4 个阈值的路径图 $P_4$ 的邻接矩阵；实对称、零对角，合法）。

分子。路径图 $P_n$ 的邻接谱是标准结果：特征值为 $2\cos \frac{k\pi }{n+1}$（$k=1,\dots ,n$）。对 $n=4$：$\pm 1.618\dots$、$\pm 0.618\dots$，故 $\Vert \Gamma \Vert =2\cos \frac{\pi }{5}\approx 1.618$。快速核验：迹为 $0$（对角为零）；而 $\mathrm{tr}{A}^2=2\times \text{边数}=6=2(1.618^2+0.618^2)$，与谱一致。

分母。逐个算 $\Gamma \circ {\Delta }_i$（用 ${\Delta }_i$ 选出分居 $i$ 两侧的对）：

• ${\Delta }_0$ 选出对 $(0,1),(0,2),(0,3)$，其中只有 $(0,1)$ 带 $\Gamma$ 权重 $\Rightarrow \Gamma \circ {\Delta }_0$ 是单边矩阵，范数 $1$；
• ${\Delta }_1$ 选出对 $(0,2),(0,3),(1,2),(1,3)$，其中只有 $(1,2)$ 带权重 $\Rightarrow$ 范数 $1$；
• ${\Delta }_2$ 选出对 $(0,3),(1,3),(2,3)$，其中只有 $(2,3)$ 带权重 $\Rightarrow$ 范数 $1$。

比值 $1.618$，故精确算法至少 $\lceil 1.618\rceil =2$ 次查询；二分搜索（先比中点 $y_1$，再比一侧）恰好用 $2$ 次，所以 $N=3$（4 个阈值）时精确查询数是 $2$，对抗界在此是紧的。顺带一提，例 2 的单查询不可能性论证对 $N=3$ 同样适用：最远输入对 $(0,3)$ 在所有位置上都分居两侧，故任何单查询后 $G_{03}^{(1)}=-1\ne 0$。

这类权重的局限：对 $N+1$ 个阈值的路径，$\Vert \Gamma \Vert \to 2$（当 $N\to \infty$），比值永远 $O(1)$——纯近邻权重证不出对数下界。要得到 $\log$ 增长，权重必须延伸到更长程，同时随距离衰减。

8.3 对数下界：Høyer–Neerbek–Shi 与 Childs–Lee

让相近阈值具有精心选择的权重、随 $|s-t|$ 衰减后，$\Gamma$ 的行为像一个离散的近奇异积分算子，其结构直觉是：

• 分子对数增长：$\Vert \Gamma \Vert$ 随 $N$ 以 $\Theta (\ln N)$ 增长——直觉上每行权重之和像调和级数一样缓慢发散，谱范数继承了这种对数累积；
• 分母有界：任一刀 $\Gamma \circ {\Delta }_i$ 只切出一个局部小块，其范数与 $N$ 无关。

二者相除得到 $c\cdot \ln N$ 形式的下界，而常数 $c$ 对权重的具体形状极其敏感。Høyer–Neerbek–Shi 通过仔细的谱计算构造出合适的权重，得到

$$Q(N)\ge \frac{\ln 2}{\pi }{\log }_{2}N-O(1)\approx 0.221{\log }_{2}N-O(1);$$

Childs–Lee 随后把”选权重”本身写成一个最优化问题（同样可 SDP 化）来处理，复核并推广了这一构造。我们把 $c=\frac{\ln 2}{\pi }$ 的谱计算留在原文；对本词条而言，重要的是结构：分子对数增长、分母有界，故任何量子算法都需要 $\Omega (\log N)$ 次查询。

8.4 缺口与三种口径

上界 $0.433$ 与下界 $0.221$ 之间仍有常数空隙，精确渐近常数未知。此外，随机化量子算法可通过 adaptive learning 把期望查询常数降到 $\frac{1}{3}$ 以下（Ben-Or–Hassidim：把”下一步比较哪里”交给一个量子自适应过程去学习，使期望树深低于均匀二分），但期望、有界错误与最坏精确三种口径不能直接比较。展开说（对应习题 4）：

1. $0.433{\log }_{2}N$ 是”精确、最坏”口径的上界，不是精确值——真实常数可以低到 $0.221$，因此”期望 $<\frac{1}{3}$“与之毫无冲突；
2. “期望”对输入分布平均，允许个别分支很深：期望小不蕴含最坏小（当然期望 $\le$ 最坏，两者并存永远合法）；
3. 口径放宽会同步削弱下界：有界误差时定理 12 的比值要乘 $1-2\epsilon$，期望口径还会进一步放宽。

所以正确的总结是分口径陈述：精确最坏情形的复杂度常数落在 $[0.221\dots ,0.433\dots ]$；有界误差与期望口径的常数各自更低，且与前者的数值不可直接比大小。

顺带回收一个方法论观察：上界侧的”算法存在性”是 SDP 可行性问题，下界侧的”选最优对抗矩阵”是 SDP 最优化问题——在更一般的框架（span program 与一般对抗界）中，这两类 SDP 被证明互为对偶，从而共同给出查询复杂度的精确刻画；这超出本词条范围，是本词条后续教程的主题。

9. 小结与习题

• 顺序搜索的量子优势只能是常数因子，复杂度仍为 $\Theta (\log N)$：精确最坏口径上界 $0.433{\log }_{2}N$（$4{\log }_{605}N$），下界 $0.221{\log }_{2}N$（$\frac{\ln 2}{\pi }{\log }_{2}N$），空隙未闭合。
• 一次量子查询对 Gram 矩阵的影响 $=$ 切矩阵的凸组合（例 2）：量子的余地只能来自多轮之间的干涉。
• 查询前状态的 Gram 矩阵把量子算法存在性化成 SDP：输入无关酉不改变内积，查询的更新是 $G^{(q+1)}={\sum }_i{G}_i^{(q)}\circ D_i$。
• SDP 可行集是凸的，故可用群平均把解对称化：Gram 矩阵化成循环矩阵、再化成 Laurent 多项式系数的非负性约束。
• 小规模精确模块（$q$ 查询、$M$ 个候选）可递归拼接成任意规模，常数为 $\frac{q}{{\log }_{2}M}$；数值解必须高精度化并精确验证后才能当作算法证明。
• 对抗比值 $\frac{\Vert \Gamma \Vert }{{\max }_i\Vert \Gamma \circ {\Delta }_i\Vert }$ 给出下界：分子是总工作量、分母是单刀上限；期望、有界错误与最坏精确三种口径不可直接比较。

习题：

1. 写出 $N=3$ 时四个阈值 oracle 的相位向量，并验证 $z^{(s)}$ 与 $z^{(t)}$ 的汉明距离恰为 $|s-t|$。
2. 证明输入无关酉操作保持 Gram 矩阵（引理 3），并解释为什么这使 SDP 里只需建模查询步、而把所有 $U^{(q)}$ 消元。
3. 从 $q=4$、$M=605$ 计算 $\frac{q}{{\log }_{2}M}$（给出中间步骤），并算出该模块平均每次查询传递多少比特；再判断：$q=3$、$M=100$ 的模块（若存在）是否优于它？
4. 解释”期望查询数少于 $\frac{1}{3}{\log }_{2}N$“为何不与”精确最坏情形可用 $0.433{\log }_{2}N$ 完成、且至少需要 $0.221{\log }_{2}N$“直接矛盾。
5. 证明酉扩张引理（引理 7），并说明它在定理 6 的重构中扮演的角色：为什么不能直接用”两组矢量内积相同”拼出算法，而必须补一个酉？
6. 证明循环矩阵的 Fourier 对角化（引理 10），并说明 Hermitian 循环矩阵的半正定性为何等价于一个 Laurent 多项式在单位圆（的 $L$ 次单位根处）非负。

参考文献

• Zoo 编号 39：Farhi、Goldstone、Gutmann 与 Sipser, Invariant Quantum Algorithms for Insertion into an Ordered List.
• Zoo 编号 103：Andrew Childs、Andrew Landahl 与 Pablo Parrilo, Improved Quantum Algorithms for the Ordered Search Problem via Semidefinite Programming.
• Zoo 编号 219、24：Høyer—Neerbek—Shi 与 Childs—Lee 的 adversary 下界。
• Zoo 编号 10：Michael Ben-Or 与 Avinatan Hassidim, Quantum Search in an Ordered List via Adaptive Learning.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/ordered-search
• 内容遵循 CC BY-NC-SA 4.0 许可协议