量子模式匹配

模式匹配（pattern matching，又叫字符串匹配）是计算机科学中最古老、应用最广的问题之一：给定一段文本 $T$（长度为 $n$ 的字符串）与一个模式 $P$（长度为 $m\le n$ 的字符串），寻找一个偏移 $s$，使得把 $P$ 平移到 $T$ 的第 $s$ 个位置后逐字符吻合，即

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

它的 $d$ 维推广（在 $n^d$ 个格点的”高维文本”中寻找一个 $m^d$ 大小的”高维模式”）对应图像匹配等问题，记号上把 $d=1$ 作为特例。

本词条回答一个自然的问题：**量子计算能在多大程度上加速模式匹配？**答案分成两条线，结论非常不同：

• 最坏情形（输入任意）：量子查询复杂度只能拿到平方根级的改进，精确结果是 $\tilde{O}(\sqrt{n}+\sqrt{m})$，与下界 $\Omega (\sqrt{n}+\sqrt{m})$ 只差 polylog 因子。这条线的关键技巧是 deterministic sampling——先对模式本身做少量”侦察”，把每个长度 $O(m)$ 的文本块中值得检查的候选偏移压到常数/对数多个，再让 Grover 搜索只花在真正需要的地方。
• 平均情形（文本与模式独立均匀随机）：随机性使”偶然匹配”的概率指数级小，问题可以被归约为一个带少量噪声的 $d$ 维 hidden shift 问题，用 Kuperberg 筛法求解。结果是相对经典平均情形算法的超多项式加速——这是模式匹配问题中少有的超多项式量子优势，但它依赖输入分布的承诺，不能替代最坏情形的结论。

课程最后强调一件容易被忽略的事：oracle 查询模型、随机平均模型、整串量子输入模型是三本不同的账，三种模型下的复杂度数字不能直接比较，混写是文献阅读中最常见的误读来源。

**前置知识。**本词条假定读者已经掌握的内容，特别是 Grover 算法与振幅放大（迭代次数 $O(\sqrt{N})$、成功概率 ${\sin }^2((2T+1)\theta )$ 那一套分析）、量子 Fourier 变换以及相位估计。hidden shift 问题与 Simon 算法一脉相承；Kuperberg 筛法我们只做结构性介绍。

1. 经典背景：这个问题为什么值得研究

1.1 经典算法做到了什么

模式匹配是早已被”解决”的问题。Knuth–Morris–Pratt 与 Boyer–Moore 等经典算法在最坏情形下用 $O(n+m)$ 时间找到匹配（或报告不存在）；Karp–Rabin 指纹法用滚动哈希把”逐位置比较”变成”逐位置比较哈希值”，实现简单且期望线性时间。既然经典已经是线性的，量子还有什么可做的？

关键在于输入的读取方式。经典算法必须逐字符读入输入，$\Omega (n)$ 次读取是不可逾越的——哪怕只想知道”匹配是否存在”，也可能必须看完几乎整个文本才能下结论。而量子算法可以在 oracle 模型中以叠加方式访问输入：一次”查询”可以同时探问所有位置的字符。Grover 搜索告诉我们，无结构数据库上的量子查询能比经典读取节省平方根倍。模式匹配不是无结构的——相邻窗口共享大量字符、模式内部有自重叠规律——问题就变成了：这些结构能被量子算法利用到什么程度？

1.2 平均情形为什么单独成章

最坏情形只是问题的一半。在大量实际场合（基因序列检索之外的许多语料、随机噪声中的信号定位），把输入建模为随机串是合理的。经典算法对随机输入也做不到比”每个文本块至少看一眼”更好，直觉上仍需检查约 $(n/m{)}^d$ 个块。而随机性恰好消灭了量子算法最头疼的东西——歧义：随机串里两个不同窗口几乎不可能长得很像，于是”模式出现在哪里”变成一个唯一确定的平移量，而这正是量子相位技术（QFT、hidden shift）最擅长提取的对象。最坏情形与平均情形的巨大反差，正是本词条两条算法线的由来。

1.3 历史脉络

• 1996–1997 年，Bennett、Bernstein、Brassard、Vazirani 证明了无结构搜索的量子查询下界 $\Omega (\sqrt{N})$，它直接给出模式匹配下界的一半（见第 3 节）。
• 2000 年，Ramesh 与 Vinay 把经典并行字符串匹配中的 deterministic sampling 思想搬进量子 oracle 模型，给出 $\tilde{O}(\sqrt{n}+\sqrt{m})$ 的最坏情形算法，与下界仅差 polylog 因子。
• 2014 年，Montanaro 证明了平均情形的超多项式加速：随机 $d$ 维模式匹配归约到带噪 hidden shift，用 Kuperberg 筛法求解。
• 2021 年，Niroula 与 Nam 研究了另一种输入模型——整串以量子态形式给出——得到的时间复杂度不能与逐字符 oracle 查询数直接比较（见第 7 节）。

这些文献与文末”参考文献”一节一一对应。

2. Oracle 模型与基本工具

**字符 oracle。**在本词条的大部分篇幅里，输入通过黑盒访问：一次查询指定一对 $(b,i)$，其中 $b\in \{T,P\}$ 指明查文本还是模式，$i$ 是位置；oracle 返回对应字符。量子版本中这是一个酉变换

$$O|b,i⟩|z⟩=|b,i⟩|z\oplus \mathrm{char}(b,i)⟩,$$

其中 $\mathrm{char}(b,i)$ 在 $b=T$ 时为 $T_i$、在 $b=P$ 时为 $P_i$，$\oplus$ 是字符集上的可逆运算（如逐位异或）。算法的查询复杂度是调用 $O$ 的次数；时间复杂度还要计入查询之间的量子门。本词条的算法两者相差至多 polylog 因子，我们用 $\tilde{O}(\cdot )$ 隐藏这些因子。

两个反复使用的工具。

• **Grover 搜索 / 振幅放大。**在 $N$ 个候选中搜索满足某性质的条目，量子查询 $O(\sqrt{N})$ 次；若判定器本身 cost $C$ 次查询，总成本是 $O(\sqrt{N}\cdot C)$ 量级。这是”外层平方根”的来源。
• 嵌套结构的乘法规则。外层 Grover 调用内层判定器时，查询数近似相乘而非相加。这一条看似简单，却是理解为什么”朴素嵌套 Grover”不够好的关键，下一节马上用到。

3. 最坏情形：基线算法与下界

3.1 基线一：固定偏移的验证

先解决一个子问题：**给定一个具体的偏移 $s$，判断它是不是匹配。**这就是在 $m$ 个位置 $\{0,1,\dots ,m-1\}$ 中搜索一个 mismatch——满足 $T[s+j]\ne P[j]$ 的位置 $j$。mismatch 判定一次只需常数次字符查询（查 $T[s+j]$ 与 $P[j]$ 并比较），于是对 $m$ 个位置做 Grover 搜索：

$$\text{验证一个偏移的查询数}=O(\sqrt{m}).$$

若不存在 mismatch，Grover 搜索报告”无解”，$s$ 是匹配；否则输出一个具体的失配位置作为证据。注意这里用的是 Grover 的存在性版本：我们不仅找到失配，还能区分”有”与”没有”。

3.2 基线二：朴素嵌套及其浪费

最直接的完整算法：把”偏移 $s$“也放进 Grover——外层在约 $n$ 个候选偏移中搜索，内层判定器就是上一段的 $O(\sqrt{m})$ 验证。由乘法规则，总查询数为

$$O(\sqrt{n}\cdot \sqrt{m})=O(\sqrt{nm}).$$

这个数字离下界 $\Omega (\sqrt{n}+\sqrt{m})$ 差得远。浪费在哪里？**相邻窗口的重叠被完全无视了。**偏移 $s$ 与偏移 $s+1$ 对应的两个长度-$m$ 窗口共享 $m-1$ 个字符，但朴素算法对每个偏移独立地、从零开始地做 $O(\sqrt{m})$ 次查询的验证，同一批字符被反复查了许多遍。直觉上，对每个偏移都花 $\sqrt{m}$ 太贵了：理想情况下，整块文本的”侦察”应该只做一次，然后用极便宜的方式排除掉几乎所有偏移。第 4 节的 deterministic sampling 正是实现这个直觉的机制。

3.3 下界：$\Omega (\sqrt{n}+\sqrt{m})$ 的两个独立来源

下界由两个互不包含的归约组成，缺一不可。

**来源一：$\Omega (\sqrt{n})$。**取 $m=1$，模式是单个字符，比如 $P=\text{1}$。问题退化为：在长度为 $n$ 的文本中搜索字符 $\text{1}$ 是否出现——这正是无结构搜索问题。由 Bennett–Bernstein–Brassard–Vazirani 的下界，任何量子算法需要 $\Omega (\sqrt{n})$ 次查询。由于 $m=1$ 的模式匹配是一般模式的特例，一般问题的下界不会更低。

来源二：$\Omega (\sqrt{m})$。这次把匹配位置固定（比如告知算法”匹配就在偏移 $0$，如果你能找到的话”），从而 $\sqrt{n}$ 不再是瓶颈；同时把文本固定为全 $\text{0}$。模式 $P$ 取为：除了某一个未知位置 $j^{\ast }$ 上是 $\text{1}$、其余全是 $\text{0}$。那么偏移 $0$ 是否匹配，等价于”这个 $\text{1}$ 是否存在”——又是在 $m$ 个字符中的无结构搜索，需要 $\Omega (\sqrt{m})$ 次对 $P$ 的查询。注意这个归约的巧妙之处：它说明即使算法免费知道所有文本字符、甚至免费知道候选偏移，仅”读懂模式本身”就要付出 $\sqrt{m}$ 的代价。这解释了为什么最终复杂度中 $\sqrt{m}$ 与 $\sqrt{n}$ 是相加而不是取最大：两项各自封锁了一类算法捷径。

合并两个来源：

$$\text{最坏情形查询下界}=\Omega (\sqrt{n}+\sqrt{m}).$$

这是后续所有算法设计的对标线。

一个自然的疑问是：为什么下界不是 $\Omega (\sqrt{nm})$——毕竟算法看起来是”$n$ 个偏移”套”$m$ 个位置”的两层结构？原因在于下界归约必须对所有算法成立，包括利用结构的算法。$\Omega (\sqrt{nm})$ 式的乘积下界只有在”内外两层互不泄露信息”时才成立；而模式匹配的两层恰恰通过窗口重叠深度耦合（3.2 节），任何声称 $\Omega (\sqrt{nm})$ 的归约都必须先排除”样本预处理后内层近乎免费”的可能——第 4 节的算法表明这种预处理真实存在。两个来源各自只在互补的参数区域内封锁捷径（$m=1$ 时封锁文本方向，固定文本时封锁模式方向），它们的正确合并方式是相加而非相乘。最终的上界 $\tilde{O}(\sqrt{n}+\sqrt{m})$ 与这个下界只差 polylog，印证了”和式”才是正确的答案。

4. Deterministic sampling：把候选偏移压到很少

4.1 直觉：模式自身的重叠结构决定了”侦察成本”

考虑这样一个思想实验。假设模式 $P$ 内部”杂乱无章”——它的任何非零平移都与自己对不上（即 $P$ 与 $P$ 平移 $t$ 位后的重叠部分存在失配，对所有 $1\le t<m$ 成立）。那么，假如我们在文本中找到了模式的一个匹配，偏移 $s$ 就被唯一锁定了：偏移 $s+t$（$t\ne 0$）处不可能同时还有一个匹配，因为那样 $P$ 与自身平移 $t$ 位必须完全一致，与假设矛盾。

再进一步：我们其实不需要比较全部 $m$ 个字符来锁定偏移。选一小撮样本位置

$$S=\{j_1,\dots ,j_r\}\subseteq \{0,\dots ,m-1\},r=|S|=O(\log m),$$

连同对应的模式字符 $P[j_a]$。如果一个偏移 $s$ 在所有样本位置上都吻合，即

$$T[s+j_a]=P[j_a]\text{对所有 }{j}_a\in S,$$

称之为 $s$ 通过样本检验。若模式不具备高度的周期结构，$O(\log m)$ 个精心挑选的样本位置所携带的信息，足以在任意一段长度 $O(m)$ 的候选偏移区间里至多放过一个偏移——直觉上，每多一个样本位置，能把”活下来的偏移集合”按模式自重叠的失配结构砍掉至少一个固定比例，对数多个位置便足以收敛到唯一（或零个）候选。

这里必须强调 deterministic sampling 与随机指纹（如 Karp–Rabin）的本质区别：样本不是随机哈希。随机哈希的正确性以高概率对”平均的文本”成立；而这里的样本位置是根据模式自身的自重叠结构确定性地挑选的，其性质——“长度 $O(m)$ 的候选块内至多一个偏移通过检验”——对任意文本无条件成立。这正是它能把最坏情形复杂度（而不是平均情形复杂度）压到下界附近的原因。

我们把这条性质写成一个正式的命题，并给出证明思路，因为它正是整个最坏情形算法的支点。

**Lemma（样本性质，非周期情形）。**设模式 $P$ 不具备高度周期结构（精确含义见下）。则存在样本集合 $S\subseteq \{0,\dots ,m-1\}$，大小 $|S|=O(\log m)$，使得：对任意文本 $T$，在任意长度 $O(m)$ 的候选偏移区间内，至多一个偏移 $s$ 通过样本检验（即 $T[s+j_a]=P[j_a]$ 对所有 $j_a\in S$ 成立）。

**证明思路。**分两步：先说明单个间隔如何被”见证”，再说明少量位置如何见证所有间隔。

*第 1 步：见证一个固定间隔。*取区间内两个偏移 $s$ 与 $s^{\prime }=s+t$（$1\le t=O(m)$），假设它们同时通过样本检验。那么对所有 $j_a\in S$：

$$T[s+j_a]=P[j_a],T[s+t+j_a]=P[j_a].$$

若 $j_a$ 与 $j_a+t$ 都在样本中，把两个等式链接起来：$P[j_a+t]=T[s+t+j_a]$（对 $s$ 用位置 $j_a+t$ 的检验）与 $T[s+t+j_a]=P[j_a]$（对 $s^{\prime }$ 用位置 $j_a$ 的检验），得到

$$P[j_a+t]=P[j_a].$$

也就是说，只要样本集合（连同其平移闭包）包含某个满足 $P[j+t]\ne P[j]$ 的位置 $j$，$s$ 与 $s+t$ 就不可能同时通过检验——这样的 $j$ 称为间隔 $t$ 的见证位置。而”高度周期”正是使见证位置不存在的情形：若对每个 $j$（重叠区内）都有 $P[j+t]=P[j]$，则 $P$ 在重叠区上以 $t$ 为周期。排除这种情形后，每个间隔 $t$ 都至少有一个见证位置。

*第 2 步：少量位置覆盖所有间隔。*区间内可能的间隔 $t$ 有 $O(m)$ 个，每个都需要被见证。注意一个位置可以同时见证许多不同的间隔，因此可以贪心构造：每轮挑一个能见证最多尚未覆盖间隔的位置加入 $S$。标准的覆盖论证（每次至少消灭未覆盖集合的一个固定比例）保证 $O(\log m)$ 轮之后全部 $O(m)$ 个间隔都被覆盖。此时区间内任意两个不同偏移都至少在一个样本位置上冲突，故至多一个通过检验。Q.E.D.（思路）

这个引理也精确了”高度周期”的定义：它就是指第 1 步中某些小间隔 $t$ 不存在见证位置的情形，下一小节专门处理它。

4.2 周期模式是唯一的麻烦

上面的直觉有一个明显的漏洞：如果模式有短周期，比如 $P=\text{aaaa}\cdots \text{a}$，那么任何样本集合都无法区分相差周期整数倍的两个偏移——它们在所有位置上都给出相同的比较结果。“每块至多一个候选”的承诺就此失效。

处理办法是把周期变成朋友而不是敌人。算法先识别模式的最小周期（周期检测本身可以在样本构造过程中一并完成）。一旦知道模式以 $p$ 为周期，一个匹配的出现会迫使一段长度 $\ge m$ 的文本也呈现周期 $p$ 的结构；而在一段周期为 $p$ 的文本区域里，所有匹配偏移天然地排成一个（或少数几个）公差为 $p$ 的等差数列。于是算法不再需要逐个检查偏移，只需对每个等差数列检查一个代表元，其余成员的匹配性由周期性免费推出。最终需要完整验证的代表仍然只有常数/对数多个。换句话说：

• 非高度周期的模式：样本检验直接过滤，每块至多剩一个候选；
• 高度周期的模式：先用周期结构把候选组织成少数等差数列，每个数列验证一个代表。

两种情况殊途同归：每个长度 $O(m)$ 的文本块里，需要认真对待的偏移只有极少个。

4.3 量子算法：四步结构

Ramesh–Vinay 算法把上述经典思想与 Grover 搜索结合为四步。我们逐步说明每一步做什么、为什么需要它、花多少查询。

第 1 步：构造样本（对模式做”自我侦察”）。样本性质要求样本位置能”见证”模式与其平移的失配。构造过程是增量式的：维护当前的候选样本 $S$，用 Grover 在模式中搜索一对自不一致位置——即存在某个平移 $t$，使得 $S$ 尚不能区分平移 $0$ 与平移 $t$、而某个新位置 $j$ 可以——找到就把 $j$ 加入 $S$。每次 Grover 在至多 $O(m)$ 个位置中搜索，成本 $O(\sqrt{m})$；样本最终大小 $r=O(\log m)$，故总成本为

$$O(\log m)\cdot O(\sqrt{m})=\tilde{O}(\sqrt{m}).$$

这一步只查模式 $P$，不查文本——它是预处理。

第 2 步：文本分块。把文本切成 $O(n/m)$ 个长度为 $O(m)$ 的重叠块（相邻块重叠约 $m$ 个字符）。重叠的目的是保证任何长度 $m$ 的匹配窗口完整地落在某一块内部，从而”找匹配”分解为”逐块找匹配”。块数 $O(n/m)$ 是后面外层搜索的空间大小。

**第 3 步：外层 Grover 搜索块，块内用样本过滤。**外层 Grover 在 $O(n/m)$ 个块中搜索”含候选的块”，需要 $O(\sqrt{n/m})$ 次外层迭代。每次迭代的块判定器做两件事：先用样本检验做粗筛——在一个块内，通过样本检验的偏移至多一个（非周期情形）或落在少数等差数列里（周期情形），粗筛本身可以通过对块内偏移和样本位置的嵌套搜索实现，成本控制在 $\tilde{O}(\sqrt{m})$ 量级——再对幸存的候选做下一步的完整验证。关键账目是：样本使一个块的候选检查成本远低于”逐偏移 $\times \sqrt{m}$“（那将是 $\tilde{O}(m^{3/2})$ 甚至更糟），样本检验把”逐偏移”这个因子消灭掉了。

**第 4 步：完整验证。**对第 3 步输出的每个幸存候选偏移，用 3.1 节的 Grover mismatch 搜索验证全部 $m$ 个位置，成本 $O(\sqrt{m})$。候选只有常数/对数多个，这一步总共 $\tilde{O}(\sqrt{m})$。验证不可省略：样本只检查 $r=O(\log m)$ 个位置，通过样本检验不等于真匹配（周期情形尤其如此），必须确认其余位置。

4.4 复杂度汇总：参数如何平衡

把四步的查询数加在一起：

• 第 1 步（预处理）：$\tilde{O}(\sqrt{m})$；
• 第 3 步（主搜索）：外层迭代数 $\times$ 单次块判定成本 $\approx \sqrt{n/m}\times \tilde{O}(\sqrt{m})=\tilde{O}(\sqrt{n/m}\cdot \sqrt{m})=\tilde{O}(\sqrt{n})$；
• 第 4 步（验证）：$\tilde{O}(\sqrt{m})$。

第 3 步的乘法式子值得多看一眼：**块长取 $\Theta (m)$ 是一个被强迫出来的平衡点。**若把块取得更小（块数增多），外层迭代 $\sqrt{\text{块数}}$ 变大；若把块取得更大（块内偏移增多），单次块判定成本上升。取块长 $\Theta (m)$ 使两个因子恰好满足”外层 $\sqrt{n/m}$ 与块内 $\sqrt{m}$ 相乘时 $m$ 对消”，得到 $\sqrt{n}$——这是两因子乘积中 $m$ 完全消去的唯一尺度。

顺带说明 $\tilde{O}$ 隐藏的 polylog 因子来自哪里：块判定器（Grover 套 Grover）本身是有误差概率的，作为外层振幅放大的子程序调用时，需要把单次错误率压到 $1/\mathrm{poly}$ 量级（否则外层 $O(\sqrt{n/m})$ 次调用中错误会累积），这靠 $O(\log n)$ 次重复与多数投票实现；样本构造中 Grover 子程序的成功概率提升同理。这些重复只贡献对数因子。四步合计：

$$\tilde{O}(\sqrt{m})+\tilde{O}(\sqrt{n})+\tilde{O}(\sqrt{m})=\tilde{O}(\sqrt{n}+\sqrt{m}),$$

与 3.3 节的下界 $\Omega (\sqrt{n}+\sqrt{m})$ 之间只差 polylog 因子。最坏情形的查询复杂度至此被钉死：模式匹配在最坏情形下，量子相对经典的加速恰好是平方根级，不会再多。

5. 平均情形：归约到带噪 hidden shift

从现在开始，我们换一个输入承诺：$T$ 与 $P$ 是独立均匀随机的字符串（$d$ 维情形是随机格点阵列）。这个承诺改变了一切。

5.1 随机性消灭了歧义

设字符表大小为 $\sigma \ge 2$。固定两个不同的长度-$m$ 窗口（例如文本中偏移 $s$ 与 $s^{\prime }$ 处的窗口，$s\ne s^{\prime }$），它们逐字符相同的概率可以这样估计：每个位置独立地以概率 $1/\sigma$ 巧合相同，故两个窗口在全部 $m$ 个位置都相同的概率是

$${\sigma }^{-m}=2^{-m{\log }_2\sigma }.$$

更一般地，“在很多位置同时相同”的概率随位置数指数衰减。把估计做完：文本中窗口总数 $O(n)$，窗口对数 $O(n^2)$，由 union bound（概率的并上界：若干事件至少一个发生的概率不超过各自概率之和），存在一对”偶然完全相同”窗口的概率至多为

$$O\left(n^2{\sigma }^{-m}\right).$$

代入一个代表性的尺度 $m=3{\log }_{\sigma }n$：${\sigma }^{-m}={\sigma }^{-3{\log }_{\sigma }n}=n^{-3}$，于是上界变成 $O(n^2\cdot n^{-3})=O(1/n)$，随 $n$ 趋于零。结论是：

**在随机实例中，真实匹配（若存在）在统计意义上是唯一显著的”结构化信号”。**只要 $m$ 略大于 $\log n$ 的尺度，偶然相似就不会构成干扰。

于是问题换了一副面孔：不再是在歧义中做排除法，而是定位一个唯一的平移量 $s$——真实匹配就像把模式字符串平移到文本的某处；窗口边界的截断效应与偶然的字符碰撞，只是叠加在这幅平移图像上的少量噪声。“定位唯一平移”正是 hidden shift 问题的形状。

5.2 分块与指纹：从字符串到函数

为了套用 hidden shift 机器，需要把字符串改写成函数。以 $d$ 维情形为例：把 $d$ 维文本分成大小约 $m^d$ 的块（与模式同尺度），共有约 $(n/m{)}^d$ 个块。对每个候选块定义一个局部指纹函数 $g$：给块内每个位置 $x$ 赋予一个由该位置邻域字符计算出的指纹值 $g(x)$；对模式同样定义指纹函数 $f$。指纹的设计要求是平移协变：如果这个块恰好包含模式在偏移 $s$ 处的一个匹配，那么对块内绝大多数位置 $x$，

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

其中 $\approx$ 的含义是”除少量位置外严格相等”：不满足的位置来自两个来源——一是边界效应（靠近块边缘的位置，其邻域伸出块外，指纹受到块外随机字符的污染），二是指纹碰撞（随机字符偶然算出相同指纹）。由 5.1 节的估计，这两类位置只占很小比例。

这样一来，“判断一个块是否含匹配”转化为：**给定两个函数 $f,g$，判断是否存在平移 $s$ 使 $g(x)\approx f(x+s)$，并在存在时求出 $s$。**这就是带噪声的 $d$ 维 hidden shift 问题（noisy $d$-dimensional hidden shift）。

5.3 理想 hidden shift：相位态从哪来

先把噪声关掉，看理想的 injective hidden shift 问题：给定两个单射函数 $f,g:{\mathbb{Z}}_M^d\to \{\text{指纹值}\}$（量子 oracle 访问），承诺存在 $s\in {\mathbb{Z}}_M^d$ 使 $g(x)=f(x+s)$ 对所有 $x$ 成立，求 $s$。

标准的量子子程序只各查询 $f,g$ 一次（相干地），产出一个携带 $s$ 信息的单量子比特相位态。我们把它完整推导一遍。

第 1 步，制备位置的均匀叠加，并加一个标志位，受控地查询 $f$（标志 $0$）或 $g$（标志 $1$）：

$$\frac{1}{\sqrt{2M^d}}\sum _{x\in {\mathbb{Z}}_M^d}(|0⟩|f(x)⟩+|1⟩|g(x)⟩)|x⟩.$$

（制备过程：对标志位加 Hadamard 得到 $|0⟩+|1⟩$，对位置寄存器做 ${\mathbb{Z}}_M^d$ 上的 QFT 类均匀化，再以标志位为控制分别调用 $f$、$g$ 的 oracle。）

第 2 步，利用单射性观察指纹值寄存器的结构。$f$ 是单射，所以每个指纹值 $v$ 作为 $f$ 的输出恰好出现一次，出现在位置 $x_0=f^{-1}(v)$、标志位 $0$ 的项里；又因为 $g(x)=f(x+s)$，同一个值 $v$ 作为 $g$ 的输出也恰好出现一次，出现在位置 $x_1$ 满足 $g(x_1)=v$，即 $x_1=x_0-s$、标志位 $1$ 的项里。也就是说，每个指纹值 $v$ 在叠加中恰好配出一对：

$$\frac{1}{\sqrt{2}}(|0⟩|v⟩|x_0⟩+|1⟩|v⟩|x_0-s⟩).$$

第 3 步，测量指纹值寄存器。无论测得哪个 $v$（结果是均匀随机的、且不包含 $s$ 的信息，可以丢弃），态坍缩为

$$\frac{1}{\sqrt{2}}(|0⟩|x_0⟩+|1⟩|x_0-s⟩),$$

其中 $x_0$ 是随测量结果均匀随机的。

第 4 步，对位置寄存器做 ${\mathbb{Z}}_M^d$ 上的量子 Fourier 变换，$|x⟩\mapsto \frac{1}{\sqrt{M^d}}{\sum }_k{e}^{2\pi ik\cdot x/M}|k⟩$。作用到上式：

$$\frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{M^d}}\sum _k(e^{2\pi ik\cdot x_0/M}|0⟩+e^{2\pi ik\cdot (x_0-s)/M}|1⟩)|k⟩.$$

第 5 步，测量 $k$（$d$ 维频率，均匀随机）。把公共因子 $e^{2\pi ik\cdot x_0/M}$ 提为全局相位并丢弃，标志位上剩下

$$\frac{|0⟩+e^{-2\pi ik\cdot s/M}|1⟩}{\sqrt{2}}.$$

这正是引言中提到的相位态（指数上的整体符号只是相位约定，无关紧要）。注意这个态的构造逻辑：$s$ 从不单独出现在任何一次测量结果里，它只以相对相位的形式藏在两个正交分支之间——标志位 $|0⟩$ 与 $|1⟩$ 的干涉项。单次测量这个比特只能得到 $s$ 的”一个线性方程的一位信息”，这就是 hidden shift 比 Simon 问题（群为 ${\mathbb{Z}}_2^d$）难得多的原因：${\mathbb{Z}}_M^d$ 上的频率 $k$ 与未知的 $s$ 以连续相位 $e^{2\pi ik\cdot s/M}$ 耦合，读出它需要一整套筛法。

5.4 噪声如何进入相位态

现在把 5.2 节的噪声加回来。指纹不再严格满足 $g(x)=f(x+s)$：少数位置上 $g$ 的值是错的（边界污染或碰撞）。这些坏位置破坏第 2 步的配对结构——一个错误的 $g$ 值可能找不到配对（坍缩后得不到干涉态）、或与错误的位置配对（相位里的平移量不是 $s$）。结果是：每次运行子程序，以小概率产出一个”坏相位态”（不携带正确的 $s$，或携带错误的相位），其余时候产出好相位态。5.1 节的随机性估计保证坏态比例可以被压得很小，但不为零。

这个噪声界是模型依赖的：它依赖”文本与模式独立均匀随机”这一分布承诺，以及指纹函数的构造细节；原文献中对噪声传播的分析带有启发式成分。这也是为什么本节的结论严格限定为平均情形结论。

6. Kuperberg 筛法：从相位态里筛出 $s$

6.1 筛法的思想

我们现在拥有的是一台”相位态工厂”：每按一次按钮，得到一个态 $\frac{1}{\sqrt{2}}(|0⟩+e^{2\pi ik\cdot s/M}|1⟩)$，其中 $k$ 已知、均匀随机，$s$ 是同一个未知量。如何从大量这样的态中提取 $s$？

朴素的相位估计在这里效率不够：随机的 $k$ 意味着每次样本的频率不同，无法直接累加同一频率的相位。Kuperberg 筛法的策略是制造可控的频率，分三个环节：

**环节一：分桶。**收集一大批相位态，按频率 $k$ 的低位数字（在适当选取的进制下）或更一般的格结构分进不同的桶；同一桶内的态具有相同（或相近）的低位频率分量。

环节二：合并。取同桶的两个态做联合测量，两个相位相消/相加，产生一个新相位态，其频率是两个旧频率之差（或之和）——低位数字被”筛掉”了，即新频率落在更小的格上。这一步值得把计算写出来。为书写简单取 $d=1$，记 ${\theta }_j=2\pi k_{j}s/M$，两个输入态的张量积为

$$\frac{1}{2}(|00⟩+e^{i{\theta }_2}|01⟩+e^{i{\theta }_1}|10⟩+e^{i({\theta }_1+{\theta }_2)}|11⟩).$$

按两个比特的奇偶性把四项重新分组：偶宇称项 $|00⟩+e^{i({\theta }_1+{\theta }_2)}|11⟩$ 与奇宇称项 $e^{i{\theta }_2}|01⟩+e^{i{\theta }_1}|10⟩$。做一次奇偶测量（等价的 Bell 基测量），各以 $1/2$ 概率落到一组：

• 落到偶宇称：归一化后施加 CNOT，$|00⟩+e^{i({\theta }_1+{\theta }_2)}|11⟩\mapsto (|0⟩+e^{i({\theta }_1+{\theta }_2)}|1⟩)|0⟩$，得到频率为 $k_1+k_2$ 的新相位态；
• 落到奇宇称：提出公共因子 $e^{i{\theta }_2}$ 后同理，得到相对相位 ${\theta }_1-{\theta }_2$，即频率为 $k_1-k_2$ 的新相位态。

所以每次合并消耗两个旧态，以各半的概率产出频率为 $k_1\pm k_2$ 的一个新态。只要配对时选择低位数字相同的两个态，差频 $k_1-k_2$ 的低位数字就是零——频率被”准直”到更细的格上，这正是分桶的意义。 3. **逐级推进。**把新态送入下一级，再按新的低位分桶、再合并。每过一级，频率的可取值范围按进制收缩；经过 $O(\sqrt{\log M})$ 量级的级数后，频率被”准直到”少数几个特殊值上，对这些终态做测量即可读出 $s$ 的一位或一个数字。重复整个过程恢复 $s$ 的全部数字。

为了让每一级都有足够多的态存活（合并有损耗、成功率不是 1），工厂需要总共生产 $2^{O(\sqrt{\log M})}$ 个相位态——这是筛法的样本复杂度，也是 hidden shift 问题著名的次指数 $2^{O(\sqrt{\log M})}$（对比 Simon 问题的多项式）的来源。

这个指数里的 $\sqrt{\log M}$ 也是一个参数平衡的结果，值得把账算出来。设把频率按某个进制的数字来筛，每一级筛掉 $\ell$ 个数字。两个相互牵制的要求是：

• **桶要装得满。**按 $\ell$ 个数字分桶，桶的数量约为 $2^{\Theta (\ell )}$（$d$ 维情形为 $2^{\Theta (d\ell )}$）；要让多数桶里至少有两个态可供配对合并，每一级开始时要储备 $2^{\Theta (\ell )}$ 个相位态。
• **级数不能太多。**频率共有 $O(\log M)$ 个数字，每级筛掉 $\ell$ 个，故级数为 $L=O(\log M/\ell )$。每一级都要用上一级的产出重新凑齐储备，消耗随级数复合增长，总样本数约为 $2^{\Theta (\ell )}\cdot 2^{\Theta (L)}$ 量级。

总指数形如 $\Theta (\ell )+\Theta (\log M/\ell )$。这是经典的”和式最小化”：两项一个随 $\ell$ 增、一个随 $\ell$ 减，平衡点在两项同阶处。令 $\ell \approx \log M/\ell$，解出 $\ell \approx \sqrt{\log M}$，代回得总指数 $\Theta (\sqrt{\log M})$，即总样本与时间 $2^{O(\sqrt{\log M})}$（$d$ 维情形的额外因子见 6.3 节）。取 $\ell$ 更小则级数失控，取 $\ell$ 更大则单级储备失控——$\sqrt{\log M}$ 是唯一的平衡尺度，其推导逻辑与 4.4 节”块长取 $\Theta (m)$“完全同构。

6.2 噪声下的筛法

模式匹配归约给出的不是理想工厂：每批相位态里混着少量坏态（5.4 节）。坏态参与合并时，可能把好态”带坏”——两个好态合并出好态，一个好一个坏则产出坏态。因此坏态比例会随级数增长，筛法必须控制这种扩散：

• **入口把关。**利用 5.1 节的估计选择指纹参数，使初始坏态比例足够小；
• **每级限制坏态比例。**在每一级筛选中追踪坏态比例的上界，保证经过 $O(\sqrt{\log M})$ 级后仍未失控；
• **冗余样本。**最终读出 $s$ 的每一位时，不用单次测量，而是用多份终态做投票/冗余采样，把残余偏差压到可接受的水平。

这些步骤在原文献中的分析是启发式的、依赖随机性假设的——这一点在引用结论时必须保留。

6.3 平均情形复杂度：逐项拆解

现在把完整的平均情形算法组装起来并算账。算法结构：外层 Grover 在约 $(n/m{)}^d$ 个块中搜索”含匹配的块”，块判定器是上一节的 noisy hidden shift 求解。

**因子一：$(n/m{)}^{d/2}$。**外层 Grover 的迭代数是搜索空间的平方根：$\sqrt{(n/m{)}^d}=(n/m{)}^{d/2}$。这是”块数开根号”，与第 4 节最坏情形算法外层 $\sqrt{n/m}$ 完全同构（那里 $d=1$）。

**因子二：$2^{O(d^{3/2}\sqrt{\log m})}$。**这是单次块判定器（Kuperberg 筛法）的成本。来源追踪：块的边长量级是 $m$（$d$ 维块含约 $m^d$ 个位置），hidden shift 所在的群大小 $M$ 满足 $\log M\approx d\log m$；筛法的样本/时间复杂度是

$$2^{O(\sqrt{\log M})}\text{（每维）},$$

$d$ 维情形的开销在各维间复合，给出指数 $O(d\cdot \sqrt{d\log m})=O\left(d^{3/2}\sqrt{\log m}\right)$，即总因子 $2^{O(d^{3/2}\sqrt{\log m})}$。再乘上指纹计算、坏态控制与冗余采样的多项式/polylog 开销（被吸收进 $\tilde{O}$）。

**总式。**两因子相乘：

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

为什么说这是超多项式加速？固定 $d$，让 $m$ 增长但不超过 $n$ 的适当尺度。第二个因子 $2^{O(d^{3/2}\sqrt{\log m})}$ 相对 $m$ 的任何多项式 $m^c$ 都是次多项式的：取对数比较，$O(\sqrt{\log m})$ 对比 $c\log m$，前者是后者的低阶无穷小。而经典随机实例算法必须对每个块至少看一眼，仍需检查约 $(n/m{)}^d$ 个位置，或付出 $n^{d/2}$ 级别的代价。于是量子与经典平均情形成本之比大约是

$$\frac{(n/m{)}^{d/2}\cdot (\text{次多项式因子})}{(n/m{)}^d}=\frac{(\text{次多项式因子})}{(n/m{)}^{d/2}},$$

只要 $m$ 大于对数尺度使块数 $(n/m{)}^d$ 仍充分大，分母的多项式增长压过分子的次多项式增长，比值趋于零——超多项式差距。

保留条款（必须随结论一起引用）。第一，这是平均情形结果，依赖 $T,P$ 独立均匀随机的承诺，不替代、也不否定第 3–4 节的最坏情形界 $\tilde{\Theta }(\sqrt{n}+\sqrt{m})$——对手写的输入仍然只有平方根加速。第二，噪声传播分析是启发式的、模型依赖的。第三，找到候选块后仍需完整验证（见下一节）。

7. 三种输入模型必须分开

模式匹配的量子文献中出现过三种输入设定，它们的复杂度数字不可混写：

1. 字符 query 模型（本词条主要模型）。每次查询只相干读取一个字符 $T_i$ 或 $P_j$。$\tilde{O}(\sqrt{n}+\sqrt{m})$ 是这个模型下的查询复杂度结论；由于每次查询后只做 polylog 的辅助计算，它也是时间复杂度（相差 polylog）。
2. 随机平均模型。在 query 模型之上，还承诺 $T,P$ 的分布（独立均匀随机）。没有这个承诺，5.1 节的碰撞概率估计、5.4 节的噪声界都无从谈起，noisy hidden shift 归约的唯一性也就失效。这是第 5–6 节超多项式加速的适用前提。
3. 整串量子输入模型。若 $n+m$ 个字符已经作为一个量子寄存器整体给出（例如数据本就在量子内存中），算法可以对整个字符串施加并行门操作。2021 年 Niroula–Nam 的方案工作在这个模型下，其复杂度数字不能与逐字符 oracle 查询数直接比较——数据装载成本已被计入输入本身，而不是算法运行时间。把它与 $\tilde{O}(\sqrt{n}+\sqrt{m})$ 并列比较，相当于比较两本不同的账。

另一个贯穿所有模型的纪律：**找到候选后必须做完整验证。**最坏情形中，样本检验只查了 $O(\log m)$ 个位置；平均情形中，指纹碰撞以小概率产生假阳性候选块。两种情况下，候选都不等于答案，验证的 $O(\sqrt{m})$ 成本（Grover mismatch 搜索）不能从总式中无故删除——好在它已经被主导项吸收。

下表把三种模型的承诺与结论并列，便于查阅：

模型	输入承诺	度量	本词条结论
字符 query	无（最坏输入）	oracle 查询数 / 时间	$\tilde{\Theta }(\sqrt{n}+\sqrt{m})$（差 polylog）
随机平均	$T,P$ 独立均匀随机	期望时间	$\tilde{O}((n/m{)}^{d/2}{2}^{O(d^{3/2}\sqrt{\log m})})$，超多项式加速
整串量子输入	字符串已在量子寄存器中	门操作数	数字与查询复杂度不具可比性（Niroula–Nam）

8. 小例子：样本过滤与验证的完整手算

取字符表 $\{\text{A},\text{C},\text{G},\text{T}\}$（$\sigma =4$）上的

$$T=\text{ACGTCGACG}(n=9),P=\text{TCGA}(m=4).$$

位置从 $0$ 开始编号，$T$ 的各字符为 $T_0\cdots T_8=\text{A,C,G,T,C,G,A,C,G}$。合法的偏移范围是 $0\le s\le n-m=5$。

**第 1 步：直接确认匹配位置。**逐个检查六个偏移处的窗口：

$s$	窗口 $T[s..s+3]$	等于 $P=\text{TCGA}$？
0	ACGT	否
1	CGTC	否
2	GTCG	否
3	TCGA	是
4	CGAC	否
5	GACG	否

偏移 $s=3$ 是唯一的匹配。

**第 2 步：样本检验。**取样本位置 $S=\{0,2\}$，所需的模式字符为 $P[0]=\text{T}$、$P[2]=\text{G}$。偏移 $s$ 通过样本检验当且仅当 $T_s=\text{T}$ 且 $T_{s+2}=\text{G}$。逐个检查：

$s$	$T_s$	$=\text{T}$？	$T_{s+2}$	$=\text{G}$？	通过？
0	A	否	G	是	否
1	C	否	T	否	否
2	G	否	C	否	否
3	T	是	G	是	是
4	C	否	A	否	否
5	G	否	C	否	否

两个样本位置就把六个候选过滤到只剩 $s=3$。这个例子也说明了样本大小的意义：若只用更小的样本 $S=\{2\}$（只要求 $T_{s+2}=\text{G}$），则 $s=0$（$T_2=\text{G}$）与 $s=3$（$T_5=\text{G}$）都幸存——样本少一个位置，候选就多漏一个，剩下的要靠验证兜住。

**第 3 步：完整验证。**对幸存的 $s=3$ 做 mismatch 检查：在 $j\in \{0,1,2,3\}$ 中搜索 $T[3+j]\ne P[j]$ 的位置。逐对比较：$(\text{T},\text{T})$、$(\text{C},\text{C})$、$(\text{G},\text{G})$、$(\text{A},\text{A})$——四个位置全部吻合，搜索无解，确认 $s=3$ 是真匹配。在量子算法中，这一步是对 $m=4$ 个位置的 Grover 搜索，$O(\sqrt{4})=O(2)$ 次查询量级，而不是逐位置的四次。

**对照 5.1 节的估计。**两个随机窗口全部 $m=4$ 个位置碰巧相同的概率是 $4^{-4}=1/256$；文本里只有六个窗口，所以本例中”偶然匹配”并不罕见地被样本检验捕获——这正是小例子与渐近情形的差距：渐近分析中 $m\gg \log n$，偶然碰撞才指数罕见。

**成本对照（数量级感受）。**在这个 $n=9,m=4$ 的小实例上，朴素嵌套 Grover（3.2 节）的查询量级是 $\sqrt{n-m+1}\times \sqrt{m}=\sqrt{6}\times 2\approx 4.9$ 次”单位判定”，即对每个外层候选都要付一次完整的 $\sqrt{m}$ 验证；而样本方案的形状是：用两个样本位置（第 2 步）以每偏移 $O(1)$ 次查询的代价筛掉五个偏移，再对唯一幸存者付一次 $O(\sqrt{m})=O(2)$ 的验证（第 3 步）。小例子里两者只差常数，但渐近地前者是 $\sqrt{nm}$、后者是 $\sqrt{n}+\sqrt{m}$，差距随 $m$ 增长而拉开——这正是”利用窗口重叠”省下的那个因子。

9. 小结与习题

小结。

• 固定偏移的匹配验证是 $m$ 个位置上的 mismatch Grover 搜索，成本 $O(\sqrt{m})$；直接对偏移嵌套 Grover 得 $O(\sqrt{nm})$，浪费在无视相邻窗口的重叠。
• 最坏情形下界 $\Omega (\sqrt{n}+\sqrt{m})$ 有两个独立来源：文本中的无结构搜索（$m=1$ 特例）与模式自身的读取成本（固定偏移、固定文本的归约）。
• Deterministic sampling 依据模式的自重叠结构确定性地选取 $O(\log m)$ 个样本位置，把每个长度 $O(m)$ 的文本块的候选偏移压到至多一个（非周期模式）或少数等差数列（周期模式）；配以外层 Grover（$\sqrt{n/m}$ 次迭代）与块内 $\tilde{O}(\sqrt{m})$ 判定，两因子相乘时 $m$ 对消，总复杂度 $\tilde{O}(\sqrt{n}+\sqrt{m})$，与下界只差 polylog。
• 随机（平均情形）模式匹配可归约到带噪 $d$ 维 hidden shift：随机性使偶然匹配指数罕见，真实匹配化为唯一平移 $s$；单射 hidden shift 的单次量子采样产生相位态 $\frac{1}{\sqrt{2}}(|0⟩+e^{2\pi ik\cdot s/M}|1⟩)$，Kuperberg 筛法以 $2^{O(d^{3/2}\sqrt{\log m})}$ 的成本从中提取 $s$，外层 Grover 贡献 $(n/m{)}^{d/2}$。
• 平均情形结论是超多项式加速，但它是分布承诺下的结果（噪声分析带启发式成分），不替代最坏界；字符 query、随机平均、整串量子输入是三种不可混写的模型；任何模型下候选都必须经过 $O(\sqrt{m})$ 的完整验证。

习题。

1. **（下界归约）**详细写出 3.3 节来源一的归约：给定一个解决一般模式匹配问题、查询数为 $Q(n,m)$ 的量子算法，如何用它以 $Q(n,1)$ 次查询解决”长度 $n$ 的 $01$ 串是否含 $\text{1}$“？由此说明 $Q(n,m)=\Omega (\sqrt{n})$。再问：为什么同一个归约不能同时给出 $\Omega (\sqrt{nm})$？
2. （周期模式）取 $P=\text{abababab}$（$m=8$，周期 $p=2$）。任取一个不包含位置 $0$ 与 $1$ 的样本集合 $S$，证明存在两个相差 $2$ 的偏移在任何以周期 $2$ 重复 $\text{ab}$ 的文本段上同时通过样本检验。这说明”每块至多一个候选”对周期模式必然失效；再简述识别周期后为什么只需验证一个代表偏移。
3. **（相位态推导）**补全 5.3 节推导的两个细节：(a) 说明第 1 步的叠加态如何用一次受控 $f$ 查询与一次受控 $g$ 查询制备；(b) 验证第 5 步中”测得任意 $k$ 的概率相同”，并解释为什么 $k$ 的测量结果本身不泄露 $s$。
4. **（复杂度化简）**在平均情形总式 $\tilde{O}((n/m{)}^{d/2}{2}^{O(d^{3/2}\sqrt{\log m})})$ 中取 $d=1$，写出化简后的式子；再令 $m={\log }^{2}n$（设文本足够长使 $n/m$ 仍为 $n$ 的多项式），比较量子成本与经典约 $n/m$ 次块检查的成本，指出超多项式差距来自哪个因子。
5. **（次多项式因子）**证明：对任何常数 $c>0$ 与固定的 $d$，$2^{O(d^{3/2}\sqrt{\log m})}=o(m^c)$。（提示：两边取对数。）这个事实是”第二因子次多项式”的严格含义。
6. **（验证不可省略）**构造一个小规模例子（字符表、文本、模式、样本集合自选），使得某个非匹配偏移通过了样本检验。由此说明：为什么无论最坏情形还是平均情形，候选指纹/样本匹配之后都必须做完整的 mismatch 验证，$O(\sqrt{m})$ 的验证成本不能从总式中删除。

参考文献与 Zoo 覆盖

• Zoo 编号 217：Ramesh 与 Vinay, String Matching in $\tilde{O}(\sqrt{n}+\sqrt{m})$ Quantum Time.
• Zoo 编号 215、66：Ashley Montanaro, Quantum Pattern Matching Fast on Average，使用 Kuperberg 筛法。
• Zoo 编号 216：Bennett—Bernstein—Brassard—Vazirani 无结构查询下界。
• Zoo 编号 435：Niroula—Nam 的整串量子输入模型算法。

---

参考资料

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