量子顺序搜索：半定规划模块与常数因子优势¶
在 Grover 算法中我们研究过一个极端：对数据库的结构一无所知，\(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 算法（相位 oracle、查询模型、反射与旋转的语言）。半定规划方面，本教程自含所需的一点点内容：读者只需接受"变量是半正定矩阵、约束是线性等式"就是一个可以数值求解的问题。
本课知识点
插入位置与阈值 oracle——能把有序搜索改写为阈值 \(t\in\{0,\ldots,N\}\) 的查询问题，写出阶跃位串 \(z^{(t)}\) 与相位 oracle，并验证汉明距离 \(|s-t|\) 与嵌套链结构。
二分搜索与两个经典下界——能证明决策树下界 \(\lceil\log_2(N+1)\rceil\)，并用前缀码的熵界说明随机化的期望比较数仍至少 \(\log_2(N+1)\)。
一刀、链与干涉的直觉——能解释一次量子查询为何在"区分输入对"的意义上仍只"切一刀"、有序搜索为何没有 Grover 式统一旋转角，以及量子的余地为何只能来自多轮干涉。
Gram 矩阵与查询更新规则——能证明输入无关酉保持 Gram 矩阵、把算法态按查询位置分解，并推导更新规则 \(G^{(q+1)}=\sum_iG_i^{(q)}\circ D_i\)。
精确求解的 SDP 刻画——能写出精确算法存在性的三条线性约束，并用谱分解与酉扩张引理从可行解重构出量子算法。
凸平均与循环矩阵压缩——能证明凸平均引理（可行集的凸性使对称化合法），并通过循环矩阵的 Fourier 对角化把半正定性化为 Laurent 多项式在单位根处的非负性。
递归拼接与参数平衡——能用候选数的归纳估计证明 \(Q(N)\le q\log_MN+O(1)\)，并计算、比较模块的渐近常数 \(\frac q{\log_2M}\)。
对抗下界与三种口径——能解释对抗比值 \(\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}\) 中分子与分母的含义，手算路径权重的例子，并说明 \(0.221\)–\(0.433\) 的缺口与三种口径为何不可直接比较。
1. 问题的精确表述¶
1.1 插入位置：\(N+1\) 种答案¶
设表中元素严格递增：
并引入哨兵 \(y_{-1}=-\infty\)、\(y_N=+\infty\)。约定 \(x\) 不等于任何 \(y_i\)（若可能与某个 \(y_i\) 相等，先花一次比较把该情形剔除即可，不影响渐近行为）。于是存在唯一的插入位置
任务是确定 \(t\)。注意答案共有 \(N+1\) 种——这个"\(+1\)"贯穿全文：它既出现在经典下界 \(\lceil\log_2(N+1)\rceil\) 中，也是后文矩阵的尺寸。
1.2 比较是阈值函数¶
与 \(y_i\) 的一次比较只能问"\(x\) 是否大于 \(y_i\)"，其答案由 \(t\) 完全决定。推导只用到插入位置的定义：
也就是说，知道 \(t\) 就知道所有比较的答案；反之，比较是仅有的信息来源。这提示我们把输入抽象为阈值 \(t\)、把比较抽象为 oracle，进入查询复杂度模型：算法看不见数据本身，只能通过 oracle 提问，我们只数提问次数。
1.3 阈值 oracle 与相位形式¶
把"\(x\) 应插到排序表哪里"改写为未知阈值 \(t\in\{0,\ldots,N\}\)。定义位串（查询位置 \(i\in\{0,\ldots,N-1\}\)）
\(z^{(t)}\) 是一条阶跃函数：前 \(t\) 个位置为 \(0\)，其后全为 \(1\)。oracle 可用相位形式
即对"阈值右侧"的基矢翻转相位。由第 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\)），则
其中每个 \(U^{(q)}\) 都是输入无关的酉。查询复杂度是 \(O_t\) 的调用次数（\(U^{(q)}\) 的门数不计）。按对"成功"的记账方式，有三种口径：
精确、最坏情形：对每个输入都零误差地输出 \(t\)，查询数按最坏输入计；
有界误差：每个输入的错误概率至多 \(\varepsilon\)，仍按最坏输入计；
期望：对某个输入分布（通常取均匀）平均的查询数。
这三种口径的数值不能直接比较大小（第 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_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\)）得
第二步：记 \(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)\)，而
其中不等号对每个固定的 \(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 式的统一旋转角；量子的余地究竟在哪里。
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)}\) 是 \((N+1)\times(N+1)\) 的半正定矩阵（任何矢量族的 Gram 矩阵半正定：对复向量 \(c\)，\(c^\dagger Gc=\|\sum_tc_t|\psi_t\rangle\|^2\ge0\)）。由于初态与输入无关，
引理 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\)）：
对每个位置 \(i\)，定义块矩阵
引理 4。每个 \(G_i^{(q)}\succeq0\)，且 \(\sum_iG_i^{(q)}=G^{(q)}\)。
证明。半正定：对任意复向量 \(c\)，
求和：\(\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.
5.3 查询如何更新 Gram 矩阵¶
定义相位差矩阵（以阈值对为索引）
由第 1.3 节，\((D_i)_{st}=-1\) 当且仅当 \(i\) 落在 \(s,t\) 之间；\(D_i\) 是元素为 \(\pm1\) 的对称矩阵、对角线全 \(+1\)。注意 \(D_i\) 只依赖问题（阈值阶跃结构），不依赖算法。
定理 5（查询更新规则）。一次查询把 \(G^{(q)}\) 变为
其中 \(\circ\) 是 Hadamard（逐元素）积；随后的输入无关酉不改变它，故 \(G^{(q+1)}=\widetilde G^{(q)}\)。
证明。逐个内积计算。查询后、酉之前，两个态是 \(O_s|\psi_s^{(q)}\rangle\) 与 \(O_t|\psi_t^{(q)}\rangle\)：
第二步用了 \(\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.
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)}\)）：
\(G^{(0)}=J\)（初始内积全为 \(1\)）；
对 \(q=0,\ldots,Q-1\)：\(\sum_iG_i^{(q)}\circ D_i=G^{(q+1)}\)；
\(\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\)，则
故 \(\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\)）：
解读：一次量子查询——无论振幅如何叠加、是否与工作寄存器纠缠——对两两内积的影响，与"以概率 \(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\) 个：
一次查询后的"距离核"是线性的：相邻对（\(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\) 与成功条件，
平均成功率至少 \(\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\) 固定）。它满足平移等变性
验证：\((i-(t+1))\bmod L=((i-1)-t)\bmod 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:=\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\) 的特征向量，特征值为
特别地，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\)）：
末步用了 \(\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\) 查询算法？流程是：
写出第 5 节的 SDP（输入标签只有 \(M\) 个）；
用第 6.2–6.3 节的对称化把变量压成 Fourier 系数；
用数值 SDP 求解器找可行点；
按定理 6 的重构（谱分解 + 引理 7）从 Gram 分解显式恢复各步酉矩阵。
警告（不可省略的一步）。SDP 求解器返回浮点数，而"浮点可行"不等于"精确可行"：约束要求等式精确成立、矩阵精确半正定。要宣称一个精确算法，必须把数值解高精度化——把条目舍入为小分母有理数（或代数数）——然后代回约束做精确验证，或者给出严格的对偶证书。不能只把浮点 SDP 状态当作精确算法的证明。原文献对其 \((q,M)=(4,605)\) 模块正是这样处理的。
7. 递归拼接：从模块到任意 \(N\)¶
7.1 构造¶
若一个 \(q\) 查询子程序能确定阈值落在 \(M\) 个有序子区间中的哪一个，就把长度 \(N\) 的列表按比例分成 \(M\) 块：
用该子程序找出正确块；
在块内递归使用同一程序；
直到候选只剩一个位置。
三点实现说明。（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\) 倍，不产生随深度累积的额外查询。
7.2 查询数：逐项分析与参数平衡¶
定理 11。上述递归给出
证明。记 \(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\) 层内结束，而
每层恰好 \(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\) 的精确模块。计算常数：
它比早期约 \(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)\)¶
8.1 对抗方法的逻辑¶
令 adversary 矩阵 \(\Gamma\) 以阈值 \(s,t\) 为索引：实对称、对角线为零（可以非负，也可以变号），它的每个元素 \(\Gamma_{st}\) 是我们指派给输入对 \((s,t)\) 的"未区分程度"。一次查询位置 \(i\) 只能区分那些阈值分别位于 \(i\) 两侧的输入对，即用
过滤 \(\Gamma\)。对抗比值
给出查询下界。精确地说：
定理 12（谱对抗界，引用不证）。对任何实对称、零对角的 \(\Gamma\)，任何误差 \(\le\varepsilon\) 的量子算法的查询数至少为
特别地，精确算法至少需要 \(\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}\) 次查询。证明见对抗方法的标准文献；本章的 Boolean 公式求值一讲会在 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 通过仔细的谱计算构造出合适的权重，得到
Childs–Lee 随后把"选权重"本身写成一个最优化问题（同样可 SDP 化）来处理，复核并推广了这一构造。我们把 \(c=\frac{\ln2}{\pi}\) 的谱计算留在原文；对本教程而言，重要的是结构：分子对数增长、分母有界，故任何量子算法都需要 \(\Omega(\log N)\) 次查询。
8.4 缺口与三种口径¶
上界 \(0.433\) 与下界 \(0.221\) 之间仍有常数空隙，精确渐近常数未知。此外，随机化量子算法可通过 adaptive learning 把期望查询常数降到 \(\frac13\) 以下（Ben-Or–Hassidim：把"下一步比较哪里"交给一个量子自适应过程去学习，使期望树深低于均匀二分），但期望、有界错误与最坏精确三种口径不能直接比较。展开说（对应文末练习 8 第 3 题）：
\(0.433\log_2N\) 是"精确、最坏"口径的上界，不是精确值——真实常数可以低到 \(0.221\)，因此"期望 \(<\frac13\)"与之毫无冲突；
"期望"对输入分布平均，允许个别分支很深：期望小不蕴含最坏小（当然期望 \(\le\) 最坏，两者并存永远合法）；
口径放宽会同步削弱下界：有界误差时定理 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 节）
写出 \(N=3\) 时四个阈值 oracle 的相位向量，并验证 \(z^{(s)}\) 与 \(z^{(t)}\) 的汉明距离恰为 \(|s-t|\)。
证明比较约定 \([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 节）
计算 \(N=100\) 与 \(N=1000\) 时二分搜索的最坏比较次数，并与 \(\lceil\log_2(N+1)\rceil\) 核对。
证明决策树下界：正确算法的决策树至少有 \(N+1\) 片叶子，而深度为 \(d\) 的二叉树至多 \(2^d\) 片叶子。
说明熵下界证明的第二步（\(H(t\,|\,R)\le H(A\,|\,R)\)）为何用到"函数不增熵"，并指出这一步在排除随机化中的作用。
提示：零误差意味着固定随机串 \(r\) 后，阈值 \(t=f_r(A)\) 是答案序列的函数。
练习 3【一刀、链与干涉的直觉】（→ 4.1 节）
用"切一刀"的语言解释：在位置 \(i\) 的一次查询把候选集合 \(\{0,\ldots,N\}\) 切成哪两部分？为什么无论振幅如何叠加，一次量子查询在"区分输入对"的意义上仍只切一刀？
对比 Grover：说明有序搜索的嵌套链 oracle 为什么不存在所有输入共享的二维不变子空间与统一旋转角。
结合例 2（一次查询对 Gram 矩阵的影响 \(=\) 切矩阵的凸组合），解释量子优势为什么只能来自多轮之间的干涉。
提示：单次查询对两两内积的影响与一次经典随机比较完全相同。
练习 4【Gram 矩阵与查询更新规则】（→ 5.3 节）
证明输入无关酉操作保持 Gram 矩阵（引理 3），并解释为什么这使 SDP 里只需建模查询步、而把所有 \(U^{(q)}\) 消元。
取均匀叠加初态（例 4 的设置），推导一次查询后 \(G^{(1)}_{st}=1-\frac{2(t-s)}{N}\)（\(s<t\)），并对 \(N=3\) 写出完整的 \(4\times4\) 矩阵、验证 \(G^{(1)}_{03}=-1\)。
证明：对任意 \(N\ge1\)，任何单查询量子算法都不能精确求解有序搜索。
提示：\(D_i\) 恰在 \(i\in[s,t)\) 的位置上取 \(-1\)，共 \(t-s\) 个。
练习 5【精确求解的 SDP 刻画】（→ 5.4 节）
写出定理 6 的三条线性约束，并说明它们分别对应算法的初态、每次查询与末态测量。
证明酉扩张引理（引理 7），并说明它在定理 6 的重构中扮演的角色：为什么不能直接用"两组矢量内积相同"拼出算法，而必须补一个酉？
由引理 8 计算：若末态内积 \(|G^{(Q)}_{st}|=\frac12\)，误差 \(\varepsilon\) 至少是多少？
提示：先证良定义性——若 \(\sum_tc_t|a_t\rangle=0\)，则 \(\sum_tc_t|b_t\rangle=0\)。
练习 6【凸平均与循环矩阵压缩】（→ 6.2 节）
复述引理 9 的证明要点（半正定锥是凸锥、线性等式在平均下保持），并解释为什么"把算法对称化"只能在 Gram/SDP 世界进行、不能直接对线路做平均。
对 \(L=2\) 的循环矩阵（系数 \(c_0,c_1\)）写出两个 Fourier 特征值，并给出半正定的充要条件。
证明循环矩阵的 Fourier 对角化（引理 10），并说明 Hermitian 循环矩阵的半正定性为何等价于一个 Laurent 多项式在单位圆（的 \(L\) 次单位根处）非负。
提示：直接计算 \((Cf_\omega)_s\)，代换 \(d=(s-t)\bmod L\) 并用 \(\omega^L=1\)。
练习 7【递归拼接与参数平衡】（→ 7.2 节）
说明递归构造中"问题形状不变"的含义：找到正确块之后，块内定位阈值为何仍是与原问题相同的有序搜索？
从 \(q=4\)、\(M=605\) 计算 \(\frac q{\log_2M}\)（给出中间步骤），并算出该模块平均每次查询传递多少比特；再判断：\(q=3\)、\(M=100\) 的模块（若存在）是否优于它？
用归纳法证明定理 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 节）
解释对抗比值 \(\frac{\|\Gamma\|}{\max_i\|\Gamma\circ\Delta_i\|}\) 中分子与分母各自的含义，并说明它与"一次查询只切一刀"的对应。
对 \(N=2\)（三个阈值、两个位置）取近邻权重 \(\Gamma_{st}=1\)（\(|s-t|=1\)，否则为 \(0\)）：计算 \(\|\Gamma\|\)、每个 \(\|\Gamma\circ\Delta_i\|\) 与比值，给出下界，并与例 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.
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.