# 通配符搜索：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 算法](../ch03-algo-basics/grover.md)与[碰撞与元素唯一性](collision-element-distinctness.md)中的两类套路），而是来自一个**状态判别 (state discrimination)** 问题——用 Pretty-Good Measurement 从一堆非正交态里"读出"一个近乎正确的整串猜测。本教程的标题正是在描述它的工作方式：**每一轮把已知的位数从 $k$ 推进到 $k+\Theta(\sqrt k)$，一共 $O(\sqrt n)$ 轮，每轮付出 $O(\log n)$ 次查询去验证并修正猜测**。

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

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

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

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

:::

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

(wildcard-query-model)=
### 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：

$$
|S\rangle|y\rangle|z\rangle\ \mapsto\ |S\rangle|y\rangle|z\oplus Q_x(S,y)\rangle,
$$

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

两个直接观察：

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

(linear-barriers)=
### 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]$ 是一个**关于整段串的全局谓词**，于是量子算法可以把"一整段候选串"放进叠加里，让相位反冲携带全局的匹配信息。本章的 [模式匹配](pattern-matching.md) 一课讨论的子串查询模型（" $y$ 是否为 $x$ 的连续子串"）是同一思路的另一个变体，Cleve 等人对它给出了 $3n/4+o(n)$ 的量子算法。

(guess-verify-repair-intuition)=
## 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. 核心状态判别问题

(subset-state-gram)=
### 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)$ 次查询就能修掉。

(fourier-spectrum-window)=
### 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$ 上的卷积矩阵，而卷积矩阵被**特征标**对角化——这正是 [量子傅里叶变换](../ch03-algo-basics/quantum-fourier-transform.md)中的老朋友：对每个 $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$，故

$$
G=\begin{pmatrix}1&\tfrac12&\tfrac12&0\\ \tfrac12&1&0&\tfrac12\\ \tfrac12&0&1&\tfrac12\\ 0&\tfrac12&\tfrac12&1\end{pmatrix}
$$

（行、列按 $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{规模}})$ 个新位。

(pgm-constant-errors)=
### 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$（特征值只依赖重量），上式是各层贡献的加权和，权重是二项式系数。关键观察有三条：

1. **质量集中在中间层**。权重 $\binom nt$ 集中在 $t=n/2\pm O(\sqrt n)$，尾部指数小（Chernoff 界）。
2. **相邻层的特征值几乎相等**。由闭式，$\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)$ 本身几乎一样。
3. **凹函数下界**。论文对每一层的主项使用初等不等式

$$
\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}$ 个分支中以一致相位出现，测量提取的是全局一致性，而不是逐位采样。

(staircase-algorithm)=
## 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$：

1. 制备均匀叠加 $\sum_{|S|=n_0}|S\rangle$，并为值准备 $n_0$ 个槽位（第 $j$ 槽对应 $S$ 的第 $j$ 小元素，纯组合计算，无需 oracle）。
2. 对每个 $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)"一词的明确约定：期望针对最坏输入上的内部随机性。

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

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

(quantum-lower-bound)=
### 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$ 的量子算法需要

$$
\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)
$$

次查询。

**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 算法](../ch03-algo-basics/grover.md)所面对的问题形态，平方根下界的直觉完全一致；上面的对抗法证明把这个直觉变成了定理。

### 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. **整段验证**：查询 $(\{1,\dots,6\},101001)$。$x_{\{1..6\}}=101101\ne101001$，答案 $0$——有错，进入二分。
2. **二分第 1 步**：查询 $(\{1,2,3\},101)$（猜测的前半段）。$x_{\{1,2,3\}}=101$ 相等，答案 $1$——前半段全对，错误在后半段 $\{4,5,6\}$。
3. **二分第 2 步**：查询 $(\{4,5\},00)$。$x_{\{4,5\}}=10\ne00$，答案 $0$——错误在 $\{4,5\}$ 内。
4. **二分第 3 步**：查询 $(\{4\},0)$。$x_4=1\ne0$，答案 $0$——错误就在第 $4$ 位。区间已收敛到单点，定位完成。
5. **修正与复验**：翻转 $\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 节](#wildcard-query-model)）

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

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

**练习 2【经典与位查询的线性壁垒】**（→ [1.2 节](#linear-barriers)）

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

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

**练习 3【猜—验—修的算法直觉】**（→ [2 节](#guess-verify-repair-intuition)）

1. 基础：解释为什么在通配符模型里验证一个长度为 $\ell$ 的整段猜测只要一次查询、定位一个错误位置只要 $O(\log n)$ 次查询；并计算朴素地随机猜一个 $n$ 位串全对的概率。
2. 进阶：核算算术骨架：若每轮把已知位数从 $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 节](#subset-state-gram)）

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$。
2. 进阶（内积公式的特例）：直接由 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 节](#fourier-spectrum-window)）

1. 基础：对 $n=2,k=1$ 用特征值闭式计算 $\lambda(00),\lambda(01),\lambda(11)$，并验证 $\sum_z\lambda(z)=2^n$。
2. 进阶（特征值手算）：取 $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$，并解释行和的组合意义。
3. 进阶：由连乘近似说明特征值在重量轴上以 $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 节](#pgm-constant-errors)）

1. 基础：证明 $\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)$ 并验证归一。
2. 进阶（对称性与最优性）：定义 $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 节](#staircase-algorithm)）

1. 基础：按顺序列出扩张阶段的五个步骤并标注每步的查询数；再说明第 0 阶段如何用 $n_0=O(\sqrt n)$ 次查询制备 $|\psi_x^{n_0}\rangle$，以及终态 $|\psi_x^n\rangle$ 为何直接给出答案。
2. 进阶：解释为什么不能一步到位——直接制备 $|\psi_x^{\,n-c\sqrt n}\rangle$ 再做一次 PGM：哪一笔成本没有被省掉？
3. 进阶（阶段数）：证明递推 $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 节](#quantum-lower-bound)）

1. 基础：对权重方案 $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$ 三种情形的取值。
2. 进阶：把 $\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](https://arxiv.org/abs/1210.1148).