通配符搜索：Pretty-Good Measurement 每轮学习 \(\Theta(\sqrt n)\) 位¶

我们要研究的问题叫做通配符搜索 (search with wildcards)，它源自一个更古老的问题——oracle 审讯 (oracle interrogation)：一个未知的比特串 \(x\in\{0,1\}^n\) 藏在 oracle 里，你只能通过查询与它交互，目标是把 \(x\) 完整地输出出来。

在普通的位查询模型（一次读一位）下，这个问题的答案已经被了解得很透彻：经典算法恰好需要 \(n\) 次查询；量子算法可以省下一半——van Dam 的算法用 \(n/2+O(\sqrt n)\) 次查询以常数成功概率学到 \(x\)，而 Farhi、Goldstone、Gutmann 与 Sipser 随后给出了匹配的 \(n/2+\Omega(\sqrt n)\) 下界。换言之，位查询下的量子加速被死死钉在线性上：\(n/2+\Theta(\sqrt n)\)。

Ambainis 与 Montanaro 在 2012 年（Zoo 编号 167）换了一种提问方式，线性壁垒应声而碎。他们允许一次查询提交任意子集 \(S\subseteq[n]\) 和候选子串 \(y\)，询问"\(x_S=y\) 是否整体成立"。经典算法面对这种增强的 oracle 毫无办法——每次回答仍然只有一比特，信息论下界依旧是 \(\Omega(n)\)。但量子算法可以做到

\[ O(\sqrt n\log n) \ \text{次查询（期望）}, \qquad \text{而任何量子算法都需要}\ \Omega(\sqrt n)\ \text{次。} \]

更有意思的是它的设计模式：这个加速既不来自振幅放大，也不来自量子行走（参见 Grover 算法与碰撞与元素唯一性中的两类套路），而是来自一个状态判别 (state discrimination) 问题——用 Pretty-Good Measurement 从一堆非正交态里"读出"一个近乎正确的整串猜测。本教程的标题正是在描述它的工作方式：每一轮把已知的位数从 \(k\) 推进到 \(k+\Theta(\sqrt k)\)，一共 \(O(\sqrt n)\) 轮，每轮付出 \(O(\log n)\) 次查询去验证并修正猜测。

前置知识：本站读者应已熟悉 Grover 算法与量子傅里叶变换（特别是 \(\mathbb Z_2^n\) 上特征标的正交性）、密度矩阵与 POVM 的基本操作。这些工具本文直接使用，不再重新推导。

阅读路线：第 1 节形式化模型并给出经典与位查询量子的两道下界；第 2 节用平实语言讲清算法的核心直觉；第 3 节是全文的技术心脏——子集态、Gram 矩阵的 Fourier 对角化与 PGM；第 4 节把状态判别装配成完整的阶梯生长算法；第 5 节核算复杂度并证明 \(\Omega(\sqrt n)\) 下界；第 6 节讨论与普通 oracle、组合群检测的关系（包括一段值得引以为戒的修正史）；第 7 节给出若干可手算的数值例子。

本课知识点

通配符查询模型——能写出通配符查询 \(Q_x(S,y)\) 与酉 oracle 的形式，并说明它与位查询模型的关系（整段验证而非逐位读取、\(|S|=1\) 时退化为位查询）。
经典与位查询的线性壁垒——能用记录计数与鸽笼原理证明确确定性经典算法需要 \(n\) 次查询，并解释位查询模型中量子复杂度被钉在 \(n/2+\Theta(\sqrt n)\) 的根源。
猜—验—修的算法直觉——能解释"验证与修错便宜、好的猜测靠子集态的量子冗余"两个部件如何配合，并核算 \(O(\sqrt n)\times O(\log n)\) 的算术骨架。
子集态与 Gram 矩阵——能写出子集态 \(|\psi_x^k\rangle\) 的定义，推导其两两内积公式并说明它只依赖汉明距离、缺失 \(c\sqrt n\) 位时邻近态几乎平行。
Fourier 对角化与谱窗口——能证明特征标 \(\chi_z\) 对角化 Gram 矩阵、使用特征值闭式 \(\lambda(z)\)，并解释谱以 \(n/m\) 尺度衰减如何钉出 \(\sqrt n\) 分辨率窗口。
Pretty-Good Measurement 与期望常数个错误——能验证 PGM 是合法 POVM、写出输出概率公式 \((\sqrt G_{yx})^2\)，并把期望错误数化为单比特 Fourier 偏差，说明每比特错误率为 \(O(1/n)\)。
阶梯生长算法与总复杂度——能列出第 0 阶段与扩张阶段的五个步骤，推导阶段数 \(L=\Theta(\sqrt n)\) 并核算总查询数 \(O(\sqrt n\log n)\)。
量子下界与近最优性——能用强加权对抗法的权重方案证明 \(\Omega(\sqrt n)\) 下界，并比较上界说明对数因子的来源。

1. Oracle 模型：换一种提问方式¶

1.1 两种查询¶

先固定记号。\([n]:=\{1,2,\dots,n\}\)；对串 \(x\in\{0,1\}^n\)，\(|x|\) 表示汉明重量，\(d(x,y):=|\{i:x_i\ne y_i\}|\) 表示汉明距离。对子集 \(S\subseteq[n]\)，把 \(S\) 中的位置按升序排列后，\(x_S\in\{0,1\}^{|S|}\) 表示 \(x\) 限制在 \(S\) 上的子串。

位查询 (bit query) 是标准的查询模型：指定一个位置 \(i\in[n]\)，oracle 返回 \(x_i\)。

通配符查询 (wildcard query) 由两个寄存器的内容指定：

\[ S\subseteq[n],\qquad y\in\{0,1\}^{|S|}, \]

oracle 返回

\[ Q_x(S,y)=1[x_S=y], \]

即"未知串在 \(S\) 上的取值是否整体等于候选串 \(y\)"。等价地，可以把一次查询写成模式串 \(s\in\{0,1,*\}^n\)：* 所在的位置不检查，其余位置必须与 \(x\) 逐一相同。两种写法一一对应：\(S\) 是 \(s\) 中非 * 位置之集，\(y\) 是 \(s\) 在这些位置上的值。

量子算法访问的是酉版本的 oracle：

其中 \(z\) 是一个答案比特。注意查询寄存器本身可以是叠加态——这是后文一切"一次查询处理所有分支"操作的物理基础。要相位版本的 oracle（把答案 kick back 成 \((-1)^{Q_x}\)），只需在答案比特上准备 \((|0\rangle-|1\rangle)/\sqrt2\)，这是我们在 Grover 算法中反复用过的标准改写。

两个直接观察：

若限制 \(|S|=1\)，通配符查询退化为位查询（问"\(x_i\) 是否等于 \(b\)"，两次即可读出 \(x_i\)）。所以通配符模型严格强于标准模型。
通配符查询的语义是验证而非读取：它只会告诉你一个猜测对不对，不会主动告诉你正确的值是什么。这个不对称性是全文的伏笔。

1.2 经典下界：一问一比特¶

命题 1. 任何确定性经典算法若对每个输入 \(x\in\{0,1\}^n\) 都正确输出 \(x\)，必须至少做 \(n\) 次查询。允许随机性与有界错误的经典算法同样需要 \(\Omega(n)\) 次查询。

证明（确定性情形）。固定算法，考察它在输入 \(x\) 上实际执行的查询序列与得到的答案序列，合称记录 (transcript)。查询是自适应的，但每次的答案 \(Q_x(S,y)\in\{0,1\}\) 是一比特，因此做 \(q\) 次查询的算法至多产生 \(2^q\) 种不同的记录，而算法的输出只依赖记录。若 \(q<n\)，则 \(2^q<2^n\)，由鸽笼原理存在两个不同的输入 \(x\ne x'\) 产生完全相同的记录，于是算法对二者输出同一个串，至少错一个。故 \(q\ge n\)。Q.E.D.

随机情形的标准论证是信息论式的：无论查询多么自适应，每一比特答案作为 \(x\) 的函数至多携带关于 \(x\) 的一比特互信息；\(q\) 次查询的全部记录与 \(x\) 的互信息至多为 \(q\) 比特，而要以概率 \(2/3\) 输出 \(n\) 比特的 \(x\)，需要"知道"其中 \(\Omega(n)\) 比特（Fano 不等式的直接应用）。因此期望查询数仍是 \(\Omega(n)\)。上界是平凡的：逐位查询 \(n\) 次。所以经典复杂度是 \(\Theta(n)\)——增强的提问方式对经典世界毫无帮助，因为答案永远只有一比特。

1.3 普通 oracle 下的量子线性壁垒¶

量子的情况则微妙得多。在标准位查询模型中，van Dam 的 oracle 审讯算法用 \(n/2+O(\sqrt n)\) 次查询学到 \(x\)（比经典的 \(n\) 省一半），而 Farhi 等人的奇偶下界与 Beals 等人的多项式方法共同确立了：有界错误地识别任意 \(x\) 需要 \(\Omega(n)\) 次位查询。两头夹逼，精确的复杂度是 \(n/2+\Theta(\sqrt n)\)——线性，不可再省。

壁垒的根源在于位查询的"局部性"：一次查询只触及一个位置，而量子查询能从一个位置上榨出的关于整个串的信息被下界定死了。通配符查询打破的正是这个局部性：它的答案 \(1[x_S=y]\) 是一个关于整段串的全局谓词，于是量子算法可以把"一整段候选串"放进叠加里，让相位反冲携带全局的匹配信息。本章的模式匹配一课讨论的子串查询模型（" \(y\) 是否为 \(x\) 的连续子串"）是同一思路的另一个变体，Cleve 等人对它给出了 \(3n/4+o(n)\) 的量子算法。

2. 直觉：整段验证便宜，好的猜测靠量子冗余¶

在进入公式之前，先把算法"为什么对"讲清楚。它依赖两个互相配合的部件。

部件一：验证便宜，修错也便宜。 在通配符模型里，验证一个长度为 \(\ell\) 的整段猜测只要一次查询（\(S\) 取那 \(\ell\) 个位置，\(y\) 取猜测值）；在位查询模型里这要花 \(\ell\) 次。更进一步：如果验证发现猜测有错，定位一个错误位置也只要 \(O(\log n)\) 次——对候选位置区间做二分，每次查询"错误是否藏在前半段"（即查询前半段子集上的整段相等性），\(\lceil\log_2 n\rceil\) 次即可收敛到一个 mismatch 位置，把那一位翻转即可修掉一个错误。于是一个很自然的算法骨架浮现出来：大胆地猜，便宜地验证，便宜地修错。

部件二：好的猜测从哪里来。 骨架里唯一缺的是"猜测"。朴素地猜当然不行——随机猜一个 \(n\) 位串，全对的概率是 \(2^{-n}\)。这里量子性提供了决定性的帮助。考虑把"已知 \(x\) 的一个 \(k\) 位子集视图"量子化为态

\[ |\psi_x^k\rangle=\frac1{\sqrt{\binom nk}}\sum_{S\subseteq[n],\,|S|=k}|S\rangle|x_S\rangle, \]

即所有"缺 \(n-k\) 位"的视图的均匀叠加。关键在于这个叠加是相干的：同一个位置 \(i\) 出现在大量分支 \(S\ni i\) 中，且各分支中 \(x_i\) 的振幅相位一致。这些相干重叠编码了强烈的全局冗余——第 3 节将证明，当缺失的位数是 \(O(\sqrt n)\) 时，存在一个测量（PGM），其输出 \(\widetilde x\) 与真值 \(x\) 的期望汉明距离只有 \(O(1)\)。与之对照，经典世界里拿任何一个固定的 \(n-O(\sqrt n)\) 位视图，剩下 \(O(\sqrt n)\) 位完全是纯熵：猜对它们的概率是 \(2^{-O(\sqrt n)}\)，指数级小。量子把"缺失位置也处于叠加"这一事实变成了可测量的信息。

为什么恰好是 \(\sqrt n\)？ 两个方向的力量平衡在这里。缺失位数 \(m=n-k\) 越大，视图之间的正交性越差、判别越难（第 3.4 节的谱分析会把这一点定量化：谱的"分辨率尺度"是 \(n/m\)，取 \(m=c\sqrt n\) 恰好让单比特错误率降到 \(O(1/n)\)，从而 \(n\) 位合计错误 \(O(1)\)）；缺失位数越小，一轮能学到的新位就越少。所以每轮把已知规模从 \(k\) 推到 \(k+\Theta(\sqrt k)\) 是甜点位置——这就是标题的来历。

算术骨架（第 4、5 节将严格化）：从规模 \(n_0=O(\sqrt n)\) 出发，每轮增长 \(\Theta(\sqrt{\text{当前规模}})\)，需要 \(L=O(\sqrt n)\) 轮走完 \(n\)；每轮的查询数是"一次验证 \(+\) 期望 \(O(1)\) 个错误 \(\times\) 每个 \(O(\log n)\) 次二分" \(=O(\log n)\)。总计

\[ \underbrace{O(\sqrt n)}_{\text{第 0 阶段抄写}}+\underbrace{O(\sqrt n)}_{\text{轮数}}\times\underbrace{O(\log n)}_{\text{每轮验证与修错}}=O(\sqrt n\log n). \]

与下界 \(\Omega(\sqrt n)\)（第 5.2 节）相比只差一个对数因子，这个因子正是"修错二分"的代价。

最后强调一次方法论：本算法的加速不经过振幅放大或量子行走。它的可迁移经验是——当 oracle 允许"整段验证"类查询时，应当问"什么样的量子态能让一个近似的整串猜测变得便宜"，也就是把查询问题转化为状态判别问题。

3. 核心状态判别问题¶

3.1 子集态¶

对 \(0\le k\le n\) 与每个 \(x\in\{0,1\}^n\)，定义子集态 (subset state)

\[ |\psi_x^k\rangle:=\frac1{\sqrt{\binom nk}}\sum_{S\subseteq[n],\,|S|=k}|S\rangle|x_S\rangle, \qquad |x_S\rangle:=\bigotimes_{i\in S}|x_i\rangle, \]

第一个寄存器存子集（\(S\) 中位置按升序编号），第二个寄存器存对应的值。直观地说，\(|\psi_x^k\rangle\) 是"随机扔掉 \(n-k\) 位之后还能看见的 \(x\)"的量子版本：扔掉哪 \(n-k\) 位处于均匀叠加，而没有扔掉的每一位都带着正确的值出现在所有包含它的分支里。

第 4 节的算法将维护一串不断增大的子集态 \(|\psi_x^{n_0}\rangle,\dots,|\psi_x^{n}\rangle\)，并在每一轮用下面的判别引理从 \(|\psi_x^{n_s}\rangle\) 附近的态"猜出"更多的位。注意当 \(k=n\) 时只有一个子集 \(S=[n]\)，故 \(|\psi_x^n\rangle=|[n]\rangle|x\rangle\)——终态的第二个寄存器就是答案本身。

3.2 Gram 矩阵只依赖汉明距离¶

态集合 \(\{|\psi_x^k\rangle\}_x\) 共有 \(2^n\) 个元素，要判别它们，第一步永远是计算两两内积。

Lemma 1. 对任意 \(x,y\in\{0,1\}^n\)，

\[ \langle\psi_x^k|\psi_y^k\rangle=\frac{\binom{n-d(x,y)}{k}}{\binom nk}. \]

证明。按定义展开：

\[ \langle\psi_x^k|\psi_y^k\rangle =\frac1{\binom nk}\sum_{S,S',\,|S|=|S'|=k}\langle S|S'\rangle\,\langle x_S|y_{S'}\rangle. \]

计算基矢正交给出 \(\langle S|S'\rangle=\delta_{S,S'}\)，于是双重求和坍缩成单重：

\[ \langle\psi_x^k|\psi_y^k\rangle =\frac1{\binom nk}\sum_{|S|=k}\langle x_S|y_S\rangle =\frac1{\binom nk}\sum_{|S|=k}\prod_{i\in S}\langle x_i|y_i\rangle. \]

单个因子 \(\langle x_i|y_i\rangle\) 等于 \(1\)（若 \(x_i=y_i\)）或 \(0\)（若 \(x_i\ne y_i\)，此时 \(|x_i\rangle,|y_i\rangle\) 是正交的计算基矢）。因此整串内积非零当且仅当 \(S\) 完全避开 \(x,y\) 的全部差异位置。记差异位置集为 \(D:=\{i:x_i\ne y_i\}\)，\(|D|=d(x,y)\)，则满足条件的 \(S\) 是从 \([n]\smallsetminus D\)（共 \(n-d(x,y)\) 个位置）中选 \(k\) 个，共有 \(\binom{n-d(x,y)}{k}\) 种，且每一种贡献 \(1\)。代入即得结论。Q.E.D.

三个直接推论，后文都要用到：

内积只依赖 \(d(x,y)\)（而不依赖 \(x,y\) 本身），这是全部对称性分析的起点。
取 \(k=n\)：\(\langle\psi_x^n|\psi_y^n\rangle=\binom{n-d}{n}/\binom nn=[d=0]\)，即 \(k=n\) 时态两两正交（练习 4 第 2 题会再从组合角度验证）。
记缺失位数 \(m:=n-k\)。当 \(d\le n-k\) 时可以把比值写成连乘：

\[ \frac{\binom{n-d}{k}}{\binom nk} =\frac{(n-d)!\,(n-k)!}{n!\,(n-d-k)!} =\prod_{j=0}^{d-1}\frac{n-k-j}{n-j} \approx\Bigl(1-\frac mn\Bigr)^{d}\approx e^{-md/n}, \]

其中最后两步对 \(d\ll n\)、\(m\ll n\) 使用了 \(\prod_j(1-\frac{m}{n-j})\approx(1-\frac mn)^d\) 与 \((1-\frac mn)^d\approx e^{-md/n}\)（每步都是 \(1-t\approx e^{-t}\) 的标准近似）。这条近似告诉我们一件重要的事：当 \(m=c\sqrt n\) 时，汉明距离为 \(1\) 的两个态的内积约为 \(1-c/\sqrt n\)，几乎平行。精确识别 \(x\) 在原理上不可能——态本身几乎不区分邻居。所以本文的目标从一开始就不是"以高概率精确输出 \(x\)"，而是"期望只错 \(O(1)\) 位"。这个放低的标准恰好够用，因为第 2 节说过：每位错误只需 \(O(\log n)\) 次查询就能修掉。

3.3 \(\mathbb Z_2^n\)-Fourier 对角化¶

判别一组态的最优测量由 Gram 矩阵决定。把 Gram 矩阵看作 \(2^n\times 2^n\) 的算子 \(G\)，其 \((x,y)\) 元是 \(f(x\oplus y)\)，其中

\[ f(w):=\frac{\binom{n-|w|}{k}}{\binom nk}. \]

（由 Lemma 1，\(G_{xy}=\langle\psi_x^k|\psi_y^k\rangle\) 只依赖 \(x\oplus y\)。）这种"只依赖差值"的矩阵是群 \(\mathbb Z_2^n\) 上的卷积矩阵，而卷积矩阵被特征标对角化——这正是量子傅里叶变换中的老朋友：对每个 \(z\in\{0,1\}^n\)，特征标 \(\chi_z(y):=(-1)^{z\cdot y}\)。

Lemma 2. 每个 \(\chi_z\) 都是 \(G\) 的特征向量，特征值

\[ \lambda(z)=\sum_{w\in\{0,1\}^n}(-1)^{z\cdot w}\,f(w) =2^{\,n-k}\,\frac{\binom{n-|z|}{\,n-k\,}}{\binom nk}. \]

（按标准约定，下指标超出范围的二项式系数取 \(0\)，故 \(|z|>k\) 时 \(\lambda(z)=0\)。）

证明。分两步。

第一步（特征向量性质）。把 \(w=x\oplus y\) 代换：

\[ (G\chi_z)(x)=\sum_y f(x\oplus y)\,(-1)^{z\cdot y} =(-1)^{z\cdot x}\sum_w f(w)\,(-1)^{z\cdot w}=\lambda(z)\,\chi_z(x), \]

其中第二个等号用了 \(z\cdot(x\oplus w)=z\cdot x+z\cdot w\)（在 \(\mathbb Z_2\) 上加法就是异或）以及代换 \(y=x\oplus w\) 是双射。这一步同时给出了特征值的表达式 \(\lambda(z)=\sum_w(-1)^{z\cdot w}f(w)\)，剩下的任务是算出闭式。（记号提醒：\(f\) 是 Gram 核函数；第 3.6 节的 \(g\) 是 PGM 输出分布、\(h\) 是重量函数，三者请勿混淆。）

第二步（闭式的组合推导）。核心是把二项式系数改写成计数：

\[ \binom{n-|w|}{k}=\#\{S\subseteq[n]:|S|=k,\ S\cap\operatorname{supp}(w)=\varnothing\}, \]

即从 \(w\) 的 \(n-|w|\) 个零位置里选 \(k\) 个。代入并与对 \(w\) 的求和交换次序：

\[ \sum_w(-1)^{z\cdot w}\binom{n-|w|}{k} =\sum_{|S|=k}\ \sum_{w:\,\operatorname{supp}(w)\cap S=\varnothing}(-1)^{z\cdot w}. \]

内层对 \(w\) 的求和中，\(w\) 只在 \(\bar S:=[n]\smallsetminus S\) 上自由取值，于是按位置分解成乘积：

\[ \sum_{w\subseteq\bar S}(-1)^{z\cdot w}=\prod_{i\in\bar S}\bigl(1+(-1)^{z_i}\bigr). \]

若某个 \(i\in\bar S\) 满足 \(z_i=1\)，因子为 \(0\)，整项消失；故内层和非零当且仅当 \(\operatorname{supp}(z)\subseteq S\)，此时每个因子都是 \(2\)，内层和为 \(2^{n-k}\)。因此

\[ \sum_w(-1)^{z\cdot w}\binom{n-|w|}{k} =2^{\,n-k}\cdot\#\{S:|S|=k,\ \operatorname{supp}(z)\subseteq S\} =2^{\,n-k}\binom{n-|z|}{k-|z|}. \]

最后 \(\binom{n-|z|}{k-|z|}=\binom{n-|z|}{(n-|z|)-(k-|z|)}=\binom{n-|z|}{n-k}\)，除以 \(\binom nk\) 即得闭式。Q.E.D.

校验。两条独立验算可以确认闭式无误：

迹：\(\sum_z\lambda(z)=\operatorname{Tr}G=2^n\)（对角元全是 \(1\)）。用恒等式 \(\binom nt\binom{n-t}{m}=\binom nm\binom{n-m}{t-m}\)（先选 \(M\) 再选不相交的 \(T\)，与先选 \(T\) 再在余下选 \(M\)，数的是同一个集合对）与 \(\sum_t\binom{n-m}{t-m}=2^{n-m}\)，取 \(m=n-k\)：

\[ \sum_{t}\binom nt\,2^{\,n-k}\frac{\binom{n-t}{n-k}}{\binom nk} =2^{\,n-k}\,\frac{\binom{n}{n-k}2^{k}}{\binom nk}=2^n, \]

与所要验证的迹一致。

小例子（\(n=2,k=1\)）。此时 \(f(0)=1,\ f(1)=\tfrac12,\ f(2)=0\)，故

\[\begin{split} G=\begin{pmatrix}1&\tfrac12&\tfrac12&0\\ \tfrac12&1&0&\tfrac12\\ \tfrac12&0&1&\tfrac12\\ 0&\tfrac12&\tfrac12&1\end{pmatrix} \end{split}\]

（行、列按 \(00,01,10,11\) 排列）。闭式给出 \(\lambda(0)=2^1\binom21\binom21^{-1}=2\)，\(\lambda(1)=2\binom11\binom21^{-1}=1\)（重数 \(2\)），\(\lambda(2)=0\)。直接验证：\((1,1,1,1)^T\) 的特征值是 \(2\)，\((1,1,-1,-1)^T\) 与 \((1,-1,1,-1)^T\) 的特征值是 \(1\)，\((1,-1,-1,1)^T\) 的特征值是 \(0\)。\(\{2,1,1,0\}\) 与闭式完全一致。

顺带把第 3.6 节要用的一条标准事实记在这里：任何只依赖 \(x\oplus y\) 的矩阵 \(A\) 若以 \(\{\mu(z)\}\) 为特征值，则其矩阵元可由特征值反解：

\[ A_{xy}=2^{-n}\sum_z\mu(z)\,(-1)^{z\cdot(x\oplus y)}, \]

这是因为归一化特征向量 \(2^{-n/2}\chi_z\) 构成 \(\mathbb R^{2^n}\) 的正交基，谱分解 \(A=\sum_z\mu(z)|\chi_z\rangle\langle\chi_z|/2^n\) 逐元写出就是上式。

3.4 谱的形状与参数窗口¶

把特征值按重量写成 \(\lambda(t)=2^m\binom{n-t}{m}\big/\binom nm\)（\(m=n-k\)，用了 \(\binom{n-t}{n-k}=\binom{n-t}{m}\) 的对称性）。两个极端先对齐直觉：

\(m=0\)（\(k=n\)）：\(\lambda(t)\equiv1\)，\(G=I\)，态两两正交——完美判别。
\(k=0\)：所有态相同，\(G\) 是全 \(1\) 矩阵，\(\lambda(z)=2^n\delta_{z,0}\)——完全不可判别。

中间情形的形状：当 \(t\ll n\) 时，

\[ \frac{\lambda(t)}{2^m}=\frac{\binom{n-t}{m}}{\binom nm} =\prod_{j=0}^{t-1}\frac{n-j-m}{n-j} \approx\Bigl(1-\frac mn\Bigr)^{t}\le e^{-mt/n}. \]

也就是说，特征值在重量轴上以尺度 \(n/m\) 衰减。用通俗的话说：Gram 矩阵的谱质量集中在"低重量的特征标方向"上，态与态之间真正"看得见"的差异只延伸到汉明重量约 \(n/m\) 的范围；比这更远的方向上谱接近零，测量原则上分辨不了。

取 \(m=c\sqrt n\)，分辨率尺度就是 \(\sqrt n/c\)。论文的附录 A 把这个窗口的两端定量地钉死了（以"精确识别概率" \((\sqrt G_{xx})^2\) 为度量，第 3.5 节将说明它正是 PGM 恰好猜中 \(x\) 的概率）：缺 \(a\sqrt n\) 位（\(0\le a\le1\)）时 \((\sqrt G_{xx})^2\ge1-2a^2-O(1/\sqrt n)\)，而缺 \(a\sqrt n\) 位（\(a\) 偏大）时 \((\sqrt G_{xx})^2\le4e^{-a^2/32}\)。\(\sqrt n\) 正是"从几乎完美到指数变差"的过渡尺度——这解释了第 2 节的断言：每轮只应放进去 \(\Theta(\sqrt{\text{规模}})\) 个新位。

3.5 Pretty Good Measurement¶

态不正交时不存在同时区分它们的投影测量；最优的策略是一个 POVM。本文用的是Pretty-Good Measurement（PGM，也叫平方根测量）。按论文的约定取未加权的和（这样公式最干净；它就是均匀先验下密度矩阵的 \(2^n\) 倍）：

\[ \rho:=\sum_x|\psi_x^k\rangle\langle\psi_x^k|,\qquad M_x:=\rho^{-1/2}\,|\psi_x^k\rangle\langle\psi_x^k|\,\rho^{-1/2}, \]

逆取在 \(\rho\) 的支撑上（所有态都落在支撑内）。名字里的"pretty good"是一种自嘲式的准确：它未必最优，但构造简单、只依赖系综的一阶统计量，且在很多对称系综上恰好最优（本系综正是如此，见第 3.6 节评注）。

合法性：每个 \(M_x\) 显然半正定，且

\[ \sum_x M_x=\rho^{-1/2}\Bigl(\sum_x|\psi_x^k\rangle\langle\psi_x^k|\Bigr)\rho^{-1/2}=\rho^{-1/2}\,\rho\,\rho^{-1/2}=I. \]

输出概率由 \(\sqrt G\) 给出。定义矩阵 \(A_{yx}:=\langle\psi_y^k|\rho^{-1/2}|\psi_x^k\rangle\)，则

\[ \Pr[\text{输出 }y\mid\text{输入 }x]=\langle\psi_x^k|M_y|\psi_x^k\rangle=|A_{yx}|^2=(\sqrt G_{yx})^2. \]

推导分三步。第一步，把 \(M_y\) 的定义代入并展开成配对：

\[ \langle\psi_x^k|M_y|\psi_x^k\rangle =\langle\psi_x^k|\rho^{-1/2}|\psi_y^k\rangle\,\langle\psi_y^k|\rho^{-1/2}|\psi_x^k\rangle=|A_{yx}|^2. \]

第二步，证 \(A^2=G\)。按矩阵乘法把中间对 \(y\) 的求和收拢（注意中间不插入任何权重）：

\[ (A^2)_{xz}=\sum_y\langle\psi_x^k|\rho^{-1/2}|\psi_y^k\rangle\,\langle\psi_y^k|\rho^{-1/2}|\psi_z^k\rangle =\langle\psi_x^k|\rho^{-1/2}\,\rho\,\rho^{-1/2}|\psi_z^k\rangle=G_{xz}, \]

其中收拢一步用了 \(\sum_y|\psi_y^k\rangle\langle\psi_y^k|=\rho\)，最后一步用了 \(\rho^{-1/2}\rho\rho^{-1/2}\) 在支撑上等于恒等。第三步，\(A\) 半正定：对任意系数 \(c\)，令 \(|\varphi\rangle:=\sum_xc_x|\psi_x^k\rangle\)（必落在支撑内），则

\[ \sum_{x,y}\overline{c_y}\,A_{yx}\,c_x =\sum_{x,y}\overline{c_y}\,\langle\psi_y^k|\rho^{-1/2}|\psi_x^k\rangle\,c_x =\langle\varphi|\rho^{-1/2}|\varphi\rangle\ \ge\ 0, \]

因为 \(\rho^{-1/2}\) 在支撑上的特征值非负（顺带一提，\(\rho=\sum_x|\psi_x^k\rangle\langle\psi_x^k|\) 与标签空间上的 \(G=\sum_{x,y}G_{xy}|x\rangle\langle y|\) 互为转置伴随，故二者有相同的非零特征值，即 \(\lambda(z)\)）。半正定平方根唯一，故 \(A=\sqrt G\)。Q.E.D.

这条公式把"测量的输出分布"完全化成了 Gram 矩阵的函数，而 \(G\) 已被第 3.3 节对角化——所以 PGM 的全部性能都可以从特征值 \(\{\lambda(z)\}\) 读出。特别地，用第 3.3 节末尾的反解公式（取 \(A=\sqrt G\)，\(\mu(z)=\sqrt{\lambda(z)}\)）：

\[ \sqrt G_{xy}=2^{-n}\sum_z\sqrt{\lambda(z)}\,(-1)^{z\cdot(x\oplus y)}. \]

3.6 主引理：期望 \(O(1)\) 个错误¶

现在陈述全文的技术心脏。

Lemma 3（Ambainis–Montanaro）. 对任意 \(k=n-O(\sqrt n)\)，存在一个测量（PGM），在输入 \(|\psi_x^k\rangle\) 时输出 \(\widetilde x\in\{0,1\}^n\)，满足

\[ \mathbb E\bigl[d(x,\widetilde x)\bigr]=O(1), \]

期望对测量的内禀随机性取，且界对每个 \(x\) 一致成立。

证明骨架。完整证明的每一步都展示如下，其中一处二项式系数的细致估计我们标注为"论文估计"并说明其思想。

Step A（对称性归一）。由 \(\sqrt G_{xy}\) 只依赖 \(x\oplus y\)（第 3.5 节末公式），输出分布 \(\Pr[\widetilde x=y\mid x]\) 只依赖 \(x\oplus y\)。于是期望错误数 \(D_k:=\mathbb E[d(x,\widetilde x)]\) 与 \(x\) 无关，不妨设 \(x=0^n\)，记输出分布为

\[ g(y):=(\sqrt G_{0y})^2,\qquad \sum_y g(y)=1. \]

（归一化正是 \(\sum_y\Pr[\widetilde x=y\mid0]=1\)。）

Step B（错误数 = 单比特偏差之和）。错误位数可以按位拆开：

\[ D_k=\sum_y|y|\,g(y)=\sum_{i=1}^n\Pr[\widetilde x_i=1] =\sum_{i=1}^n\frac{1-\mathbb E[(-1)^{\widetilde x_i}]}{2}. \]

对 \(h:\{0,1\}^n\to\mathbb R\) 定义 Fourier 系数 \(\widehat h(z):=2^{-n}\sum_y(-1)^{z\cdot y}h(y)\)，则 \(\mathbb E[(-1)^{\widetilde x_i}]=\sum_yg(y)(-1)^{y_i}=2^n\widehat g(e_i)\)。又由对称性（坐标 \(i\) 之间可互换），诸 \(\widehat g(e_i)\) 相等，故

\[ D_k=\frac n2\Bigl(1-2^n\widehat g(e_1)\Bigr). \]

也可以绕道 Plancherel 得到同一式：把 \(D_k\) 看作重量函数 \(h(y):=|y|\) 与 \(g(y)\) 的内积，用展开 \(h(y)=\sum_z\widehat h(z)(-1)^{z\cdot y}\)（该展开成立是因为 \(\sum_z(-1)^{z\cdot(y\oplus t)}=2^n[y=t]\)）逐项乘开，得 \(D_k=2^n\sum_z\widehat h(z)\widehat g(z)\)；再直接计算 \(\widehat h\)：把 \(y\) 与 \(y\oplus e_i\) 配对可算出

\[ \widehat h(0^n)=\frac n2,\qquad \widehat h(e_i)=-\frac12,\qquad \widehat h(z)=0\ (|z|\ge2), \]

（\(\widehat h\) 在 \(|z|\ge2\) 为零的原因：把 \(y\) 与 \(y\oplus e_j\)（\(j\in\operatorname{supp}(z)\) 任取一位）配对，两项 \(|y|\) 与 \(|y\oplus e_j|\) 之和中的线性部分相消——具体地 \(\sum_y(-1)^{z\cdot y}|y|=0\)，练习 6 第 2 题要求补全）。代回并注意 \(\widehat g(0)=2^{-n}\)，同样得到 \(D_k=\frac n2(1-2^n\widehat g(e_1))\)。

于是引理等价于证明：PGM 输出的每一个比特，其错误概率只有 \(O(1/n)\)。\(n\) 位合计起来才是 \(O(1)\)——这就是"期望 \(O(1)\) 个错误"的真正含义。

Step C（用特征值表达 \(\widehat g(e_1)\)）。Fourier 变换把逐点乘积变成卷积：若 \(u(y)v(y)=g(y)\)，则 \(\widehat g(z)=\sum_{a\oplus b=z}\widehat u(a)\widehat v(b)\)（把 \(u,v\) 各自按特征标展开相乘、合并同类项即得）。取 \(u(y)=v(y):=\sqrt G_{0y}\)（注意这是带符号的函数，第 7.4 节会看到 \(\sqrt G_{11}<0\) 的例子），其 Fourier 系数由第 3.5 节末公式给出：\(\widehat u(z)=2^{-n}\sqrt{\lambda(z)}\)。故

\[ 2^n\widehat g(e_1) =2^n\sum_a\widehat u(a)\,\widehat u(a\oplus e_1) =2^{-n}\sum_{a\in\{0,1\}^n}\sqrt{\lambda(a)\,\lambda(a\oplus e_1)}. \]

Step D（论文估计）。剩下的任务是证明上式 \(\ge1-O(1/n)\)（即每个输出比特几乎无偏）。把 \(a\) 按重量 \(t=|a|\) 分层。由于 \(\sqrt{\lambda(a)\lambda(a\oplus e_1)}\) 在层内只依赖 \(t\)（特征值只依赖重量），上式是各层贡献的加权和，权重是二项式系数。关键观察有三条：

质量集中在中间层。权重 \(\binom nt\) 集中在 \(t=n/2\pm O(\sqrt n)\)，尾部指数小（Chernoff 界）。
相邻层的特征值几乎相等。由闭式，\(\lambda(t)/\lambda(t+1)=\binom{n-t}{m}\big/\binom{n-t-1}{m}=\frac{n-t}{n-t-m}\)，在 \(t\approx n/2\)、\(m=c\sqrt n\) 时等于 \(1+\frac{m}{n/2-m}=1+O(1/\sqrt n)\)——几何平均 \(\sqrt{\lambda(a)\lambda(a\oplus e_1)}\) 与 \(\lambda(a)\) 本身几乎一样。
凹函数下界。论文对每一层的主项使用初等不等式

\[ \sqrt x\ \ge\ \frac32x-\frac12x^2\qquad(x\ge0), \]

（证明：令 \(u=\sqrt x\ge0\)，则 \(\sqrt x-\frac32x+\frac12x^2=\frac12\,u(u-1)^2(u+2)\ge0\)，因式分解展开即可验证）把根号展开成幂次，逐层估出主项 \(T_t\ge1-O(1/n)\)，其中 \(O(1/n)\) 对 \(t=n/2+a\sqrt n\)、常数范围的 \(a,c\) 一致。

三层合起来给出 \(2^n\widehat g(e_1)\ge1-O(1/n)\)，代回 Step B：

\[ D_k=\frac n2\cdot O(1/n)=O(1). \]

Q.E.D.

评注（诚实声明）。Step D 中"逐层展开并把余项加总"涉及对二项式系数与 Krawtchouk 型和的细致控制，本教程只展示了结构与关键不等式；完整的逐项估计见论文第 3 节（其附录 A 还包含精确识别概率的上下界，即第 3.4 节引用的两条）。此外论文还借助 Eldar–Forney 的定理说明：这组态在阿贝尔群 \(\{U_z\}\)（\(U_z|S\rangle|w\rangle=|S\rangle|w\oplus z_S\rangle\)，满足 \(U_z|\psi_0^k\rangle=|\psi_z^k\rangle\)，见练习 6 第 2 题）下几何均匀 (geometrically uniform)，而几何均匀系综上 PGM 恰好是最小化平均错误率的最优测量。所以"换一个更好的测量"在此没有收益——\(O(1)\) 不是算法的懒散，是这个态集合的本质属性。

3.7 一个对照：经典视图 vs 量子子集态¶

把第 2 节的口号落实成数字。固定缺失 \(m=c\sqrt n\) 位，比较两条路线：

经典：拿到任意一个固定的 \(n-\sqrt n\) 位视图后，剩余 \(\sqrt n\) 位是纯熵，全部猜对的概率只有 \(2^{-\Theta(\sqrt n)}\)；
量子：从子集态 \(|\psi_x^k\rangle\) 出发做一次 PGM，期望只错 \(O(1)\) 位，整串恰好猜对的概率为常数——而且残余的错误位每个只需 \(O(\log n)\) 次查询就能定位并修复。

量子优势的来源不是"读得更快"，而是缺失位置之间的相干重叠使整串信息过定 (overdetermined)：同一个 \(x_i\) 在 \(\binom{n-1}{k-1}\) 个分支中以一致相位出现，测量提取的是全局一致性，而不是逐位采样。

4. 阶梯生长算法¶

4.1 蓝图与阶段序列¶

算法维护一列规模递增的子集态。取阶段序列 \(n_0<n_1<\cdots<n_L=n\)，满足递推

\[ n_{s-1}=\bigl\lceil n_s-\sqrt{n_s}\bigr\rceil\quad(1\le s\le L), \qquad n_0=O(\sqrt n), \]

即自顶向下地从 \(n\) 每次砍掉约 \(\sqrt{(\cdot)}\)。第 \(s\) 阶段把 \(|\psi_x^{n_{s-1}}\rangle\) 升级成 \(|\psi_x^{n_s}\rangle\)；由 \(n_L=n\) 与 \(|\psi_x^n\rangle=|[n]\rangle|x\rangle\)，最终测量第二个寄存器即得 \(x\)。

阶段数 \(L=O(\sqrt n)\) 的推导。把递推 \(n_{s-1}\approx n_s-\sqrt{n_s}\) 与常微分方程 \(\frac{dn}{ds}=-\sqrt n\) 比较：由链式法则 \(\frac{d}{ds}\sqrt{n}=\frac{1}{2\sqrt n}\cdot(-\sqrt n)=-\frac12\)，即 \(\sqrt n\) 关于 \(s\) 以斜率 \(-\frac12\) 线性下降，从 \(\sqrt n\) 降到 \(\sqrt{n_0}=O(n^{1/4})\) 需要

\[ L\approx2\bigl(\sqrt n-\sqrt{n_0}\bigr)=\Theta(\sqrt n) \]

步；离散递推与 ODE 的误差在每步 \(O(1)\)，累计 \(O(\sqrt n)\) 不改变阶。第 7.3 节会用 \(n=100\) 的数值验证（一路降到 \(1\) 共 \(18\) 步，对照 ODE 估计 \(2(\sqrt{100}-\sqrt{1})=18\)）。

为什么不一步到位、直接制备 \(|\psi_x^{\,n-c\sqrt n}\rangle\) 然后做一次 PGM？因为制备本身就需要知道 \(x\)：oracle 只做验证、不报数值，把 \(n-c\sqrt n\) 个位置的值写进寄存器仍然要逐位抄写，一次 PGM 省不掉这个成本。阶梯的意义在于让 PGM 的"猜测"替代"抄写"：每一轮只需第 0 阶段那样抄 \(\sqrt{(\cdot)}\) 位（而且只在最初做一次），之后的增长全部由"猜 + 验 + 修"驱动。

4.2 第 0 阶段：直接抄写 \(\sqrt n\) 位¶

制备初态 \(|\psi_x^{n_0}\rangle\)：

制备均匀叠加 \(\sum_{|S|=n_0}|S\rangle\)，并为值准备 \(n_0\) 个槽位（第 \(j\) 槽对应 \(S\) 的第 \(j\) 小元素，纯组合计算，无需 oracle）。
对每个 \(j\in[n_0]\)，做一次单点通配符查询：查询 \((\{i_j\},0)\)，其中 \(i_j\) 是从寄存器 \(S\) 中相干算出的第 \(j\) 小元素。答案比特为 \(1-x_{i_j}\)，翻转一次即得 \(x_{i_j}\)，写入第 \(j\) 槽。

要点是：查询寄存器处于叠加态，所以一次查询同时为所有 \(\binom{n}{n_0}\) 个分支写好了第 \(j\) 槽（第 1.1 节的物理基础）。\(n_0\) 个槽共耗 \(n_0=O(\sqrt n)\) 次查询，得到

\[ |\psi_x^{n_0}\rangle=\frac1{\sqrt{\binom n{n_0}}}\sum_{|S|=n_0}|S\rangle|x_S\rangle. \]

4.3 扩张阶段的五个步骤¶

设第 \(s\) 阶段输入为 \(|\psi_x^{n_{s-1}}\rangle\)。回顾参数关系：\(n_s-n_{s-1}=\lceil\sqrt{n_s}\rceil\)，即每个分支内"缺失"的位数恰好落在 Lemma 3 的窗口里。

步骤 1（相干嵌入，零查询）。把每个 \(n_{s-1}\) 子集分支"浸泡"进它的所有 \(n_s\) 元超集：

\[ |\psi_x^{n_{s-1}}\rangle\ \longmapsto\ \sum_{S\subseteq[n],\,|S|=n_s}|S\rangle\,|\psi_{x_S}^{n_{s-1}}\rangle, \]

（外层省略归一化因子 \(1/\sqrt{\binom n{n_s}}\)；内层 \(|\psi_{x_S}^{n_{s-1}}\rangle=\binom{n_s}{n_{s-1}}^{-1/2}\sum_{T\subset S,|T|=n_{s-1}}|T\rangle|x_T\rangle\) 是以 \(S\) 为全集的子集态。）为什么零查询？因为这步只是对已在寄存器里的旧值做重组：从分支 \(T\) 出发，均匀叠加它的超集 \(S\supseteq T\)（从 \([n]\smallsetminus T\) 中再选 \(n_s-n_{s-1}\) 个元素，纯组合操作），然后把值寄存器原样带入。新的 \(n_s-n_{s-1}\) 个位置的值尚不在态里——它们正是 PGM 即将预测的对象。

步骤 2（分支内 PGM）。对每个分支 \(S\) 的寄存器执行同一个酉变换 \(U_{n_s,n_{s-1}}\)：即"参数为（全集大小 \(n_s\)、子集大小 \(n_{s-1}=n_s-O(\sqrt{n_s})\)）的 PGM 的酉部分"，把分支态映到"输出寄存器 \(\mathcal H_o\) 持有整串猜测 \(\widetilde{x_S}\in\{0,1\}^{n_s}\)、其余放垃圾 \(\mathcal H_g\)"的形态。按 Lemma 3（把其中的 \(n\) 换成 \(n_s\)），每个分支的猜测期望只有 \(O(1)\) 个错误位。注意这里不测量输出寄存器——猜测以叠加的形式保留，测量被推迟到验证标志上。

步骤 3（一次查询验证整段）。对叠加里的每个分支，用一次通配符查询计算

\[ Q_x\bigl(S,\widetilde{x_S}\bigr)=1[\widetilde{x_S}=x_S] \]

到标志比特，然后测量标志。若读到 \(1\)：所有存活分支的猜测都整段正确，态形如 \(\sum_{|S|=n_s}|S\rangle|x_S\rangle_{\mathcal H_o}|\varphi_S\rangle_{\mathcal H_g}\)——输出寄存器已经持有每个分支的正确值，正是我们要的形状，跳到步骤 5。

步骤 4（相干二分修错）。若标志读到 \(0\)：对每个仍错的分支（猜测与 \(x_S\) 至少差一位），用 \(\lceil\log_2 n_s\rceil\) 次子段查询相干地（不测量）定位一个错误位置：查询"候选区间的前半段上猜测是否全对"，答案 \(0\) 说明错误在前半段、\(1\) 说明在后半段（若前半全对则错误必在余下部分），逐次折半区间直至收敛到单个位置 \(i\)，翻转 \(\widetilde{x_S}\) 的第 \(i\) 位。随后再次整段验证并测量标志；若仍为 \(0\)，回到本步骤开头。由于期望错误位数是 \(O(1)\)，期望只需 \(O(1)\) 轮。

步骤 5（清除垃圾，零查询）。当标志最终读到 \(1\)，每个分支的输出寄存器持有经过验证的 \(x_S\)。此时分支的全部辅助内容都是 \((S,x_S)\) 的确定性函数：以正确值为输入，把步骤 1–4 的计算逆着执行一遍（uncomputation）即可把 \(\mathcal H_g\) 与所有搜索用的辅助比特还原为 \(|0\rangle\)。逆运算不消耗 oracle 查询，因为验证已经保证每一次用过的 oracle 答案都能从输出寄存器重新推出。丢弃辅助寄存器后得到

\[ |\psi_x^{n_s}\rangle=\frac1{\sqrt{\binom n{n_s}}}\sum_{|S|=n_s}|S\rangle|x_S\rangle. \]

4.4 每阶段代价、正确性与一个技术评注¶

查询记账。第 \(s\) 阶段（\(s\ge1\)）：步骤 3 花 \(1\) 次；步骤 4 每轮 \(\lceil\log_2 n_s\rceil\) 次、期望 \(O(1)\) 轮，合计期望 \(O(\log n)\)。总计每阶段期望

\[ 1+O(\log n)\cdot\mathbb E[D]=O(\log n), \]

其中 \(\mathbb E[D]=O(1)\) 正是 Lemma 3 的结论。

正确性。算法是 Las Vegas 式的：只要它停机，输出必然正确——终态是 \(|\psi_x^{n}\rangle=|[n]\rangle|x\rangle\)，测量第二个寄存器得到的就是 \(x\) 本身；而每一阶段留给下一阶段的寄存器内容都通过了整段验证 \(1[\widetilde{x_S}=x_S]\)，验证不通过的分支不会进入下一阶段。运行时间的随机性来自测量的内禀随机性（PGM 猜错几位、二分撞上哪个位置），与输入 \(x\) 无关，也不是假设 \(x\) 随机分布——这是论文对"平均 (on average)"一词的明确约定：期望针对最坏输入上的内部随机性。

评注（相干实现的细节）。有三处细节值得诚实标注，它们不影响复杂度阶，但严格的实现需要小心：

测量标志为什么安全。测量只施加在标志比特上；由系综的对称性，PGM 在各分支给出"正确猜测"的振幅是同一个常数（\(\sqrt G\) 的对角元与分支无关，见练习 6 第 2 题），所以读到 \(1\) 时存活分支的相对振幅没有被扭曲，态仍与目标态成比例。这是"只测标志、不测输出"的对称性保护。
修错循环的相干性。步骤 4 的二分必须对叠加中的所有错误分支同时执行（论文明确要求"coherently, without measurements"）；循环的终止判定依赖测量结果，严格实现时要把"修一轮"作为受控子程序反复调用并按期望时间记账。
跨阶段误差累积。若把全部操作做成严格相干的版本（连标志都不测），每阶段残留的"未修净"分支范数会沿 \(L=O(\sqrt n)\) 个阶段累积，需要相应的误差预算。论文按 Las Vegas/期望时间的口径处理这些细节，得到定理 1 的 \(O(\sqrt n\log n)\) 期望查询界。

4.5 从期望时间到最坏情形有界错误¶

期望复杂度可以按标准套路转成最坏情形有界错误：设某算法期望 \(q\) 次查询，把它截断在 \(cq\) 次（\(c\) 为常数）：由 Markov 不等式，超时概率 \(\le1/c\)，故一次运行以常数概率在预算内成功；超时就整体重来，重复 \(O(\log(1/\delta))\) 次把失败概率压到 \(\delta\)。代价是查询数乘上 \(O(1)\) 或 \(O(\log(1/\delta))\)——常数或对数放大，不改变 \(O(\sqrt n\log n)\) 的阶。

5. 总复杂度与下界¶

5.1 逐因子核算¶

总期望查询数是

\[ \underbrace{n_0}_{\text{第 0 阶段抄写}} +\sum_{s=1}^{L}\underbrace{\bigl(1+O(\log n)\bigr)}_{\text{验证}+\text{期望修错}} =O(\sqrt n)+O(\sqrt n)\cdot O(\log n)=O(\sqrt n\log n). \]

逐项解释每个因子的来源：

\(O(\sqrt n)\)（第 0 阶段）：初态规模 \(n_0=O(\sqrt n)\)，每个槽位一次单点查询。
\(O(\sqrt n)\)（轮数 \(L\)）：由递推 \(n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil\) 与 ODE 比较（第 4.1 节）。
\(O(\log n)\)（每轮）：\(1\) 次整段验证，加上期望 \(O(1)\) 个错误、每个 \(O(\log n)\) 次二分。
每轮增长 \(\Theta(\sqrt{n_s})\) 位的参数选择不是可调的优化自由度：它被 Lemma 3 的窗口（缺失位数必须是 \(O(\sqrt{\text{规模}})\)）双向夹死——跳得更大则 PGM 期望错误不再是 \(O(1)\)，修错成本反超收益。

5.2 量子下界 \(\Omega(\sqrt n)\)¶

定理（Zhang 的强加权对抗法，此处采用 Cleve 等与 Špalek–Szegedy 的表述）. 设要计算的函数 \(f\) 的输入 \(x\) 通过 oracle \(O_x|q\rangle|z\rangle=|q\rangle|z\oplus\zeta(x,q)\rangle\) 访问。给每对输出不同的输入 \((x,y)\) 赋对称权重 \(w(x,y)\ge0\)，给每个三元组 \((x,y,q)\) 赋权重 \(w'(x,y,q)\ge0\)，要求 \(w'(x,y,q)=0\) 只要 \(\zeta(x,q)=\zeta(y,q)\)，且对 \(\zeta(x,q)\ne\zeta(y,q)\) 的对满足 \(w'(x,y,q)\,w'(y,x,q)\ge w(x,y)^2\)。记 \(\mathrm{wt}(x)=\sum_yw(x,y)\)、\(v(x,q)=\sum_yw'(x,y,q)\)。则任何以概率 \(\ge2/3\) 计算 \(f\) 的量子算法需要

\[\begin{split} \Omega\Bigl(\min_{\substack{x,y,q:\,w(x,y)>0\\\zeta(x,q)\ne\zeta(y,q)}}\sqrt{\frac{\mathrm{wt}(x)\,\mathrm{wt}(y)}{v(x,q)\,v(y,q)}}\Bigr) \end{split}\]

次查询。

Lemma 6. 任何以最坏情形概率 \(2/3\) 解通配符搜索的量子算法需要 \(\Omega(\sqrt n)\) 次查询。

证明。对通配符搜索，输入集是全部 \(\{0,1\}^n\)，查询是 \(q=(S,y)\)，\(\zeta(x,q)=1[x_S=y]\)，且不同输入必须被区分（\(f(x)=x\)）。取权重方案：

\[ w(x,y)=1[d(x,y)=1],\qquad w'(x,y,q)=1[d(x,y)=1\ \text{且}\ \zeta(x,q)\ne\zeta(y,q)]. \]

合法性：\(w\) 对称且在 \(f(x)=f(y)\)（即 \(x=y\)）时为零；\(w'\) 在 \(\zeta\) 相等时为零；对 \(d(x,y)=1\) 且 \(\zeta\) 不同的对，\(w'(x,y,q)w'(y,x,q)=1\cdot1\ge1^2=w(x,y)^2\)。三条要求全部满足。

计算 \(\mathrm{wt}\)：每个 \(x\) 恰有 \(n\) 个汉明邻居，故 \(\mathrm{wt}(x)=n\)。

计算 \(v(x,q)\)：邻居形如 \(y=x\oplus e_i\)。分情况：

若 \(\zeta(x,q)=1\)（即 \(x_S=y\)）：翻转 \(S\) 外的位不改变答案；翻转 \(S\) 内任一位都会破坏整段相等。故 \(\zeta(x\oplus e_i,q)\ne\zeta(x,q)\) 当且仅当 \(i\in S\)，\(v(x,q)=|S|\)。
若 \(\zeta(x,q)=0\)：\(x_S\ne y\)，设二者在 \(S\) 内差 \(\delta\ge1\) 位。翻转第 \(i\) 位后恰好追平，当且仅当 \(\delta=1\) 且 \(i\) 是那个唯一差异位。故 \(v(x,q)=1\)（若 \(\delta=1\)）或 \(0\)（若 \(\delta\ge2\)）。

取任意满足 \(w(x,y)>0\) 且 \(\zeta(x,q)\ne\zeta(y,q)\) 的三元组：不妨 \(\zeta(x,q)=1\)、\(\zeta(y,q)=0\)，则 \(v(x,q)\le|S|\le n\)、\(v(y,q)\le1\)，于是

\[ \sqrt{\frac{\mathrm{wt}(x)\,\mathrm{wt}(y)}{v(x,q)\,v(y,q)}}\ \ge\ \sqrt{\frac{n\cdot n}{n\cdot1}}=\sqrt n, \]

代入定理得 \(\Omega(\sqrt n)\)。Q.E.D.

与 Grover 的直觉联系。这条下界可以这样"摸"出来：把候选输入限制为 \(n\) 个单 1 串 \(e_1,\dots,e_n\)（彼此汉明距离为 \(2\)，但每个都与 \(0^n\) 只差一位——"只在一个位置改变隐藏串"）。对这族输入，查询 \((S,0^{|S|})\) 的答案是"\(i\notin S\)"，取反即"\(i\in S\)"。于是区分这 \(n\) 个输入等价于：用"标记位置是否落在 \(S\) 内"的子集查询做无结构搜索，找那个唯一的标记位置——这正是 Grover 算法所面对的问题形态，平方根下界的直觉完全一致；上面的对抗法证明把这个直觉变成了定理。

5.3 近最优性¶

上界 \(O(\sqrt n\log n)\) 与下界 \(\Omega(\sqrt n)\) 之间的对数因子，来源已在上文标明：每轮 \(O(\log n)\) 的修错二分。论文没有消除这个差距；是否能把上界压到 \(O(\sqrt n)\)（或证明对数因子必要）是一个自然悬而未决的问题。就目前的知识，"近最优"是对这个算法最准确的评价。

6. 与普通 oracle 和组合群检测的对比¶

6.1 普通 bit oracle 模拟不了什么¶

逐条检查算法的每个用钱之处：

第 0 阶段的单点查询就是位查询，可以模拟。
步骤 3 的整段验证：用位查询模拟需要把 \(S\) 内每个位置都读一遍再比较——\(|S|\) 次查询，且不存在已知的相干捷径（位查询模型下识别整个串本来就需要 \(\Theta(n)\) 次，第 1.3 节）。
步骤 4 的二分：每一步都是一次子段整段验证，同上。

所以算法的全部优势都押在"一次查询验证一整段"这一语义上；练习 1 第 3 题要求把这一点量化。这也是把本教程放在"查询复杂度"一章的原因：模型的一步之差，把复杂度从 \(\Theta(n)\) 拉到 \(O(\sqrt n\log n)\)，而算法设计随之换了一个范式。

6.2 组合群检测：\(O(k\log k)\) 与 \(k=1\) 特例¶

组合群检测 (combinatorial group testing, CGT) 是通配符搜索的"孪生"问题：输入 \(x\in\{0,1\}^n\) 承诺汉明重量 \(|x|\le k\)（\(k\ll n\)），查询是

\[ Q_x(S)=\operatorname{OR}_{i\in S}x_i \]

（"\(S\) 里是否有坏元素"），目标是找出全部坏元素。它的历史可以追溯到 1943 年：Dorfman 为美军士兵的梅毒筛查设计混检方案（把多人血样混在一起一次检测），此后发展出庞大文献，应用于分子生物学、数据流、压缩感知与"带通配符的模式匹配"。经典复杂度是 \(\Theta(k\log(n/k))\)——下界来自信息论，上界来自二分。论文对它的量子结果是：

\[ \text{CGT：量子}\ O(k\log k)\ \text{次查询（期望），下界}\ \Omega(\sqrt k). \]

注意上界与 \(n\) 无关——像经典的 \(\log(n/k)\) 因子被整体消去了。

它的工作机制与通配符搜索完全不同，值得一提，因为它展示了"OR 语义"的另一种用法。先看 \(k=1\) 的极端情形：

引理（\(k=1\) 时一次查询足矣）. 承诺 \(|x|\le1\) 时，\(\operatorname{OR}_{i\in S}x_i=x\cdot 1_S\)（点积），因此 OR-oracle 就是内积 oracle——这正是 Bernstein–Vazirani 式相位反冲的舞台。制备 \(2^{-n/2}\sum_s|s\rangle(|0\rangle-|1\rangle)/\sqrt2\)，查询一次把相位 \((-1)^{s\cdot x}\) 踢回叠加，再作用 \(H^{\otimes n}\)，测得 \(|x\rangle\)。

一般 \(k\) 的算法（概要）：以概率 \(1/k\) 独立采每个元素得到子集 \(S\)，在 \(S\) 上做同样的"Hadamard 读出"，得到串 \(y\)。可以证明输出满足：凡 \(y_i=1\) 处必有 \(x_{S_i}=1\)（零假阳性——读出的坏元素必然是真坏元素），且 \(S\) 恰含一个坏元素（概率 \(\ge(1-1/k)^{k-1}\ge1/e\)）时必然学到它。于是期望 \(O(1)\) 次查询学到一个新的坏元素，共 \(O(k)\) 次；若只知上界 \(k\) 而不知真值，按 \(2^0,2^1,\dots\) 猜规模，每步多付 \(O(\log k)\)，总 \(O(k\log k)\)。用补集查询可以验证是否已找全，故它也是 Las Vegas 的。

两个问题的关系。语义上二者"相反"：通配符问"全部相等吗"，CGT 问"存在坏元素吗"，且 CGT 带稀疏承诺。论文给出一个干净的块构造说明通配符搜索是 CGT 的特例：把 \(2k\) 个位置分成 \(k\) 块 \(B_i=\{2i-1,2i\}\)，承诺每块恰有一个 \(1\)，其位置编码一个比特 \(z_i\)。CGT 查询与 \(B_i\) 的交可以是 \(\{2i-1\}\)（问 \(z_i=0\)？）、\(\{2i\}\)（问 \(z_i=1\)？）或 \(\varnothing\)（跳过），整条查询是这些子问题的 OR——把回答取反，就得到对 \(\bar z\) 的一条通配符查询。因此 CGT 算法可以解通配符搜索，且第 5.2 节的 \(\Omega(\sqrt n)\) 下界经此归约传递成 CGT 的 \(\Omega(\sqrt k)\)。

6.3 一段修正史¶

这两个问题之间的关系曾导致一个被撤回的结果，值得记录。论文的早期版本声称通过"把 CGT 归约到通配符搜索"得到 CGT 的 \(O(\sqrt k\,\mathrm{polylog}(k))\) 量子上界；该归约后来被发现有误（一位同行发现了关键错误），作者在 v4 中明确撤回并"略微弱化结果"。目前可靠的结论是：

通配符搜索：\(O(\sqrt n\log n)\) 期望查询，\(\Omega(\sqrt n)\) 下界；
CGT：\(O(k\log k)\) 期望查询（第 6.2 节的算法），\(\Omega(\sqrt k)\) 下界；其精确量子查询复杂度仍是公开问题。

教训有二：其一，两个 oracle 语义"看起来可以互相模拟"时，必须逐分支核对查询的代数形式，特别是自适应性与取反；其二，文献中"曾经宣布后被修正"的界不应当被无批判地引用。

7. 数值小例子¶

7.1 一次通配符查询的解剖¶

设 \(x=101101\)（位置从 \(1\) 编号）。查询

\[ S=\{1,3,4,6\},\qquad y=1111 \]

按定义逐一比较：\(x_1=1=y_1\)，\(x_3=1=y_2\)，\(x_4=1=y_3\)，\(x_6=1=y_4\)，全部相等，故 \(Q_x(S,y)=1\)。用模式串写法，这是 \(s=1*11*1\) 与 \(x=101101\) 的匹配（第 \(2,5\) 位是 *，不检查）。

7.2 二分修错全程¶

沿用 \(x=101101\)。假设某轮 PGM 给出整串猜测 \(\widetilde x=101001\)。逐位比对：只有第 \(4\) 位不同（\(x_4=1\)，\(\widetilde x_4=0\)），\(d=1\)。修错过程：

整段验证：查询 \((\{1,\dots,6\},101001)\)。\(x_{\{1..6\}}=101101\ne101001\)，答案 \(0\)——有错，进入二分。
二分第 1 步：查询 \((\{1,2,3\},101)\)（猜测的前半段）。\(x_{\{1,2,3\}}=101\) 相等，答案 \(1\)——前半段全对，错误在后半段 \(\{4,5,6\}\)。
二分第 2 步：查询 \((\{4,5\},00)\)。\(x_{\{4,5\}}=10\ne00\)，答案 \(0\)——错误在 \(\{4,5\}\) 内。
二分第 3 步：查询 \((\{4\},0)\)。\(x_4=1\ne0\)，答案 \(0\)——错误就在第 \(4\) 位。区间已收敛到单点，定位完成。
修正与复验：翻转 \(\widetilde x_4\) 得 \(101101\)；再查询 \((\{1,\dots,6\},101101)\)，答案 \(1\)——修好了。

整轮共 \(5\) 次查询（\(1\) 次初始验证 \(+\lceil\log_2 6\rceil=3\) 次二分 \(+1\) 次复验），与"\(1+\log n\) 每个错误"的记账一致。对比之下，若用位查询逐位扫描，最坏要 \(6\) 次才能找到一个错误——通配符语义的优势就体现在这里。

7.3 阶梯的数值¶

取 \(n=100\)，按 \(n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil\) 自顶向下：

\[ 100\to90\to81\to72\to64\to56\to49\to42\to36\to30\to25\to20\to16\to12\to9\to6\to4\to2\to1, \]

共 \(18\) 步，对照 ODE 估计 \(2(\sqrt{100}-\sqrt{1})=18\)，严格吻合。算法不必走到 \(1\)：在 \(n_0\approx\sqrt n=10\) 附近（上表走到 \(9\)，\(14\) 步）就可以停，用第 0 阶段抄写。每步的增量正是 \(\lceil\sqrt{n_s}\rceil\)：例如 \(100\to90\) 学 \(10\) 位，\(36\to30\) 学 \(6\) 位，\(16\to12\) 学 \(4\) 位——"每轮学习 \(\Theta(\sqrt{\text{规模}})\) 位"的直接体现。

7.4 手算 PGM：\(n=2,\ k=1\)¶

把第 3 节的全部公式在一个能手算的规模上过一遍。\(n=2,k=1\)（缺失 \(m=1\) 位）：

态与 Gram。\(|\psi_{00}^1\rangle=\frac{|1\rangle|0\rangle+|2\rangle|0\rangle}{\sqrt2}\) 等四个态。Gram 公式给出 \(f(0)=1,f(1)=\frac12,f(2)=0\)，即第 3.3 节校验中写出的矩阵。

特征值。\(\lambda(t)=2^1\binom{2-t}{1}\big/\binom21\)：\(\lambda(0)=2,\ \lambda(1)=1,\ \lambda(2)=0\)，与直接对角化一致。

\(\sqrt G\) 与输出分布。由反解公式 \(\sqrt G_{0y}=\frac14\sum_z\sqrt{\lambda(z)}(-1)^{z\cdot y}\)：

\[ \sqrt G_{00}=\tfrac{\sqrt2+2}{4},\quad \sqrt G_{01}=\sqrt G_{10}=\tfrac{\sqrt2}{4},\quad \sqrt G_{11}=\tfrac{\sqrt2-2}{4}. \]

取平方得输出分布 \(g(y)=(\sqrt G_{0y})^2\)：

\[ g(00)=\frac{3+2\sqrt2}{8}\approx0.7285,\quad g(01)=g(10)=\frac18,\quad g(11)=\frac{3-2\sqrt2}{8}\approx0.0214, \]

且 \(\sum_yg(y)=\frac{3+2\sqrt2+3-2\sqrt2}{8}+\frac28=1\)（这同时也是对"PGM 输出概率 \(=(\sqrt G_{xy})^2\)"的独立数值验证：一个概率分布必须归一）。

期望错误数。

\[ D_1=1\cdot\bigl(g(01)+g(10)\bigr)+2\cdot g(11)=\frac14+\frac{3-2\sqrt2}{4}=1-\frac{\sqrt2}{2}\approx0.293. \]

再用 Step B 的公式核对：偏差 \(\mathbb E[(-1)^{\widetilde x_1}]=g(00)+g(01)-g(10)-g(11)=g(00)-g(11)=\frac{4\sqrt2}{8}=\frac1{\sqrt2}\)，故 \(D_1=\frac n2(1-\frac1{\sqrt2})=1-\frac{\sqrt2}{2}\)，与逐位直接计算完全一致。最后核对 Step C 的特征值表达式：\(2^n\widehat g(e_1)=2^{-n}\sum_a\sqrt{\lambda(a)\lambda(a\oplus e_1)}=\frac14(\sqrt2+\sqrt2+0+0)=\frac1{\sqrt2}\)（\(a=00,01\) 两项非零，\(a=10,11\) 因 \(\lambda(11)=0\) 而为零），与直接算出的偏差再次一致。也就是说：在这个玩具规模下，PGM 输入 \(|\psi_{00}^1\rangle\) 时约有 \(73\%\) 概率整串猜对、\(29\%\) 的期望错误位数——数量级上正是 Lemma 3 所说的 \(O(1)\)。

8. 本课小结¶

小结。

子集态 \(|\psi_x^k\rangle\) 把"缺 \(n-k\) 位的视图"放进相干叠加；其 Gram 矩阵只依赖汉明距离，因而被 \(\mathbb Z_2^n\) 的特征标对角化，特征值有闭式 \(\lambda(z)=2^{n-k}\binom{n-|z|}{n-k}\big/\binom nk\)。
谱在重量轴上以 \(n/(n-k)\) 的尺度衰减，把"\(\sqrt n\) 缺失位"钉成分辨率窗口；窗口内 PGM（对这组几何均匀的态还是最优测量）以期望 \(O(1)\) 个错误恢复整串。
通配符查询一次验证一整段；配合相干二分，每个错误 \(O(\log n)\) 次查询即可定位并修正。
阶梯 \(n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil\) 有 \(L=O(\sqrt n)\) 级，总复杂度 \(O(\sqrt n)+O(\sqrt n)\cdot O(\log n)=O(\sqrt n\log n)\) 期望查询；对抗法给出 \(\Omega(\sqrt n)\) 下界，算法近最优。
与位查询、CGT 的边界要划清：位查询模拟不了整段验证（\(\Theta(n)\) 壁垒）；CGT 有自己的 \(O(k\log k)\) 算法与 \(\Omega(\sqrt k)\) 下界，二者之间的错误归约曾被撤回。

练习题¶

练习 1【通配符查询模型】（→ 1.1 节）

基础：设 \(x=101101\)（位置从 \(1\) 编号）。计算 \(Q_x(\{1,3,4,6\},1111)\) 与 \(Q_x(\{1,3,4,6\},1101)\)，并把这两次查询分别写成模式串 \(s\in\{0,1,*\}^6\) 的形式。
基础：说明当 \(|S|=1\) 时如何用两次通配符查询读出 \(x_i\)，由此说明通配符查询可以模拟位查询。
进阶（位查询的不可模拟性）：指出算法四个步骤中哪一步无法用 \(O(1)\) 次位查询模拟，并说明：若把每条通配符查询都换成"逐位读取再比较"的实现，整个算法的查询复杂度会退化到什么阶？结合第 1.3 节说明为什么这种退化不是实现技巧的问题。

提示：第 6.1 节逐条检查了算法的每个"用钱之处"。

练习 2【经典与位查询的线性壁垒】（→ 1.2 节）

基础：写出经典确定性下界的鸽笼论证：做 \(q\) 次查询的算法至多产生多少种记录？由此说明 \(q<n\) 时为何必然存在两个输入产生完全相同的记录，从而算法至少错一个。
基础：复述位查询模型下 oracle 审讯的精确量子复杂度，并指出上界与下界各来自哪些结果。
进阶（经典随机下界）：把第 1.2 节的随机情形论证补全：证明若经典算法以概率 \(\ge2/3\) 输出 \(x\)，则期望查询数为 \(\Omega(n)\)。

提示：条件熵 \(H(X\mid\text{输出})\) 与 Fano 不等式；每比特答案关于 \(X\) 的互信息至多 \(1\)。

练习 3【猜—验—修的算法直觉】（→ 2 节）

基础：解释为什么在通配符模型里验证一个长度为 \(\ell\) 的整段猜测只要一次查询、定位一个错误位置只要 \(O(\log n)\) 次查询；并计算朴素地随机猜一个 \(n\) 位串全对的概率。
进阶：核算算术骨架：若每轮把已知位数从 \(k\) 推进到 \(k+\Theta(\sqrt k)\)，证明走完 \(n\) 位需要 \(O(\sqrt n)\) 轮，每轮期望 \(O(\log n)\) 次查询，总计 \(O(\sqrt n\log n)\)。

提示：与常微分方程 \(\frac{dn}{ds}=\sqrt n\) 比较（即 \(\frac{d}{ds}\sqrt n=\frac12\)），对照第 4.1 节的下降版本。

练习 4【子集态与 Gram 矩阵】（→ 3.1 节）

基础：写出 \(n=2,k=1\) 时的四个子集态 \(|\psi_{00}^1\rangle,|\psi_{01}^1\rangle,|\psi_{10}^1\rangle,|\psi_{11}^1\rangle\)，并用 Lemma 1 计算 \(\langle\psi_{00}^1|\psi_{01}^1\rangle\)。
进阶（内积公式的特例）：直接由 Lemma 1 计算：(a) \(d(x,y)=1\) 时 \(\langle\psi_x^k|\psi_y^k\rangle=\frac{n-k}{n}\)；(b) \(d(x,y)=2\) 时的表达式；(c) 证明 \(k=n\) 时诸态两两正交（从"差异位置集必须被避开"的计数角度说明，而不只是代入公式）。

提示：把 \(\binom{n-d}{k}\big/\binom nk\) 写成连乘即可得到 (a)、(b)。

练习 5【Fourier 对角化与谱窗口】（→ 3.3 节）

基础：对 \(n=2,k=1\) 用特征值闭式计算 \(\lambda(00),\lambda(01),\lambda(11)\)，并验证 \(\sum_z\lambda(z)=2^n\)。
进阶（特征值手算）：取 \(n=4,k=2\)：列出 \(\lambda(t)\)（\(t=0,1,2,3,4\)）与 \(f(d)\)（\(d=0,\dots,4\)），验证 \(\sum_z\lambda(z)=16\) 与任意一行的行和等于 \(2^{n-k}=4\)，并解释行和的组合意义。
进阶：由连乘近似说明特征值在重量轴上以 \(n/m\) 的尺度衰减，并解释 \(m=c\sqrt n\) 时分辨率窗口为何是 \(\sqrt n/c\)。

提示：行和——固定 \(x\)，数满足 \(x_S=y_S\) 的 \((y,S)\) 对；衰减——仿照第 3.4 节的 \(\prod_{j<t}\frac{n-j-m}{n-j}\le e^{-mt/n}\)。

练习 6【Pretty-Good Measurement 与期望常数个错误】（→ 3.5 节）

基础：证明 \(\sum_x M_x=I\)，即 PGM 是合法 POVM；再对 \(n=2,k=1\)，利用 \(\sqrt G_{00}=\frac{\sqrt2+2}{4}\)、\(\sqrt G_{01}=\sqrt G_{10}=\frac{\sqrt2}{4}\)、\(\sqrt G_{11}=\frac{\sqrt2-2}{4}\) 计算输出分布 \(g(00),g(01),g(10),g(11)\) 并验证归一。
进阶（对称性与最优性）：定义 \(U_z|S\rangle|w\rangle=|S\rangle|w\oplus z_S\rangle\)。(a) 证明 \(\{U_z\}_{z\in\{0,1\}^n}\) 是一个阿贝尔酉群，且 \(U_z|\psi_0^k\rangle=|\psi_z^k\rangle\)（即态集合几何均匀）；(b) 由此证明 \(\sqrt G\) 的对角元全相等，并说明这正是第 4.4 节评注 1 中"测量标志不扭曲分支振幅"的根源；(c) 补全第 3.6 节 Step B 中 \(\widehat h(e_i)=-\frac12\) 与 \(\widehat h(z)=0\ (|z|\ge2)\) 的配对计算。

提示：(a) 逐位验证 \(U_zU_{z'}=U_{z\oplus z'}\)；(c) 把 \(y\) 与 \(y\oplus e_j\)（\(j\in\operatorname{supp}(z)\)）配对。

练习 7【阶梯生长算法与总复杂度】（→ 4 节）

基础：按顺序列出扩张阶段的五个步骤并标注每步的查询数；再说明第 0 阶段如何用 \(n_0=O(\sqrt n)\) 次查询制备 \(|\psi_x^{n_0}\rangle\)，以及终态 \(|\psi_x^n\rangle\) 为何直接给出答案。
进阶：解释为什么不能一步到位——直接制备 \(|\psi_x^{\,n-c\sqrt n}\rangle\) 再做一次 PGM：哪一笔成本没有被省掉？
进阶（阶段数）：证明递推 \(n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil\) 从 \(n\) 降到 \(O(\sqrt n)\) 需要 \(\Theta(\sqrt n)\) 步。要求把 ODE 比较论证补严格（例如证明每一步 \(\sqrt{n_s}\) 至少下降一个固定的常数分数以上或至少下降 \(\frac12-o(1)\)），并对 \(n=100\) 列出完整序列。

提示：与 \(\frac{d}{ds}\sqrt n=-\frac12\) 的 ODE 比较；第 7.3 节的数值序列可作对照。

练习 8【量子下界与近最优性】（→ 5.2 节）

基础：对权重方案 \(w(x,y)=1[d(x,y)=1]\) 计算 \(\mathrm{wt}(x)\)；再复述 \(v(x,q)\) 在 \(\zeta(x,q)=1\)、\(\zeta(x,q)=0\) 且 \(\delta=1\)、\(\zeta(x,q)=0\) 且 \(\delta\ge2\) 三种情形的取值。
进阶：把 \(\mathrm{wt}\) 与 \(v\) 的值代入强加权对抗法定理，完成 \(\Omega(\sqrt n)\) 下界的推导；并说明上界 \(O(\sqrt n\log n)\) 与该下界之间的对数因子来自何处。

提示：仿照正文取 \(\zeta(x,q)=1\)、\(\zeta(y,q)=0\) 的三元组；对数因子回到第 5.1 节逐项核算每轮的修错二分。

参考文献¶

Zoo 编号 167：Andris Ambainis 与 Ashley Montanaro, Quantum Algorithms for Search with Wildcards and Combinatorial Group Testing.