# 量子顺序搜索：半定规划模块与常数因子优势

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

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

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

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

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

**前置知识**：本站第 3 章的 [Grover 算法](../ch03-algo-basics/grover.md)（相位 oracle、查询模型、反射与旋转的语言）。半定规划方面，本教程自含所需的一点点内容：读者只需接受"变量是半正定矩阵、约束是线性等式"就是一个可以数值求解的问题。

:::{admonition} 本课知识点
:class: tip

1. **[插入位置与阈值 oracle](#threshold-oracle)**——能把有序搜索改写为阈值 $t\in\{0,\ldots,N\}$ 的查询问题，写出阶跃位串 $z^{(t)}$ 与相位 oracle，并验证汉明距离 $|s-t|$ 与嵌套链结构。
2. **[二分搜索与两个经典下界](#classical-lower-bounds)**——能证明决策树下界 $\lceil\log_2(N+1)\rceil$，并用前缀码的熵界说明随机化的期望比较数仍至少 $\log_2(N+1)$。
3. **[一刀、链与干涉的直觉](#one-cut-intuition)**——能解释一次量子查询为何在"区分输入对"的意义上仍只"切一刀"、有序搜索为何没有 Grover 式统一旋转角，以及量子的余地为何只能来自多轮干涉。
4. **[Gram 矩阵与查询更新规则](#gram-update-rule)**——能证明输入无关酉保持 Gram 矩阵、把算法态按查询位置分解，并推导更新规则 $G^{(q+1)}=\sum_iG_i^{(q)}\circ D_i$。
5. **[精确求解的 SDP 刻画](#sdp-characterization)**——能写出精确算法存在性的三条线性约束，并用谱分解与酉扩张引理从可行解重构出量子算法。
6. **[凸平均与循环矩阵压缩](#group-average-symmetrization)**——能证明凸平均引理（可行集的凸性使对称化合法），并通过循环矩阵的 Fourier 对角化把半正定性化为 Laurent 多项式在单位根处的非负性。
7. **[递归拼接与参数平衡](#recursion-query-count)**——能用候选数的归纳估计证明 $Q(N)\le q\log_MN+O(1)$，并计算、比较模块的渐近常数 $\frac q{\log_2M}$。
8. **[对抗下界与三种口径](#adversary-lower-bound)**——能解释对抗比值 $\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}$ 中分子与分母的含义，手算路径权重的例子，并说明 $0.221$–$0.433$ 的缺口与三种口径为何不可直接比较。

:::

## 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,\ldots,N\},\qquad 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\iff x\text{ 高于 }y_i\iff i\le t-1\iff i<t.$$

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

(threshold-oracle)=
### 1.3 阈值 oracle 与相位形式

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

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

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

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

即对"阈值右侧"的基矢翻转相位。由第 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\rangle$，$i=0,\ldots,N-1$）与**工作寄存器**（任意维数，存放辅助信息）。初态与输入无关；随后输入无关的酉变换与 oracle 调用交替进行。记第 $q$ 次查询前的算法态为 $|\psi_t^{(q)}\rangle$（它依赖输入 $t$），则

$$
|\psi_t^{(0)}\rangle=|\mathrm{init}\rangle,\qquad
|\psi_t^{(q+1)}\rangle=U^{(q)}O_t|\psi_t^{(q)}\rangle,
$$

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

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

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

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

(classical-lower-bounds)=
### 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_1a_2\cdots a_T$（$T$ 为停止时刻）天然自终止——算法一旦停止序列即结束，因此任何两个可能的答案序列都互不为对方前缀，构成前缀码。对长度为 $\ell_w$ 的前缀码与码字上的分布 $p$，Kraft 不等式给出 $K:=\sum_w2^{-\ell_w}\le1$；令 $q_w:=2^{-\ell_w}/K$，由 KL 散度非负（$\sum_wp_w\log_2\frac{p_w}{q_w}\ge0$）得

$$
H(p)\le\sum_wp_w\log_2\frac1{q_w}=\sum_wp_w\bigl(\ell_w+\log_2K\bigr)\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_rp_r\,H(A\,|\,R=r)\le\sum_rp_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\approx2^{9.24}$ 种可能，平均每次约 $2.31$ 比特），且无法突破对数量级（第 8 节）。

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

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

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

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

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

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

(one-cut-intuition)=
### 4.1 一次查询只"切一刀"

经典地，在位置 $i$ 比较一次，等于把候选集合 $\{0,\ldots,N\}$ 切成两半：$\{t\le i\}$ 与 $\{t>i\}$（第 1.2 节）。量子地，算法可以让查询寄存器处于叠加 $\sum_i\alpha_i|i\rangle$，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 加速的机制：全部输入信息凝聚为一个内积 $\langle x_0|s\rangle=\frac1{\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\rangle$ 让 oracle 同时翻转一段后缀的相位；随后的酉变换把不同候选阈值送往不同方向，使下一刀切在"更有信息量"的叠加上——不同候选阈值的相位边界于是产生不同的干涉模式。第 5 节的 Gram 矩阵正是把这件事变成全局优化：每一步应该把哪些候选状态拉开多少，同时不违反"一次查询只能施加一个阶跃相位"的约束。第 6–7 节的数值解告诉我们：精心设计的干涉能让每次查询平均换取约 $2.31$ 比特（$4$ 次查询区分 $605\approx2^{9.24}$ 种可能），远超经典的 $1$ 比特——优势是真的，但每查询的信息量仍是常数，对数量级纹丝不动。

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

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

### 5.1 状态与 Gram 矩阵

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

$$
G^{(q)}_{st}=\langle\psi_s^{(q)}|\psi_t^{(q)}\rangle,\qquad s,t\in\{0,\ldots,N\}.
$$

$G^{(q)}$ 是 $(N+1)\times(N+1)$ 的半正定矩阵（任何矢量族的 Gram 矩阵半正定：对复向量 $c$，$c^\dagger Gc=\|\sum_tc_t|\psi_t\rangle\|^2\ge0$）。由于初态与输入无关，

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

**引理 3（输入无关酉保持 Gram 矩阵）**。对任何酉 $U$，$\langle\psi_s|U^\dagger U|\psi_t\rangle=\langle\psi_s|\psi_t\rangle$，即输入无关酉前后的 Gram 矩阵相同。

**证明**。$U^\dagger U=I$，直接代入。Q.E.D.

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

### 5.2 按查询位置分解

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

$$
|\psi_t^{(q)}\rangle=\sum_i|i\rangle\otimes|\varphi_{t,i}^{(q)}\rangle,\qquad|\varphi_{t,i}^{(q)}\rangle:=(\langle i|\otimes I)|\psi_t^{(q)}\rangle.
$$

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

$$
\bigl(G_i^{(q)}\bigr)_{st}:=\langle\varphi_{s,i}^{(q)}|\varphi_{t,i}^{(q)}\rangle.
$$

**引理 4**。每个 $G_i^{(q)}\succeq0$，且 $\sum_iG_i^{(q)}=G^{(q)}$。

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

$$
c^\dagger G_i^{(q)}c=\sum_{s,t}\bar c_sc_t\langle\varphi_{s,i}^{(q)}|\varphi_{t,i}^{(q)}\rangle
=\Bigl\langle\sum_tc_t|\varphi_{t,i}^{(q)}\rangle\,,\ \sum_tc_t|\varphi_{t,i}^{(q)}\rangle\Bigr\rangle\ge0.
$$

求和：$\sum_i(G_i^{(q)})_{st}=\sum_i\langle\varphi_{s,i}^{(q)}|\varphi_{t,i}^{(q)}\rangle=\langle\psi_s^{(q)}|\psi_t^{(q)}\rangle$，最后一步是因为查询寄存器的基矢两两正交，交叉项 $\langle i|j\rangle=0\ (i\ne j)$ 全部清零。Q.E.D.

(gram-update-rule)=
### 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$ 是元素为 $\pm1$ 的对称矩阵、对角线全 $+1$。注意 $D_i$ 只依赖问题（阈值阶跃结构），不依赖算法。

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

$$
\widetilde G^{(q)}=\sum_iG_i^{(q)}\circ D_i,
$$

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

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

$$
\begin{aligned}
\langle\psi_s^{(q)}|O_s^\dagger O_t|\psi_t^{(q)}\rangle
&=\sum_{i,j}(-1)^{z_i^{(s)}}(-1)^{z_j^{(t)}}\langle i|j\rangle\,\langle\varphi_{s,i}^{(q)}|\varphi_{t,j}^{(q)}\rangle\\
&=\sum_i(-1)^{z_i^{(s)}+z_i^{(t)}}\,(G_i^{(q)})_{st},
\end{aligned}
$$

第二步用了 $\langle i|j\rangle=\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.

(sdp-characterization)=
### 5.4 精确求解的刻画：一个 SDP 可行性问题

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

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

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

**证明**。

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

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

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

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

**证明**。定义 $V\bigl(\sum_tc_t|a_t\rangle\bigr):=\sum_tc_t|b_t\rangle$。**良定义**：若 $\sum_tc_t|a_t\rangle=0$，则

$$
\Bigl\|\sum_tc_t|b_t\rangle\Bigr\|^2=\sum_{s,t}\bar c_sc_t\langle b_s|b_t\rangle
=\sum_{s,t}\bar c_sc_t\langle a_s|a_t\rangle=\Bigl\|\sum_tc_t|a_t\rangle\Bigr\|^2=0,
$$

故 $\sum_tc_t|b_t\rangle=0$，$V$ 在表示不唯一时也给同一结果。**等距**：同一计算给出 $\langle Vx|Vy\rangle=\langle x|y\rangle$。于是 $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}\rangle=\sum_i|i\rangle\otimes|w_i\rangle$，故 $(G_i^{(0)})_{st}=\langle w_i|w_i\rangle=:p_i$ 与 $s,t$ 无关，即 $G_i^{(0)}=p_iJ$，其中 $p_i\ge0$、$\sum_ip_i=\|\mathrm{init}\|^2=1$。代入定理 5（并注意 $J\circ D_i=D_i$，因为 $D_i$ 的元素全是 $\pm1$）：

$$
G^{(1)}=\sum_ip_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^{(1)}_{st}=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^{(1)}_{02}=-(p_0+p_1)=-1$；
- 对 $(0,1)$：只有位置 $0$ 分居两侧 $\Rightarrow G^{(1)}_{01}=p_1-p_0$；
- 对 $(1,2)$：只有位置 $1$ 分居两侧 $\Rightarrow G^{(1)}_{12}=p_0-p_1$。

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

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

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

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

### 5.6 有界误差：measurement feasibility

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

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

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

$$
\langle\psi_s|E_s|\psi_s\rangle\ge1-\varepsilon,\qquad
\langle\psi_t|E_s|\psi_t\rangle\le1-\langle\psi_t|E_t|\psi_t\rangle\le\varepsilon,
$$

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

于是有界误差版本就是把"$G^{(Q)}=I$"放宽为"非对角内积足够小"（配合测量变量的精确形式）；取 $\varepsilon\to0$ 也顺带补上了定理 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^{(t)}_i=\mathbf 1[(i-t)\bmod L<m]$（弧长 $m$ 固定）。它满足**平移等变性**

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

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

(group-average-symmetrization)=
### 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:=\frac1{|\Sigma|}\sum_{\sigma\in\Sigma}\sigma\cdot x$ 仍属于 $\mathcal F$，且是 $\Sigma$ 的不动点。

**证明**。半正定锥是凸锥，故 $\bar x\succeq0$（半正定约束保持）。对线性等式 $g(x)=0$：由 $g$ 线性与每个 $\sigma\cdot x$ 可行，$g(\bar x)=\frac1{|\Sigma|}\sum_\sigma g(\sigma\cdot x)=0$。不动点：对 $\tau\in\Sigma$，$\tau\cdot\bar x=\frac1{|\Sigma|}\sum_\sigma(\tau\sigma)\cdot x=\frac1{|\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)\bmod L$）。再加反射对称（阈值次序取逆），解还可取成实的、只依赖 $\pm(s-t)$。就原问题而言，这正是"Gram 矩阵近似只依赖 $s-t$"——循环化在扩展问题中是精确的，回到直线问题时只在端点附近有边界效应。

### 6.3 循环矩阵与 Laurent 多项式

**引理 10**。设 $C$ 是 $L\times L$ 循环矩阵：$C_{st}=c_{(s-t)\bmod 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\bmod L}=\bar c_d$）半正定 $\iff$ 对所有 $L$ 次单位根 $\omega$ 有 $\lambda(\omega)\ge0$。

**证明**。直接计算（代换 $d=(s-t)\bmod L$，即 $t=(s-d)\bmod L$，求和遍历 $\mathbb Z_L$）：

$$
(Cf_\omega)_s=\sum_tc_{(s-t)\bmod L}\,\omega^t=\sum_dc_d\,\omega^{(s-d)\bmod L}=\omega^s\sum_dc_d\omega^{-d},
$$

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

意义：$\lambda(\omega)$ 是 Laurent 多项式 $p(x)=\sum_dc_dx^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\iff i<t$"的推理在块结构上的重演。**（iii）分块不必整除**：把大小为 $n$ 的候选集合分成 $M$ 块、每块至多 $\lceil n/M\rceil$ 个（末块可小），块数仍固定为 $M$，子程序照常适用；这样每层候选数精确地缩到 $\lceil n/M\rceil$ 倍，不产生随深度累积的额外查询。

(recursion-query-count)=
### 7.2 查询数：逐项分析与参数平衡

**定理 11**。上述递归给出

$$
Q(N)\ \le\ q\log_MN+O(1)=\frac q{\log_2M}\log_2N+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\le2N/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_MN+O(1).
$$

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

复杂度表达式逐项拆开：

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

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

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

$$
\log_2605=\frac{\ln605}{\ln2},\qquad 605=512\times1.18164\ldots,
$$

$$
\log_2605=9+\log_21.18164\ldots=9+\frac{\ln1.18164\ldots}{\ln2}\approx9+\frac{0.16698}{0.69315}\approx9.241,
$$

$$
Q(N)\ \le\ 4\log_{605}N+O(1)=\frac4{9.241}\log_2N+O(1)\approx0.433\log_2N+O(1).
$$

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

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

(adversary-lower-bound)=
### 8.1 对抗方法的逻辑

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

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

过滤 $\Gamma$。对抗比值

$$
\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}
$$

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

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

$$
(1-2\varepsilon)\,\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|};
$$

特别地，精确算法至少需要 $\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}$ 次查询。证明见对抗方法的标准文献；本章的 [Boolean 公式求值](formula-evaluation-span-programs.md)一讲会在 SDP 对偶视角下统一处理这类界。

三个因子各自的含义：

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

于是"选一个好的 $\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,\ldots,n$）。对 $n=4$：$\pm1.618\ldots$、$\pm0.618\ldots$，故 $\|\Gamma\|=2\cos\frac\pi5\approx1.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$，故精确算法至少 $\lceil1.618\rceil=2$ 次查询；二分搜索（先比中点 $y_1$，再比一侧）恰好用 $2$ 次，所以 $N=3$（4 个阈值）时精确查询数是 $2$，对抗界在此是紧的。顺带一提，例 2 的单查询不可能性论证对 $N=3$ 同样适用：最远输入对 $(0,3)$ 在所有位置上都分居两侧，故任何单查询后 $G^{(1)}_{03}=-1\ne0$。

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

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

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

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

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

$$
Q(N)\ \ge\ \frac{\ln2}{\pi}\log_2N-O(1)\ \approx\ 0.221\log_2N-O(1);
$$

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

### 8.4 缺口与三种口径

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

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

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

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

## 9. 小结

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

## 练习题

**练习 1【插入位置与阈值 oracle】**（→ [1.3 节](#threshold-oracle)）

1. 写出 $N=3$ 时四个阈值 oracle 的相位向量，并验证 $z^{(s)}$ 与 $z^{(t)}$ 的汉明距离恰为 $|s-t|$。
2. 证明比较约定 $[x>y_i]=1-z_i^{(t)}$ 与 $z$ 约定给出的 oracle 只相差一个全局因子 $-1$，因此两种约定对所有测量概率给出相同结果。

> 提示：逐位有 $(-1)^{1-z_i^{(t)}}=-(-1)^{z_i^{(t)}}$，即两个 oracle 满足 $O'_t=-O_t$。

**练习 2【二分搜索与两个经典下界】**（→ [2.1 节](#classical-lower-bounds)）

1. 计算 $N=100$ 与 $N=1000$ 时二分搜索的最坏比较次数，并与 $\lceil\log_2(N+1)\rceil$ 核对。
2. 证明决策树下界：正确算法的决策树至少有 $N+1$ 片叶子，而深度为 $d$ 的二叉树至多 $2^d$ 片叶子。
3. 说明熵下界证明的第二步（$H(t\,|\,R)\le H(A\,|\,R)$）为何用到"函数不增熵"，并指出这一步在排除随机化中的作用。

> 提示：零误差意味着固定随机串 $r$ 后，阈值 $t=f_r(A)$ 是答案序列的函数。

**练习 3【一刀、链与干涉的直觉】**（→ [4.1 节](#one-cut-intuition)）

1. 用"切一刀"的语言解释：在位置 $i$ 的一次查询把候选集合 $\{0,\ldots,N\}$ 切成哪两部分？为什么无论振幅如何叠加，一次量子查询在"区分输入对"的意义上仍只切一刀？
2. 对比 Grover：说明有序搜索的嵌套链 oracle 为什么不存在所有输入共享的二维不变子空间与统一旋转角。
3. 结合例 2（一次查询对 Gram 矩阵的影响 $=$ 切矩阵的凸组合），解释量子优势为什么只能来自多轮之间的干涉。

> 提示：单次查询对两两内积的影响与一次经典随机比较完全相同。

**练习 4【Gram 矩阵与查询更新规则】**（→ [5.3 节](#gram-update-rule)）

1. 证明输入无关酉操作保持 Gram 矩阵（引理 3），并解释为什么这使 SDP 里只需建模查询步、而把所有 $U^{(q)}$ 消元。
2. 取均匀叠加初态（例 4 的设置），推导一次查询后 $G^{(1)}_{st}=1-\frac{2(t-s)}{N}$（$s<t$），并对 $N=3$ 写出完整的 $4\times4$ 矩阵、验证 $G^{(1)}_{03}=-1$。
3. 证明：对任意 $N\ge1$，任何单查询量子算法都不能精确求解有序搜索。

> 提示：$D_i$ 恰在 $i\in[s,t)$ 的位置上取 $-1$，共 $t-s$ 个。

**练习 5【精确求解的 SDP 刻画】**（→ [5.4 节](#sdp-characterization)）

1. 写出定理 6 的三条线性约束，并说明它们分别对应算法的初态、每次查询与末态测量。
2. 证明酉扩张引理（引理 7），并说明它在定理 6 的重构中扮演的角色：为什么不能直接用"两组矢量内积相同"拼出算法，而必须补一个酉？
3. 由引理 8 计算：若末态内积 $|G^{(Q)}_{st}|=\frac12$，误差 $\varepsilon$ 至少是多少？

> 提示：先证良定义性——若 $\sum_tc_t|a_t\rangle=0$，则 $\sum_tc_t|b_t\rangle=0$。

**练习 6【凸平均与循环矩阵压缩】**（→ [6.2 节](#group-average-symmetrization)）

1. 复述引理 9 的证明要点（半正定锥是凸锥、线性等式在平均下保持），并解释为什么"把算法对称化"只能在 Gram/SDP 世界进行、不能直接对线路做平均。
2. 对 $L=2$ 的循环矩阵（系数 $c_0,c_1$）写出两个 Fourier 特征值，并给出半正定的充要条件。
3. 证明循环矩阵的 Fourier 对角化（引理 10），并说明 Hermitian 循环矩阵的半正定性为何等价于一个 Laurent 多项式在单位圆（的 $L$ 次单位根处）非负。

> 提示：直接计算 $(Cf_\omega)_s$，代换 $d=(s-t)\bmod L$ 并用 $\omega^L=1$。

**练习 7【递归拼接与参数平衡】**（→ [7.2 节](#recursion-query-count)）

1. 说明递归构造中"问题形状不变"的含义：找到正确块之后，块内定位阈值为何仍是与原问题相同的有序搜索？
2. 从 $q=4$、$M=605$ 计算 $\frac q{\log_2M}$（给出中间步骤），并算出该模块平均每次查询传递多少比特；再判断：$q=3$、$M=100$ 的模块（若存在）是否优于它？
3. 用归纳法证明定理 11 中的断言：只要 $M^d\le N$ 就有 $n_d\le\frac{2N}{M^d}$，并解释底部门槛 $M_0$ 为何只贡献 $O(1)$ 次查询。

> 提示：$n_{d+1}\le\lceil n_d/M\rceil\le n_d/M+1$，末步用 $1\le N/M^{d+1}$。

**练习 8【对抗下界与三种口径】**（→ [8.1 节](#adversary-lower-bound)）

1. 解释对抗比值 $\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}$ 中分子与分母各自的含义，并说明它与"一次查询只切一刀"的对应。
2. 对 $N=2$（三个阈值、两个位置）取近邻权重 $\Gamma_{st}=1$（$|s-t|=1$，否则为 $0$）：计算 $\|\Gamma\|$、每个 $\|\Gamma\circ\Delta_i\|$ 与比值，给出下界，并与例 3 的结论比较。
3. 解释"期望查询数少于 $\frac13\log_2N$"为何不与"精确最坏情形可用 $0.433\log_2N$ 完成、且至少需要 $0.221\log_2N$"直接矛盾。

> 提示：$P_3$ 的邻接谱为 $\{0,\pm\sqrt2\}$；$\Delta_i$ 只保留分居位置 $i$ 两侧的输入对。

## 参考文献

- Zoo 编号 39：Farhi、Goldstone、Gutmann 与 Sipser, [Invariant Quantum Algorithms for Insertion into an Ordered List](https://arxiv.org/abs/quant-ph/9901059).
- Zoo 编号 103：Andrew Childs、Andrew Landahl 与 Pablo Parrilo, [Improved Quantum Algorithms for the Ordered Search Problem via Semidefinite Programming](https://arxiv.org/abs/quant-ph/0608161).
- Zoo 编号 219、24：Høyer--Neerbek--Shi 与 [Childs--Lee](https://arxiv.org/abs/0708.3396) 的 adversary 下界。
- Zoo 编号 10：Michael Ben-Or 与 Avinatan Hassidim, [Quantum Search in an Ordered List via Adaptive Learning](https://arxiv.org/abs/quant-ph/0703231).