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

给定未知串 $x\in\{0,1\}^n$，普通 oracle 一次只读一位，量子完整恢复仍需约 $n/2$ 次查询。通配符 oracle 更强：一次可提交任意子集 $S$ 和候选子串 $y$，询问 $x_S=y$ 是否整体成立。经典回答仍只有一比特，故需 $\Omega(n)$ 次；量子算法通过状态判别与整段验证，以 $O(\sqrt n\log n)$ 期望查询恢复全部 $x$。

## 1. Oracle 模型

查询由

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

指定，返回

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

等价地，用 $s\in\{0,1,*\}^n$ 表示：`*` 位置不检查，其余位置必须与 $x$ 相同。量子 oracle 为

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

若 $|S|=1$ 就退化成普通 bit query。经典每次只获得 yes/no，区分 $2^n$ 个串至少需要 $n$ 比特答案。

## 2. 核心状态判别问题

定义

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

若 $k=n-c\sqrt n$，这个态在叠加中包含“所有缺少约 $c\sqrt n$ 位的视图”。两个字符串 $x,y$ 的态内积只依赖 Hamming 距离 $d(x,y)$：

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

只有当所选 $S$ 完全避开所有差异位时两项才重合。

由于 Gram 矩阵仅依赖 $x\oplus y$，它由 $\mathbb Z_2^n$ Fourier 变换对角化。Pretty-Good Measurement（PGM）使用

$$
M_x=\rho^{-1/2}
|\psi_x^k\rangle\langle\psi_x^k|
\rho^{-1/2},
\qquad
\rho=\sum_x|\psi_x^k\rangle\langle\psi_x^k|.
$$

对上述 $k$，Fourier 特征值分析表明 PGM 输出 $\widetilde x$ 满足

$$
\mathbb E[d(x,\widetilde x)]=O(1).
$$

经典拿到任意固定的 $k$ 位后还要猜 $\Theta(\sqrt n)$ 位；PGM 利用“缺失位置也处于叠加”产生的非正交态整体结构，把错误压到常数个。

## 3. 怎样从小子集态逐步长大

构造序列

$$
n_0=O(\sqrt n),\qquad
n_s-n_{s-1}\approx\sqrt{n_s},\qquad
n_L=n,
$$

所以阶段数 $L=O(\sqrt n)$。

**初始阶段：**均匀叠加所有 $n_0$ 元子集，并用 singleton wildcard queries 逐一写入 $x_i$，花 $O(\sqrt n)$ 次，得到 $|\psi_x^{n_0}\rangle$。

**扩张阶段：**假设已有 $|\psi_x^{n_{s-1}}\rangle$。

1. 相干嵌入到所有 $n_s$ 元超集 $S'$，使内部寄存器是 $S'$ 内随机 $n_{s-1}$ 子集及其真值。
2. 在每个 $S'$ 分支上执行 PGM，得到对整个 $x_{S'}$ 的猜测 $\widetilde x_{S'}$；期望只有 $O(1)$ 个错误。
3. 用一次 wildcard query 验证整段猜测是否完全正确。
4. 若错误，对候选位置做相干二分：查询前半段是否全对，递归定位一个 mismatch，花 $O(\log n)$ 次；翻转该猜测位并重新验证。
5. 期望修正常数个错误后，清除 PGM garbage，得到 $|\psi_x^{n_s}\rangle$。

每阶段期望 $O(\log n)$ 查询，最终 $n_L=n$ 时第二寄存器就是完整 $x$。

## 4. 总复杂度与下界

总期望查询数

$$
O(\sqrt n)
+O(\sqrt n)\cdot O(\log n)
=O(\sqrt n\log n).
$$

“期望”针对最坏输入上的内部测量/修错随机性，不是假设 $x$ 随机。截断过长运行并重复可转成有界错误最坏界，付出常数或对数放大。

量子下界为 $\Omega(\sqrt n)$。可把 Grover 搜索或适当 adversary 实例嵌入：若只在一个位置改变隐藏串，区分所有候选仍要求平方根次整体 equality queries。因此算法近最优，只差 $\log n$。

## 5. 与普通 oracle 和 group testing 的区别

普通 oracle 允许询问“第 $i$ 位是什么”，却不能一次验证一个长候选子串。这里二分修错每一步都依赖“某一半是否全部正确”的 wildcard query；不能在普通模型中免费模拟。

Combinatorial group testing 查询的是

$$
\operatorname{OR}_{i\in S}x_i,
$$

并承诺 $|x|\le k$。它能表示某些 wildcard 实例，但 oracle 语义相反且有稀疏承诺。早期把二者直接归约得到更强上界的论证曾被修正；可靠结论是 wildcard $O(\sqrt n\log n)$，group testing 有自己的 $O(k\log k)$ 算法。

## 6. 小例子

设 $x=101101$。查询

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

（从 1 编号）检查 $x_S=1111$，实际为 $1111$，返回 1。若 PGM 猜测整串为 `101001`，一次全串查询发现错误；二分查询前三位正确、后半错误，再查询位置 4--5，可定位第 4 位并修正，而不是逐位扫描六次。

## 7. 小结与习题

- 子集态的 Gram 矩阵只依赖 Hamming 距离，可由 Boolean Fourier 变换分析。
- PGM 从缺少 $O(\sqrt n)$ 位的叠加视图恢复一个只有常数错误的整串猜测。
- Wildcard equality query 验证整段，并用二分在 $O(\log n)$ 查询内定位错误。
- $O(\sqrt n)$ 个扩张阶段给出 $O(\sqrt n\log n)$ 期望复杂度。

1. 推导两个子集态的内积公式。
2. 说明 $k=n$ 时这些态为何完全正交。
3. 解近似递推 $n_s-n_{s-1}=\sqrt{n_s}$，估计阶段数。
4. 指出普通 bit oracle 无法以一次查询模拟哪一步。

## 参考文献

- Zoo 编号 167：Andris Ambainis 与 Ashley Montanaro, [Quantum Algorithms for Search with Wildcards and Combinatorial Group Testing](https://arxiv.org/abs/1210.1148).