量子模式匹配：确定性采样、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 覆盖