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

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

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

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

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

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

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

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

:::{admonition} 本课知识点
:class: tip

1. **[字符 oracle 模型与嵌套 Grover 的代价规则](#oracle-model-nested-cost)**——能写出字符 oracle 的酉作用式、区分查询复杂度与时间复杂度，并用乘法规则计算嵌套 Grover 结构的总查询数。
2. **[最坏情形基线与下界](#worst-case-baseline-lower-bound)**——能用 Grover mismatch 搜索验证单个偏移并计算朴素嵌套的 $O(\sqrt{nm})$，再构造两个归约证明下界 $\Omega(\sqrt n+\sqrt m)$，并解释两项为何相加而非相乘。
3. **[样本性质与周期模式的处理](#deterministic-sampling-lemma)**——能陈述样本性质引理、用见证位置与贪心覆盖给出证明思路，并解释周期模式为何是唯一例外、如何用等差数列把验证压缩到代表元。
4. **[四步算法与参数平衡](#four-step-algorithm)**——能列出 Ramesh–Vinay 算法的四步及各自查询成本，推导块长 $\Theta(m)$ 如何让 $m$ 在两因子相乘时对消，得到 $\widetilde O(\sqrt n+\sqrt m)$。
5. **[随机性消灭歧义与带噪 hidden shift 归约](#randomness-kills-ambiguity)**——能用逐位置巧合概率 $\sigma^{-m}$ 与 union bound 估计偶然匹配的概率上界，并把"块内找匹配"改写成带噪声的 hidden shift 问题。
6. **[相位态的制备与噪声](#phase-state-derivation-pattern-matching)**——能补全从均匀叠加、受控 oracle 到测量指纹值、QFT 的五步推导，写出相位态 $\frac{1}{\sqrt2}(|0\rangle+e^{2\pi ik\cdot s/M}|1\rangle)$，并说明坏相位态的来源。
7. **[Kuperberg 筛法与平均情形复杂度](#kuperberg-sieve)**——能解释分桶、合并、逐级推进三环节，完成宇称测量的合并计算并推导平衡点 $\ell\approx\sqrt{\log M}$，把总式拆成 $(n/m)^{d/2}\cdot 2^{O(d^{3/2}\sqrt{\log m})}$ 并说明超多项式加速的保留条款。
8. **[三种输入模型与完整验证](#three-input-models)**——能列出字符 query、随机平均、整串量子输入三种模型的输入承诺、复杂度度量与结论，解释三者的数字为何不可混写，以及候选偏移为何必须完整验证。

:::

## 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 模型，给出 $\widetilde O(\sqrt n+\sqrt m)$ 的最坏情形算法，与下界仅差 polylog 因子。
- 2014 年，Montanaro 证明了平均情形的超多项式加速：随机 $d$ 维模式匹配归约到带噪 hidden shift，用 Kuperberg 筛法求解。
- 2021 年，Niroula 与 Nam 研究了另一种输入模型——整串以量子态形式给出——得到的时间复杂度不能与逐字符 oracle 查询数直接比较（见第 7 节）。

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

(oracle-model-nested-cost)=
## 2. Oracle 模型与基本工具

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

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

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

**两个反复使用的工具。**

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

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

(worst-case-baseline-lower-bound)=
### 3.1 基线一：固定偏移的验证

先解决一个子问题：**给定一个具体的偏移 $s$，判断它是不是匹配。**这就是在 $m$ 个位置 $\{0,1,\ldots,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=\texttt{1}$。问题退化为：在长度为 $n$ 的文本中搜索字符 $\texttt{1}$ 是否出现——这正是无结构搜索问题。由 Bennett–Bernstein–Brassard–Vazirani 的下界，任何量子算法需要 $\Omega(\sqrt n)$ 次查询。由于 $m=1$ 的模式匹配是一般模式的特例，一般问题的下界不会更低。

**来源二：$\Omega(\sqrt m)$。**这次把匹配位置**固定**（比如告知算法"匹配就在偏移 $0$，如果你能找到的话"），从而 $\sqrt n$ 不再是瓶颈；同时把文本固定为全 $\texttt{0}$。模式 $P$ 取为：除了某一个未知位置 $j^*$ 上是 $\texttt{1}$、其余全是 $\texttt{0}$。那么偏移 $0$ 是否匹配，等价于"这个 $\texttt{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$ 时封锁文本方向，固定文本时封锁模式方向），它们的正确合并方式是相加而非相乘。最终的上界 $\widetilde O(\sqrt n+\sqrt m)$ 与这个下界只差 polylog，印证了"和式"才是正确的答案。

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

(deterministic-sampling-lemma)=
### 4.1 直觉：模式自身的重叠结构决定了"侦察成本"

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

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

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

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

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

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

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

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

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

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

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

$$
T[s+j_a]=P[j_a],\qquad 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'$ 用位置 $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=\texttt{aaaa}\cdots\texttt{a}$，那么任何样本集合都无法区分相差周期整数倍的两个偏移——它们在所有位置上都给出相同的比较结果。"每块至多一个候选"的承诺就此失效。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(randomness-kills-ambiguity)=
### 5.1 随机性消灭了歧义

设字符表大小为 $\sigma\ge 2$。固定两个不同的长度-$m$ 窗口（例如文本中偏移 $s$ 与 $s'$ 处的窗口，$s\ne s'$），它们逐字符相同的概率可以这样估计：每个位置独立地以概率 $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）。

(phase-state-derivation-pattern-matching)=
### 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}\Big(|0\rangle|f(x)\rangle+|1\rangle|g(x)\rangle\Big)|x\rangle.
$$

（制备过程：对标志位加 Hadamard 得到 $|0\rangle+|1\rangle$，对位置寄存器做 $\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}{\sqrt2}\Big(|0\rangle|v\rangle|x_0\rangle+|1\rangle|v\rangle|x_0-s\rangle\Big).
$$

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

$$
\frac{1}{\sqrt2}\Big(|0\rangle|x_0\rangle+|1\rangle|x_0-s\rangle\Big),
$$

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

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

$$
\frac{1}{\sqrt2}\cdot\frac{1}{\sqrt{M^d}}\sum_{k}\Big(e^{2\pi i k\cdot x_0/M}|0\rangle+e^{2\pi i k\cdot(x_0-s)/M}|1\rangle\Big)|k\rangle.
$$

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

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

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

### 5.4 噪声如何进入相位态

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

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

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

(kuperberg-sieve)=
### 6.1 筛法的思想

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

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

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

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

$$
\frac{1}{2}\Big(|00\rangle+e^{i\theta_2}|01\rangle+e^{i\theta_1}|10\rangle+e^{i(\theta_1+\theta_2)}|11\rangle\Big).
$$

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

- 落到偶宇称：归一化后施加 CNOT，$|00\rangle+e^{i(\theta_1+\theta_2)}|11\rangle\mapsto\big(|0\rangle+e^{i(\theta_1+\theta_2)}|1\rangle\big)|0\rangle$，得到频率为 $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})}\quad\text{（每维）},
$$

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

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

$$
\widetilde 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 节的最坏情形界 $\widetilde\Theta(\sqrt n+\sqrt m)$——对手写的输入仍然只有平方根加速。第二，噪声传播分析是启发式的、模型依赖的。第三，找到候选块后仍需完整验证（见下一节）。

(three-input-models)=
## 7. 三种输入模型必须分开

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

1. **字符 query 模型（本课主要模型）。**每次查询只相干读取**一个**字符 $T_i$ 或 $P_j$。$\widetilde 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 查询数直接比较——**数据装载成本已被计入输入本身**，而不是算法运行时间。把它与 $\widetilde O(\sqrt n+\sqrt m)$ 并列比较，相当于比较两本不同的账。

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

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

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

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

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

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

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

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

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

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

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

| $s$ | $T_s$ | $=\texttt{T}$？ | $T_{s+2}$ | $=\texttt{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}=\texttt{G}$），则 $s=0$（$T_2=\texttt{G}$）与 $s=3$（$T_5=\texttt{G}$）都幸存——样本少一个位置，候选就多漏一个，剩下的要靠验证兜住。

**第 3 步：完整验证。**对幸存的 $s=3$ 做 mismatch 检查：在 $j\in\{0,1,2,3\}$ 中搜索 $T[3+j]\ne P[j]$ 的位置。逐对比较：$(\texttt{T},\texttt{T})$、$(\texttt{C},\texttt{C})$、$(\texttt{G},\texttt{G})$、$(\texttt{A},\texttt{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}$ 次迭代）与块内 $\widetilde O(\sqrt m)$ 判定，两因子相乘时 $m$ 对消，总复杂度 $\widetilde O(\sqrt n+\sqrt m)$，与下界只差 polylog。
- 随机（平均情形）模式匹配可归约到带噪 $d$ 维 hidden shift：随机性使偶然匹配指数罕见，真实匹配化为唯一平移 $s$；单射 hidden shift 的单次量子采样产生相位态 $\frac{1}{\sqrt2}(|0\rangle+e^{2\pi i k\cdot s/M}|1\rangle)$，Kuperberg 筛法以 $2^{O(d^{3/2}\sqrt{\log m})}$ 的成本从中提取 $s$，外层 Grover 贡献 $(n/m)^{d/2}$。
- 平均情形结论是超多项式加速，但它是**分布承诺下**的结果（噪声分析带启发式成分），不替代最坏界；字符 query、随机平均、整串量子输入是三种不可混写的模型；任何模型下候选都必须经过 $O(\sqrt m)$ 的完整验证。

## 练习题

**练习 1【字符 oracle 模型与嵌套 Grover 的代价规则】**（→ [2 节](#oracle-model-nested-cost)）

1. 写出本课字符 oracle 对态 $|b,i\rangle|z\rangle$ 的作用式，并说明"查询复杂度"与"时间复杂度"分别统计什么。
2. 外层 Grover 在 $N$ 个候选中搜索、每次迭代调用一个成本为 $C$ 次查询的判定器：写出总查询数；再取 $N=n/m$、$C=\widetilde O(\sqrt m)$，计算外层搜索的总查询数，并指出 $m$ 在乘积中发生了什么。

> 提示：总查询数是外层迭代次数与单次判定成本的乘积。

**练习 2【最坏情形基线与下界】**（→ [3.1 节](#worst-case-baseline-lower-bound)）

1. 计算朴素嵌套的总查询数：外层在 $n-m+1$ 个候选偏移上做 Grover 搜索，内层判定器是 $O(\sqrt m)$ 的 mismatch 搜索，说明总查询数为 $O(\sqrt{(n-m+1)\,m})\le O(\sqrt{nm})$。
2. 详细写出 3.3 节来源一的归约：给定一个解决一般模式匹配问题、查询数为 $Q(n,m)$ 的量子算法，如何用它以 $Q(n,1)$ 次查询解决"长度 $n$ 的 $01$ 串是否含 $\texttt{1}$"？由此说明 $Q(n,m)=\Omega(\sqrt n)$。再问：为什么同一个归约不能同时给出 $\Omega(\sqrt{nm})$？

> 提示：$m=1$、$P=\texttt{1}$ 时，"是否存在匹配偏移"恰好就是"文本中是否出现字符 $\texttt{1}$"。

**练习 3【样本性质与周期模式的处理】**（→ [4.1 节](#deterministic-sampling-lemma)）

1. 在第 8 节的实例 $T=\texttt{ACGTCGACG}$、$P=\texttt{TCGA}$ 上改用样本 $S=\{1,3\}$（对应 $P[1]=\texttt C$、$P[3]=\texttt A$）：逐一检验六个偏移 $0\le s\le 5$，指出幸存者，并对幸存者做一次完整验证。
2. 取 $P=\texttt{abababab}$（$m=8$，周期 $p=2$）。任取一个不包含位置 $0$ 与 $1$ 的样本集合 $S$，证明存在两个相差 $2$ 的偏移在**任何**以周期 $2$ 重复 $\texttt{ab}$ 的文本段上同时通过样本检验。这说明"每块至多一个候选"对周期模式必然失效；再简述识别周期后为什么只需验证一个代表偏移。

> 提示：在以周期 $2$ 重复 $\texttt{ab}$ 的文本段上，相差 $2$ 的两个窗口逐字符相同。

**练习 4【四步算法与参数平衡】**（→ [4.3 节](#four-step-algorithm)）

1. 列出 Ramesh–Vinay 算法的四步，写出每一步的查询成本，并把它们相加验证总和为 $\widetilde O(\sqrt n+\sqrt m)$。
2. 若块判定不使用样本检验，而是对块内约 $m$ 个偏移逐个做 $O(\sqrt m)$ 的完整验证：计算单次块判定成本与总查询数，并说明样本检验消灭的是哪一个因子。

> 提示：$\sqrt{n/m}\times m^{3/2}=m\sqrt n$，多出来的那个 $m$ 正来自"逐偏移"。

**练习 5【随机性消灭歧义与带噪 hidden shift 归约】**（→ [5.1 节](#randomness-kills-ambiguity)）

1. 取 $\sigma=2$、$n=2^{20}$、$m=60$：计算两个固定窗口在全部 $m$ 个位置上巧合相同的概率，再用 union bound 估计"存在一对完全相同的窗口"的概率上界，并判断偶然匹配是否构成干扰。
2. 说明随机性为什么能把"模式出现在哪里"变成一个唯一确定的平移量；写出指纹函数需要满足的"平移协变"关系，并指出不满足该关系的坏位置有哪两个来源。

> 提示：对照 5.2 节的 $g(x)\approx f(x+s)$；坏位置来自边界效应与指纹碰撞。

**练习 6【相位态的制备与噪声】**（→ [5.3 节](#phase-state-derivation-pattern-matching)）

1. 取 $d=1$、$M=8$、$s=3$：分别写出测得 $k=2$ 与 $k=4$ 时标志比特所处的相位态（用 5.3 节的相位约定）。
2. 补全 5.3 节推导的两个细节：(a) 说明第 1 步的叠加态如何用一次受控 $f$ 查询与一次受控 $g$ 查询制备；(b) 验证第 5 步中"测得任意 $k$ 的概率相同"，并解释为什么 $k$ 的测量结果本身不泄露 $s$。
3. 说明 5.4 节中"坏相位态"是如何产生的，以及为什么坏态比例只能被压得很小、但恒不为零。

> 提示：测量前两个频率分支的振幅模长都与 $k$ 无关；坏态比例的上界依赖输入的随机分布承诺。

**练习 7【Kuperberg 筛法与平均情形复杂度】**（→ [6.1 节](#kuperberg-sieve)）

1. 把两个相位态 $\frac{1}{\sqrt2}(|0\rangle+e^{i\theta_1}|1\rangle)$ 与 $\frac{1}{\sqrt2}(|0\rangle+e^{i\theta_2}|1\rangle)$（$\theta_j=2\pi k_js/M$）的张量积按两个比特的奇偶性分组，写出偶宇称组与奇宇称组，并说明测量各以多大概率产出频率为 $k_1+k_2$ 或 $k_1-k_2$ 的新态。
2. 在平均情形总式 $\widetilde O\big((n/m)^{d/2}2^{O(d^{3/2}\sqrt{\log m})}\big)$ 中取 $d=1$，写出化简后的式子；再令 $m=\log^2 n$（设文本足够长使 $n/m$ 仍为 $n$ 的多项式），比较量子成本与经典约 $n/m$ 次块检查的成本，指出超多项式差距来自哪个因子。
3. 证明：对任何常数 $c>0$ 与固定的 $d$，$2^{O(d^{3/2}\sqrt{\log m})}=o(m^c)$。（提示：两边取对数。）这个事实是"第二因子次多项式"的严格含义。

> 提示：仿照 6.3 节，把量子/经典成本之比写成 $\frac{(\text{次多项式因子})}{(n/m)^{1/2}}$ 再比较增长速度。

**练习 8【三种输入模型与完整验证】**（→ [7 节](#three-input-models)）

1. 分别用一句话说出字符 query、随机平均、整串量子输入三种模型各自的输入承诺与复杂度度量，为前两种模型各举一个本课得到的复杂度结论，并说明第三种模型的数字为何与前两者不可比。
2. 构造一个小规模例子（字符表、文本、模式、样本集合自选），使得某个非匹配偏移通过了样本检验。由此说明：为什么无论最坏情形还是平均情形，候选指纹/样本匹配之后都必须做完整的 mismatch 验证，$O(\sqrt m)$ 的验证成本不能从总式中删除。

> 提示：第 8 节中样本 $S=\{2\}$ 的情形已给出一个现成反例（$s=0$ 通过检验却并非匹配），可先复述它再自造一例。

## 参考文献与 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 的整串量子输入模型算法。