# 量子模式匹配：确定性采样、Grover 与平均情形 Hidden Shift

给定文本 $T$（长度 $n$）与模式 $P$（长度 $m\le n$），寻找偏移 $s$ 使

$$
T[s+j]=P[j],\qquad0\le j<m.
$$

最坏情况下，量子查询只能获得平方根级改进；随机文本与模式却可把匹配化为带少量噪声的 hidden shift，出现超多项式平均加速。本课分别推导这两条算法线，并强调 oracle 查询、整串输入和预处理成本的区别。

## 1. 最坏情况基线与下界

字符通过 oracle 访问：查询 $(b,i)$ 返回 $T_i$ 或 $P_i$。验证固定偏移 $s$ 是否匹配，就是在 $m$ 个位置中搜索 mismatch，Grover 需

$$
O(\sqrt m)
$$

次字符查询。再对约 $n$ 个偏移直接 Grover 会得到 $O(\sqrt{nm})$，没有充分利用相邻窗口重叠。

下界包含两个独立来源：把 $m=1$ 化为文本中的无结构搜索得到 $\Omega(\sqrt n)$；把匹配位置固定、只让模式中一位未知得到 $\Omega(\sqrt m)$。所以

$$
\Omega(\sqrt n+\sqrt m)
$$

是自然目标。

## 2. Deterministic sampling 压缩候选偏移

对模式选择一个小样本

$$
S=\{j_1,\ldots,j_r\},\qquad r=O(\log m),
$$

及对应字符 $P[j_a]$。Deterministic sampling 的性质是：在一个长度 $O(m)$ 的候选偏移块中，若模式不是高度周期的，则至多一个偏移同时满足

$$
T[s+j_a]=P[j_a]
\quad\forall j_a\in S.
$$

若模式有短周期，则算法先识别周期并用周期结构把候选组织成少数等差数列；最终仍只需验证常数/对数多个代表。样本不是随机哈希：它根据模式的自重叠结构选择，保证任意文本上成立。

量子构造与使用样本的步骤是：

1. 用 Grover 搜索模式的自不一致位置，逐步建立 $S$，成本 $\widetilde O(\sqrt m)$；
2. 把文本分成 $O(n/m)$ 个重叠块，使任一长度 $m$ 的匹配完整落在某块；
3. 对块做外层 Grover 搜索；块判定器用样本并行排除几乎所有偏移；
4. 对留下的偏移用 Grover 搜索 mismatch，做完整验证。

样本使一个块的候选检查低于“逐偏移 × $\sqrt m$”。外层平方根与块数平衡后，总查询/时间达到

$$
\widetilde O(\sqrt n+\sqrt m),
$$

与下界相差 polylog 因子。

## 3. 为什么随机实例可以快得更多

若 $P,T$ 独立均匀随机，两个不同长度 $m$ 窗口在很多位置同时相同的概率指数小。真实匹配若存在，就像把模式字符串平移到文本某处；窗口边界和偶然字符碰撞形成少量噪声。

把 $d$ 维文本分成大小约 $m^d$ 的块，并对模式与候选块构造局部指纹函数。正确块中的两组指纹满足

$$
g(x)\approx f(x+s),
$$

其中 $s$ 是匹配位置，少量 $x$ 因边界或指纹碰撞不满足。于是块判定器变成 noisy $d$-dimensional hidden shift。

## 4. Kuperberg 筛法怎样处理噪声

理想 injective hidden shift 查询产生带随机频率 $k$ 的相位态

$$
\frac{|0\rangle+e^{2\pi i k\cdot s/M}|1\rangle}{\sqrt2}.
$$

Kuperberg 筛法按频率低位/格桶分组并合并相位态，逐步制造容易读出 $s$ 的频率。模式匹配归约中，错误指纹使部分相位态带噪；算法在每级筛选中限制坏态比例，并用冗余样本保持最终偏差。

外层对约 $(n/m)^d$ 个块做 Grover，平均情形总时间为

$$
\widetilde O\!\left(
(n/m)^{d/2}
2^{O(d^{3/2}\sqrt{\log m})}
\right).
$$

当 $m$ 大于对数尺度且 $d$ 固定，第二因子相对 $m$ 次多项式为次多项式，而经典随机实例仍需检查约 $(n/m)^d$ 个位置或付出 $n^{d/2}$ 级代价，因而可形成超多项式差距。这个结论是**平均情形**，不替代最坏界。

## 5. 三种输入模型必须分开

1. **字符 query 模型：**每次只相干读取一个 $T_i/P_j$，上述 $\widetilde O(\sqrt n+\sqrt m)$ 是查询结论。
2. **随机平均模型：**还承诺 $T,P$ 的分布，才能使用 noisy hidden shift 的唯一性与噪声界。
3. **整串量子输入模型：**若 $n+m$ 个字符已作为量子寄存器整体给出，可以并行门操作字符串；2021 年方案的复杂度不能与逐字符 oracle 查询数直接比较，数据装载已被计入输入。

同时，找到候选后必须做完整验证，否则平均情形指纹碰撞会产生假阳性。验证的 $O(\sqrt m)$ 成本不能从总式中无故删除。

## 6. 小例子

取

$$
T=\texttt{ACGTCGACG},\qquad P=\texttt{TCGA}.
$$

偏移 3 给出 `TCGA`。若样本位置 $S=\{0,2\}$，所需字符为 `T`,`G`；它先过滤绝大多数偏移，但偏移 1 的 `CGCG` 也可能在某些更小样本下幸存。最终 Grover mismatch 检查验证四个位置，保证只输出真实匹配。

## 7. 小结与习题

- 固定偏移验证是 mismatch Grover 搜索；直接嵌套会浪费窗口重叠。
- Deterministic sampling 用模式自重叠结构把每块候选压到很少。
- 随机模式匹配可归约到带噪多维 hidden shift，并使用 Kuperberg 筛法。
- 最坏、平均和整串输入模型的复杂度不可混写。

1. 从无结构搜索构造 $\Omega(\sqrt n)$ 下界实例。
2. 解释高度周期模式为何会破坏“每块至多一个样本匹配偏移”。
3. 对 $d=1$ 化简平均情形复杂度并讨论 $m=\log^2n$。
4. 说明候选指纹匹配后为什么仍需完整 mismatch 验证。

## 参考文献与 Zoo 覆盖

- Zoo 编号 217：Ramesh 与 Vinay, [String Matching in $\widetilde O(\sqrt n+\sqrt m)$ Quantum Time](https://arxiv.org/abs/quant-ph/0011049).
- Zoo 编号 215、66：Ashley Montanaro, [Quantum Pattern Matching Fast on Average](https://arxiv.org/abs/1408.1816)，使用 Kuperberg 筛法。
- Zoo 编号 216：Bennett--Bernstein--Brassard--Vazirani 无结构查询下界。
- Zoo 编号 435：Niroula--Nam 的整串量子输入模型算法。