通配符搜索：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 无法以一次查询模拟哪一步。

参考文献