通配符搜索

我们要研究的问题叫做通配符搜索 (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{次查询（期望）},\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 节给出若干可手算的数值例子。

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],y\in \{0,1{\}}^{|S|},$$

oracle 返回

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

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

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

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

其中 $z$ 是一个答案比特。注意查询寄存器本身可以是叠加态——这是后文一切”一次查询处理所有分支”操作的物理基础。要相位版本的 oracle（把答案 kick back 成 $(-1{)}^{Q_x}$），只需在答案比特上准备 $(|0⟩-|1⟩)/\sqrt{2}$，这是我们在 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^{\prime }$ 产生完全相同的记录，于是算法对二者输出同一个串，至少错一个。故 $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⟩=\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}}\sum _{S\subseteq [n],|S|=k}|S⟩|x_S⟩,$$

即所有”缺 $n-k$ 位”的视图的均匀叠加。关键在于这个叠加是相干的：同一个位置 $i$ 出现在大量分支 $S\ni i$ 中，且各分支中 $x_i$ 的振幅相位一致。这些相干重叠编码了强烈的全局冗余——第 3 节将证明，当缺失的位数是 $O(\sqrt{n})$ 时，存在一个测量（PGM），其输出 $\tilde{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)$。总计

$$\underset{\text{第 0 阶段抄写}}{\underbrace{O(\sqrt{n})}}+\underset{\text{轮数}}{\underbrace{O(\sqrt{n})}}\times \underset{\text{每轮验证与修错}}{\underbrace{O(\log n)}}=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⟩:=\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}}\sum _{S\subseteq [n],|S|=k}|S⟩|x_S⟩,|x_S⟩:=\underset{i\in S}{⨂}|x_i⟩,$$

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

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

3.2 Gram 矩阵只依赖汉明距离

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

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

$$⟨{\psi }_x^k|{\psi }_y^k⟩=\frac{\left(\genfrac{}{}{0ex}{}{n-d(x,y)}{k}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}.$$

证明。按定义展开：

$$⟨{\psi }_x^k|{\psi }_y^k⟩=\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\sum _{S,S^{\prime },|S|=|S^{\prime }|=k}⟨S|S^{\prime }⟩⟨x_S|y_{S^{\prime }}⟩.$$

计算基矢正交给出 $⟨S|S^{\prime }⟩={\delta }_{S,S^{\prime }}$，于是双重求和坍缩成单重：

$$⟨{\psi }_x^k|{\psi }_y^k⟩=\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\sum _{|S|=k}⟨x_S|y_S⟩=\frac{1}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}\sum _{|S|=k}\prod _{i\in S}⟨x_i|y_i⟩.$$

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

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

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

$$\frac{\left(\genfrac{}{}{0ex}{}{n-d}{k}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}=\frac{(n-d)!(n-k)!}{n!(n-d-k)!}=\prod _{j=0}^{d-1}\frac{n-k-j}{n-j}\approx (1-\frac{m}{n}{)}^d\approx e^{-md/n},$$

其中最后两步对 $d\ll n$、$m\ll n$ 使用了 ${\prod }_j(1-\frac{m}{n-j})\approx (1-\frac{m}{n}{)}^d$ 与 $(1-\frac{m}{n}{)}^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{\left(\genfrac{}{}{0ex}{}{n-|w|}{k}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}.$$

（由 Lemma 1，$G_{xy}=⟨{\psi }_x^k|{\psi }_y^k⟩$ 只依赖 $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{\left(\genfrac{}{}{0ex}{}{n-|z|}{n-k}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}.$$

（按标准约定，下指标超出范围的二项式系数取 $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$ 是重量函数，三者请勿混淆。）

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

$$\left(\genfrac{}{}{0ex}{}{n-|w|}{k}\right)=\#\{S\subseteq [n]:|S|=k,S\cap \mathrm{supp}(w)=\varnothing \},$$

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

$$\sum _w(-1{)}^{z\cdot w}(\genfrac{}{}{0ex}{}{n-|w|}{k})=\sum _{|S|=k}\sum _{w:\mathrm{supp}(w)\cap S=\varnothing }(-1{)}^{z\cdot w}.$$

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

$$\sum _{w\subseteq \bar{S}}(-1{)}^{z\cdot w}=\prod _{i\in \bar{S}}(1+(-1{)}^{z_i}).$$

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

$$\sum _w(-1{)}^{z\cdot w}(\genfrac{}{}{0ex}{}{n-|w|}{k})=2^{n-k}\cdot \#\{S:|S|=k,\mathrm{supp}(z)\subseteq S\}=2^{n-k}(\genfrac{}{}{0ex}{}{n-|z|}{k-|z|}).$$

最后 $\left(\genfrac{}{}{0ex}{}{n-|z|}{k-|z|}\right)=\left(\genfrac{}{}{0ex}{}{n-|z|}{(n-|z|)-(k-|z|)}\right)=\left(\genfrac{}{}{0ex}{}{n-|z|}{n-k}\right)$，除以 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 即得闭式。Q.E.D.

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

• 迹：${\sum }_z\lambda (z)=\mathrm{Tr}G=2^n$（对角元全是 $1$）。用恒等式 $\left(\genfrac{}{}{0ex}{}{n}{t}\right)\left(\genfrac{}{}{0ex}{}{n-t}{m}\right)=\left(\genfrac{}{}{0ex}{}{n}{m}\right)\left(\genfrac{}{}{0ex}{}{n-m}{t-m}\right)$（先选 $M$ 再选不相交的 $T$，与先选 $T$ 再在余下选 $M$，数的是同一个集合对）与 ${\sum }_t\left(\genfrac{}{}{0ex}{}{n-m}{t-m}\right)=2^{n-m}$，取 $m=n-k$：

$$\sum _t\left(\genfrac{}{}{0ex}{}{n}{t}\right)2^{n-k}\frac{\left(\genfrac{}{}{0ex}{}{n-t}{n-k}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}=2^{n-k}\frac{\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)2^k}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}=2^n,$$

与所要验证的迹一致。

• 小例子（$n=2,k=1$）。此时 $f(0)=1,f(1)=\frac{1}{2},f(2)=0$，故

$$G=\left(\begin{array}{cccc}1& \frac{1}{2}& \frac{1}{2}& 0\\ \frac{1}{2}& 1& 0& \frac{1}{2}\\ \frac{1}{2}& 0& 1& \frac{1}{2}\\ 0& \frac{1}{2}& \frac{1}{2}& 1\end{array}\right)$$

（行、列按 $00,01,10,11$ 排列）。闭式给出 $\lambda (0)=2^1\left(\genfrac{}{}{0ex}{}{2}{1}\right){\left(\genfrac{}{}{0ex}{}{2}{1}\right)}^{-1}=2$，$\lambda (1)=2\left(\genfrac{}{}{0ex}{}{1}{1}\right){\left(\genfrac{}{}{0ex}{}{2}{1}\right)}^{-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⟩⟨{\chi }_z|/2^n$ 逐元写出就是上式。

3.4 谱的形状与参数窗口

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

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

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

$$\frac{\lambda (t)}{2^m}=\frac{\left(\genfrac{}{}{0ex}{}{n-t}{m}\right)}{\left(\genfrac{}{}{0ex}{}{n}{m}\right)}=\prod _{j=0}^{t-1}\frac{n-j-m}{n-j}\approx (1-\frac{m}{n}{)}^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\le 1$）时 $({\sqrt{G}}_{xx}{)}^2\ge 1-2a^2-O(1/\sqrt{n})$，而缺 $a\sqrt{n}$ 位（$a$ 偏大）时 $({\sqrt{G}}_{xx}{)}^2\le 4e^{-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⟩⟨{\psi }_x^k|,M_x:={\rho }^{-1/2}|{\psi }_x^k⟩⟨{\psi }_x^k|{\rho }^{-1/2},$$

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

合法性：每个 $M_x$ 显然半正定，且

$$\sum _x{M}_x={\rho }^{-1/2}(\sum _x|{\psi }_x^k⟩⟨{\psi }_x^k|){\rho }^{-1/2}={\rho }^{-1/2}\rho {\rho }^{-1/2}=I.$$

输出概率由 $\sqrt{G}$ 给出。定义矩阵 $A_{yx}:=⟨{\psi }_y^k|{\rho }^{-1/2}|{\psi }_x^k⟩$，则

$$\mathrm{Pr}[\text{输出 }y\mid \text{输入 }x]=⟨{\psi }_x^k|M_y|{\psi }_x^k⟩=|A_{yx}{|}^2=({\sqrt{G}}_{yx}{)}^2.$$

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

$$⟨{\psi }_x^k|M_y|{\psi }_x^k⟩=⟨{\psi }_x^k|{\rho }^{-1/2}|{\psi }_y^k⟩⟨{\psi }_y^k|{\rho }^{-1/2}|{\psi }_x^k⟩=|A_{yx}{|}^2.$$

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

$$(A^2{)}_{xz}=\sum _y⟨{\psi }_x^k|{\rho }^{-1/2}|{\psi }_y^k⟩⟨{\psi }_y^k|{\rho }^{-1/2}|{\psi }_z^k⟩=⟨{\psi }_x^k|{\rho }^{-1/2}\rho {\rho }^{-1/2}|{\psi }_z^k⟩=G_{xz},$$

其中收拢一步用了 ${\sum }_y|{\psi }_y^k⟩⟨{\psi }_y^k|=\rho$，最后一步用了 ${\rho }^{-1/2}\rho {\rho }^{-1/2}$ 在支撑上等于恒等。第三步，$A$ 半正定：对任意系数 $c$，令 $|\phi ⟩:={\sum }_x{c}_x|{\psi }_x^k⟩$（必落在支撑内），则

$$\sum _{x,y}\overline{c_y}{A}_{yx}{c}_x=\sum _{x,y}\overline{c_y}⟨{\psi }_y^k|{\rho }^{-1/2}|{\psi }_x^k⟩c_x=⟨\phi |{\rho }^{-1/2}|\phi ⟩\ge 0,$$

因为 ${\rho }^{-1/2}$ 在支撑上的特征值非负（顺带一提，$\rho ={\sum }_x|{\psi }_x^k⟩⟨{\psi }_x^k|$ 与标签空间上的 $G={\sum }_{x,y}{G}_{xy}|x⟩⟨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⟩$ 时输出 $\tilde{x}\in \{0,1{\}}^n$，满足

$$\mathbb{E}[d(x,\tilde{x})]=O(1),$$

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

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

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

$$g(y):=({\sqrt{G}}_{0y}{)}^2,\sum _{y}g(y)=1.$$

（归一化正是 ${\sum }_y\mathrm{Pr}[\tilde{x}=y\mid 0]=1$。）

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

$$D_k=\sum _y|y|g(y)=\sum _{i=1}^n\mathrm{Pr}[{\tilde{x}}_i=1]=\sum _{i=1}^n\frac{1-\mathbb{E}[(-1{)}^{{\tilde{x}}_i}]}{2}.$$

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

$$D_k=\frac{n}{2}(1-2^n\hat{g}(e_1)).$$

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

$$\hat{h}(0^n)=\frac{n}{2},\hat{h}(e_i)=-\frac{1}{2},\hat{h}(z)=0(|z|\ge 2),$$

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

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

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

$$2^n\hat{g}(e_1)=2^n\sum _a\hat{u}(a)\hat{u}(a\oplus e_1)=2^{-n}\sum _{a\in \{0,1{\}}^n}\sqrt{\lambda (a)\lambda (a\oplus e_1)}.$$

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

1. 质量集中在中间层。权重 $\left(\genfrac{}{}{0ex}{}{n}{t}\right)$ 集中在 $t=n/2\pm O(\sqrt{n})$，尾部指数小（Chernoff 界）。
2. 相邻层的特征值几乎相等。由闭式，$\lambda (t)/\lambda (t+1)=\left(\genfrac{}{}{0ex}{}{n-t}{m}\right)/\left(\genfrac{}{}{0ex}{}{n-t-1}{m}\right)=\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 \frac{3}{2}x-\frac{1}{2}{x}^2(x\ge 0),$$

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

三层合起来给出 $2^n\hat{g}(e_1)\ge 1-O(1/n)$，代回 Step B：

$$D_k=\frac{n}{2}\cdot O(1/n)=O(1).$$

Q.E.D.

评注（诚实声明）。Step D 中”逐层展开并把余项加总”涉及对二项式系数与 Krawtchouk 型和的细致控制，本词条只展示了结构与关键不等式；完整的逐项估计见论文第 3 节（其附录 A 还包含精确识别概率的上下界，即第 3.4 节引用的两条）。此外论文还借助 Eldar–Forney 的定理说明：这组态在阿贝尔群 $\{U_z\}$（$U_z|S⟩|w⟩=|S⟩|w\oplus z_S⟩$，满足 $U_z|{\psi }_0^k⟩=|{\psi }_z^k⟩$，见习题 6）下几何均匀 (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⟩$ 出发做一次 PGM，期望只错 $O(1)$ 位，整串恰好猜对的概率为常数——而且残余的错误位每个只需 $O(\log n)$ 次查询就能定位并修复。

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

4. 阶梯生长算法

4.1 蓝图与阶段序列

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

$$n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil (1\le s\le L),n_0=O(\sqrt{n}),$$

即自顶向下地从 $n$ 每次砍掉约 $\sqrt{(\cdot )}$。第 $s$ 阶段把 $|{\psi }_x^{n_{s-1}}⟩$ 升级成 $|{\psi }_x^{n_s}⟩$；由 $n_L=n$ 与 $|{\psi }_x^n⟩=|[n]⟩|x⟩$，最终测量第二个寄存器即得 $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})=-\frac{1}{2}$，即 $\sqrt{n}$ 关于 $s$ 以斜率 $-\frac{1}{2}$ 线性下降，从 $\sqrt{n}$ 降到 $\sqrt{n_0}=O(n^{1/4})$ 需要

$$L\approx 2(\sqrt{n}-\sqrt{n_0})=\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}}⟩$ 然后做一次 PGM？因为制备本身就需要知道 $x$：oracle 只做验证、不报数值，把 $n-c\sqrt{n}$ 个位置的值写进寄存器仍然要逐位抄写，一次 PGM 省不掉这个成本。阶梯的意义在于让 PGM 的”猜测”替代”抄写”：每一轮只需第 0 阶段那样抄 $\sqrt{(\cdot )}$ 位（而且只在最初做一次），之后的增长全部由”猜 + 验 + 修”驱动。

4.2 第 0 阶段：直接抄写 $\sqrt{n}$ 位

制备初态 $|{\psi }_x^{n_0}⟩$：

1. 制备均匀叠加 ${\sum }_{|S|=n_0}|S⟩$，并为值准备 $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$ 槽。

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

$$|{\psi }_x^{n_0}⟩=\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{n}{n_0}\right)}}\sum _{|S|=n_0}|S⟩|x_S⟩.$$

4.3 扩张阶段的五个步骤

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

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

$$|{\psi }_x^{n_{s-1}}⟩⟼\sum _{S\subseteq [n],|S|=n_s}|S⟩|{\psi }_{x_S}^{n_{s-1}}⟩,$$

（外层省略归一化因子 $1/\sqrt{\left(\genfrac{}{}{0ex}{}{n}{n_s}\right)}$；内层 $|{\psi }_{x_S}^{n_{s-1}}⟩={\left(\genfrac{}{}{0ex}{}{n_s}{n_{s-1}}\right)}^{-1/2}{\sum }_{T\subset S,|T|=n_{s-1}}|T⟩|x_T⟩$ 是以 $S$ 为全集的子集态。）为什么零查询？因为这步只是对已在寄存器里的旧值做重组：从分支 $T$ 出发，均匀叠加它的超集 $S\supseteq T$（从 $[n]\setminus 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(S,\widetilde{x_S})=1[\widetilde{x_S}=x_S]$$

到标志比特，然后测量标志。若读到 $1$：所有存活分支的猜测都整段正确，态形如 ${\sum }_{|S|=n_s}|S⟩|x_S{⟩}_{{\mathcal{H}}_o}|{\phi }_S{⟩}_{{\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⟩$。逆运算不消耗 oracle 查询，因为验证已经保证每一次用过的 oracle 答案都能从输出寄存器重新推出。丢弃辅助寄存器后得到

$$|{\psi }_x^{n_s}⟩=\frac{1}{\sqrt{\left(\genfrac{}{}{0ex}{}{n}{n_s}\right)}}\sum _{|S|=n_s}|S⟩|x_S⟩.$$

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

查询记账。第 $s$ 阶段（$s\ge 1$）：步骤 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⟩=|[n]⟩|x⟩$，测量第二个寄存器得到的就是 $x$ 本身；而每一阶段留给下一阶段的寄存器内容都通过了整段验证 $1[\widetilde{x_S}=x_S]$，验证不通过的分支不会进入下一阶段。运行时间的随机性来自测量的内禀随机性（PGM 猜错几位、二分撞上哪个位置），与输入 $x$ 无关，也不是假设 $x$ 随机分布——这是论文对”平均 (on average)“一词的明确约定：期望针对最坏输入上的内部随机性。

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

1. 测量标志为什么安全。测量只施加在标志比特上；由系综的对称性，PGM 在各分支给出”正确猜测”的振幅是同一个常数（$\sqrt{G}$ 的对角元与分支无关，见习题 6），所以读到 $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 不等式，超时概率 $\le 1/c$，故一次运行以常数概率在预算内成功；超时就整体重来，重复 $O(\log (1/\delta ))$ 次把失败概率压到 $\delta$。代价是查询数乘上 $O(1)$ 或 $O(\log (1/\delta ))$——常数或对数放大，不改变 $O(\sqrt{n}\log n)$ 的阶。

5. 总复杂度与下界

5.1 逐因子核算

总期望查询数是

$$\underset{\text{第 0 阶段抄写}}{\underbrace{n_0}}+\sum _{s=1}^L\underset{\text{验证}+\text{期望修错}}{\underbrace{(1+O(\log n))}}=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⟩|z⟩=|q⟩|z\oplus \zeta (x,q)⟩$ 访问。给每对输出不同的输入 $(x,y)$ 赋对称权重 $w(x,y)\ge 0$，给每个三元组 $(x,y,q)$ 赋权重 $w^{\prime }(x,y,q)\ge 0$，要求 $w^{\prime }(x,y,q)=0$ 只要 $\zeta (x,q)=\zeta (y,q)$，且对 $\zeta (x,q)\ne \zeta (y,q)$ 的对满足 $w^{\prime }(x,y,q)w^{\prime }(y,x,q)\ge w(x,y{)}^2$。记 $\mathrm{wt}(x)={\sum }_{y}w(x,y)$、$v(x,q)={\sum }_y{w}^{\prime }(x,y,q)$。则任何以概率 $\ge 2/3$ 计算 $f$ 的量子算法需要

$$\Omega \left(\underset{\begin{array}{c}x,y,q:w(x,y)>0\\ \zeta (x,q)\ne \zeta (y,q)\end{array}}{\min }\sqrt{\frac{\mathrm{wt}(x)\mathrm{wt}(y)}{v(x,q)v(y,q)}}\right)$$

次查询。

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],w^{\prime }(x,y,q)=1[d(x,y)=1\text{且}\zeta (x,q)\ne \zeta (y,q)].$$

合法性：$w$ 对称且在 $f(x)=f(y)$（即 $x=y$）时为零；$w^{\prime }$ 在 $\zeta$ 相等时为零；对 $d(x,y)=1$ 且 $\zeta$ 不同的对，$w^{\prime }(x,y,q)w^{\prime }(y,x,q)=1\cdot 1\ge 1^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 \ge 1$ 位。翻转第 $i$ 位后恰好追平，当且仅当 $\delta =1$ 且 $i$ 是那个唯一差异位。故 $v(x,q)=1$（若 $\delta =1$）或 $0$（若 $\delta \ge 2$）。

取任意满足 $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)\le 1$，于是

$$\sqrt{\frac{\mathrm{wt}(x)\mathrm{wt}(y)}{v(x,q)v(y,q)}}\ge \sqrt{\frac{n\cdot n}{n\cdot 1}}=\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 的二分：每一步都是一次子段整段验证，同上。

所以算法的全部优势都押在”一次查询验证一整段”这一语义上；习题 4 要求把这一点量化。这也是把本词条放在”查询复杂度”一章的原因：模型的一步之差，把复杂度从 $\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)={\mathrm{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|\le 1$ 时，${\mathrm{OR}}_{i\in S}{x}_i=x\cdot 1_S$（点积），因此 OR-oracle 就是内积 oracle——这正是 Bernstein–Vazirani 式相位反冲的舞台。制备 $2^{-n/2}{\sum }_s|s⟩(|0⟩-|1⟩)/\sqrt{2}$，查询一次把相位 $(-1{)}^{s\cdot x}$ 踢回叠加，再作用 $H^{\otimes n}$，测得 $|x⟩$。

一般 $k$ 的算法（概要）：以概率 $1/k$ 独立采每个元素得到子集 $S$，在 $S$ 上做同样的”Hadamard 读出”，得到串 $y$。可以证明输出满足：凡 $y_i=1$ 处必有 $x_{S_i}=1$（零假阳性——读出的坏元素必然是真坏元素），且 $S$ 恰含一个坏元素（概率 $\ge (1-1/k{)}^{k-1}\ge 1/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\},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\ast 11\ast 1$ 与 $x=101101$ 的匹配（第 $2,5$ 位是 *，不检查）。

7.2 二分修错全程

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

1. 整段验证：查询 $(\{1,\dots ,6\},101001)$。$x_{\{\mathrm{1..6}\}}=101101\ne 101001$，答案 $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\ne 00$，答案 $0$——错误在 $\{4,5\}$ 内。
4. 二分第 3 步：查询 $(\{4\},0)$。$x_4=1\ne 0$，答案 $0$——错误就在第 $4$ 位。区间已收敛到单点，定位完成。
5. 修正与复验：翻转 ${\tilde{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\to 90\to 81\to 72\to 64\to 56\to 49\to 42\to 36\to 30\to 25\to 20\to 16\to 12\to 9\to 6\to 4\to 2\to 1,$$

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

7.4 手算 PGM：$n=2,k=1$

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

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

特征值。$\lambda (t)=2^1\left(\genfrac{}{}{0ex}{}{2-t}{1}\right)/\left(\genfrac{}{}{0ex}{}{2}{1}\right)$：$\lambda (0)=2,\lambda (1)=1,\lambda (2)=0$，与直接对角化一致。

$\sqrt{G}$ 与输出分布。由反解公式 ${\sqrt{G}}_{0y}=\frac{1}{4}{\sum }_z\sqrt{\lambda (z)}(-1{)}^{z\cdot y}$：

$${\sqrt{G}}_{00}=\frac{\sqrt{2}+2}{4},{\sqrt{G}}_{01}={\sqrt{G}}_{10}=\frac{\sqrt{2}}{4},{\sqrt{G}}_{11}=\frac{\sqrt{2}-2}{4}.$$

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

$$g(00)=\frac{3+2\sqrt{2}}{8}\approx 0.7285,g(01)=g(10)=\frac{1}{8},g(11)=\frac{3-2\sqrt{2}}{8}\approx 0.0214,$$

且 ${\sum }_{y}g(y)=\frac{3+2\sqrt{2}+3-2\sqrt{2}}{8}+\frac{2}{8}=1$（这同时也是对”PGM 输出概率 $=({\sqrt{G}}_{xy}{)}^2$“的独立数值验证：一个概率分布必须归一）。

期望错误数。

$$D_1=1\cdot (g(01)+g(10))+2\cdot g(11)=\frac{1}{4}+\frac{3-2\sqrt{2}}{4}=1-\frac{\sqrt{2}}{2}\approx \mathrm{0.293.}$$

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

8. 小结与习题

小结。

• 子集态 $|{\psi }_x^k⟩$ 把”缺 $n-k$ 位的视图”放进相干叠加；其 Gram 矩阵只依赖汉明距离，因而被 ${\mathbb{Z}}_2^n$ 的特征标对角化，特征值有闭式 $\lambda (z)=2^{n-k}\left(\genfrac{}{}{0ex}{}{n-|z|}{n-k}\right)/\left(\genfrac{}{}{0ex}{}{n}{k}\right)$。
• 谱在重量轴上以 $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. **（内积公式的特例）**直接由 Lemma 1 计算：(a) $d(x,y)=1$ 时 $⟨{\psi }_x^k|{\psi }_y^k⟩=\frac{n-k}{n}$；(b) $d(x,y)=2$ 时的表达式；(c) 证明 $k=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$，并解释行和的组合意义（提示：固定 $x$，数满足 $x_S=y_S$ 的 $(y,S)$ 对）。
3. **（阶段数）**证明递推 $n_{s-1}=\lceil n_s-\sqrt{n_s}\rceil$ 从 $n$ 降到 $O(\sqrt{n})$ 需要 $\Theta (\sqrt{n})$ 步。要求把 ODE 比较论证补严格（例如证明每一步 $\sqrt{n_s}$ 至少下降一个固定的常数分数以上或至少下降 $\frac{1}{2}-o(1)$），并对 $n=100$ 列出完整序列。
4. **（位查询的不可模拟性）**指出算法四个步骤中哪一步无法用 $O(1)$ 次位查询模拟，并说明：若把每条通配符查询都换成”逐位读取再比较”的实现，整个算法的查询复杂度会退化到什么阶？结合第 1.3 节说明为什么这种退化不是实现技巧的问题。
5. **（经典随机下界）**把第 1.2 节的随机情形论证补全：证明若经典算法以概率 $\ge 2/3$ 输出 $x$，则期望查询数为 $\Omega (n)$。（提示：条件熵 $H(X\mid \text{输出})$ 与 Fano 不等式；每比特答案关于 $X$ 的互信息至多 $1$。）
6. **（对称性与最优性）**定义 $U_z|S⟩|w⟩=|S⟩|w\oplus z_S⟩$。(a) 证明 $\{U_z{\}}_{z\in \{0,1{\}}^n}$ 是一个阿贝尔酉群，且 $U_z|{\psi }_0^k⟩=|{\psi }_z^k⟩$（即态集合几何均匀）；(b) 由此证明 $\sqrt{G}$ 的对角元全相等，并说明这正是第 4.4 节评注 1 中”测量标志不扭曲分支振幅”的根源；(c) 补全第 3.6 节 Step B 中 $\hat{h}(e_i)=-\frac{1}{2}$ 与 $\hat{h}(z)=0(|z|\ge 2)$ 的配对计算。

参考文献

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

---

参考资料

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