量子模式匹配：确定性采样、Grover 与平均情形 Hidden Shift¶
模式匹配（pattern matching，又叫字符串匹配）是计算机科学中最古老、应用最广的问题之一：给定一段文本 \(T\)（长度为 \(n\) 的字符串）与一个模式 \(P\)（长度为 \(m\le n\) 的字符串），寻找一个偏移 \(s\)，使得把 \(P\) 平移到 \(T\) 的第 \(s\) 个位置后逐字符吻合，即
它的 \(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 算法与振幅放大（迭代次数 \(O(\sqrt{N})\)、成功概率 \(\sin^2((2T+1)\theta)\) 那一套分析）、量子 Fourier 变换以及相位估计。hidden shift 问题与 Simon 算法一脉相承；Kuperberg 筛法我们只做结构性介绍。
本课知识点
字符 oracle 模型与嵌套 Grover 的代价规则——能写出字符 oracle 的酉作用式、区分查询复杂度与时间复杂度，并用乘法规则计算嵌套 Grover 结构的总查询数。
最坏情形基线与下界——能用 Grover mismatch 搜索验证单个偏移并计算朴素嵌套的 \(O(\sqrt{nm})\)，再构造两个归约证明下界 \(\Omega(\sqrt n+\sqrt m)\)，并解释两项为何相加而非相乘。
样本性质与周期模式的处理——能陈述样本性质引理、用见证位置与贪心覆盖给出证明思路，并解释周期模式为何是唯一例外、如何用等差数列把验证压缩到代表元。
四步算法与参数平衡——能列出 Ramesh–Vinay 算法的四步及各自查询成本，推导块长 \(\Theta(m)\) 如何让 \(m\) 在两因子相乘时对消，得到 \(\widetilde O(\sqrt n+\sqrt m)\)。
随机性消灭歧义与带噪 hidden shift 归约——能用逐位置巧合概率 \(\sigma^{-m}\) 与 union bound 估计偶然匹配的概率上界，并把"块内找匹配"改写成带噪声的 hidden shift 问题。
相位态的制备与噪声——能补全从均匀叠加、受控 oracle 到测量指纹值、QFT 的五步推导，写出相位态 \(\frac{1}{\sqrt2}(|0\rangle+e^{2\pi ik\cdot s/M}|1\rangle)\)，并说明坏相位态的来源。
Kuperberg 筛法与平均情形复杂度——能解释分桶、合并、逐级推进三环节，完成宇称测量的合并计算并推导平衡点 \(\ell\approx\sqrt{\log M}\)，把总式拆成 \((n/m)^{d/2}\cdot 2^{O(d^{3/2}\sqrt{\log m})}\) 并说明超多项式加速的保留条款。
三种输入模型与完整验证——能列出字符 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 节）。
这些文献与文末"参考文献"一节一一对应。
2. Oracle 模型与基本工具¶
**字符 oracle。**在本课的大部分篇幅里，输入通过黑盒访问：一次查询指定一对 \((b,i)\)，其中 \(b\in\{T,P\}\) 指明查文本还是模式，\(i\) 是位置；oracle 返回对应字符。量子版本中这是一个酉变换
其中 \(\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. 最坏情形：基线算法与下界¶
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 搜索：
若不存在 mismatch，Grover 搜索报告"无解"，\(s\) 是匹配；否则输出一个具体的失配位置作为证据。注意这里用的是 Grover 的存在性版本：我们不仅找到失配，还能区分"有"与"没有"。
3.2 基线二：朴素嵌套及其浪费¶
最直接的完整算法：把"偏移 \(s\)"也放进 Grover——外层在约 \(n\) 个候选偏移中搜索，内层判定器就是上一段的 \(O(\sqrt m)\) 验证。由乘法规则，总查询数为
这个数字离下界 \(\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\) 是相加而不是取最大：两项各自封锁了一类算法捷径。
合并两个来源：
这是后续所有算法设计的对标线。
一个自然的疑问是：为什么下界不是 \(\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：把候选偏移压到很少¶
4.1 直觉：模式自身的重叠结构决定了"侦察成本"¶
考虑这样一个思想实验。假设模式 \(P\) 内部"杂乱无章"——它的任何非零平移都与自己对不上（即 \(P\) 与 \(P\) 平移 \(t\) 位后的重叠部分存在失配，对所有 \(1\le t<m\) 成立）。那么，假如我们在文本中找到了模式的一个匹配，偏移 \(s\) 就被唯一锁定了：偏移 \(s+t\)（\(t\ne 0\)）处不可能同时还有一个匹配，因为那样 \(P\) 与自身平移 \(t\) 位必须完全一致，与假设矛盾。
再进一步：我们其实不需要比较全部 \(m\) 个字符来锁定偏移。选一小撮样本位置
连同对应的模式字符 \(P[j_a]\)。如果一个偏移 \(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\)：
若 \(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+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)\) 的文本块里，需要认真对待的偏移只有极少个。
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)\)，故总成本为
这一步只查模式 \(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 子程序的成功概率提升同理。这些重复只贡献对数因子。四步合计：
与 3.3 节的下界 \(\Omega(\sqrt n+\sqrt m)\) 之间只差 polylog 因子。最坏情形的查询复杂度至此被钉死：模式匹配在最坏情形下，量子相对经典的加速恰好是平方根级，不会再多。
5. 平均情形：归约到带噪 hidden shift¶
从现在开始，我们换一个输入承诺：\(T\) 与 \(P\) 是独立均匀随机的字符串（\(d\) 维情形是随机格点阵列）。这个承诺改变了一切。
5.1 随机性消灭了歧义¶
设字符表大小为 \(\sigma\ge 2\)。固定两个不同的长度-\(m\) 窗口（例如文本中偏移 \(s\) 与 \(s'\) 处的窗口，\(s\ne s'\)），它们逐字符相同的概率可以这样估计：每个位置独立地以概率 \(1/\sigma\) 巧合相同，故两个窗口在全部 \(m\) 个位置都相同的概率是
更一般地，"在很多位置同时相同"的概率随位置数指数衰减。把估计做完：文本中窗口总数 \(O(n)\)，窗口对数 \(O(n^2)\)，由 union bound（概率的并上界：若干事件至少一个发生的概率不超过各自概率之和），存在一对"偶然完全相同"窗口的概率至多为
代入一个代表性的尺度 \(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\)，
其中 \(\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\)）：
（制备过程：对标志位加 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\) 在叠加中恰好配出一对：
第 3 步，测量指纹值寄存器。无论测得哪个 \(v\)（结果是均匀随机的、且不包含 \(s\) 的信息，可以丢弃），态坍缩为
其中 \(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\)。作用到上式：
第 5 步，测量 \(k\)（\(d\) 维频率，均匀随机）。把公共因子 \(e^{2\pi i k\cdot x_0/M}\) 提为全局相位并丢弃，标志位上剩下
这正是引言中提到的相位态（指数上的整体符号只是相位约定，无关紧要）。注意这个态的构造逻辑：\(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\)¶
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\)，两个输入态的张量积为
按两个比特的奇偶性把四项重新分组：偶宇称项 \(|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\)；筛法的样本/时间复杂度是
\(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\)）。
**总式。**两因子相乘：
为什么说这是超多项式加速？固定 \(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}\) 级别的代价。于是量子与经典平均情形成本之比大约是
只要 \(m\) 大于对数尺度使块数 \((n/m)^d\) 仍充分大，分母的多项式增长压过分子的次多项式增长，比值趋于零——超多项式差距。
保留条款（必须随结论一起引用）。第一，这是平均情形结果，依赖 \(T,P\) 独立均匀随机的承诺，不替代、也不否定第 3–4 节的最坏情形界 \(\widetilde\Theta(\sqrt n+\sqrt m)\)——对手写的输入仍然只有平方根加速。第二，噪声传播分析是启发式的、模型依赖的。第三，找到候选块后仍需完整验证（见下一节）。
7. 三种输入模型必须分开¶
模式匹配的量子文献中出现过三种输入设定，它们的复杂度数字不可混写：
字符 query 模型（本课主要模型）。每次查询只相干读取一个字符 \(T_i\) 或 \(P_j\)。\(\widetilde O(\sqrt n+\sqrt m)\) 是这个模型下的查询复杂度结论；由于每次查询后只做 polylog 的辅助计算，它也是时间复杂度（相差 polylog）。
随机平均模型。在 query 模型之上，还承诺 \(T,P\) 的分布（独立均匀随机）。没有这个承诺，5.1 节的碰撞概率估计、5.4 节的噪声界都无从谈起，noisy hidden shift 归约的唯一性也就失效。这是第 5–6 节超多项式加速的适用前提。
整串量子输入模型。若 \(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\)）上的
位置从 \(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 |
|
否 |
1 |
|
否 |
2 |
|
否 |
3 |
|
是 |
4 |
|
否 |
5 |
|
否 |
偏移 \(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 |
|
否 |
|
是 |
否 |
1 |
|
否 |
|
否 |
否 |
2 |
|
否 |
|
否 |
否 |
3 |
|
是 |
|
是 |
是 |
4 |
|
否 |
|
否 |
否 |
5 |
|
否 |
|
否 |
否 |
两个样本位置就把六个候选过滤到只剩 \(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 对态 \(|b,i\rangle|z\rangle\) 的作用式，并说明"查询复杂度"与"时间复杂度"分别统计什么。
外层 Grover 在 \(N\) 个候选中搜索、每次迭代调用一个成本为 \(C\) 次查询的判定器：写出总查询数；再取 \(N=n/m\)、\(C=\widetilde O(\sqrt m)\)，计算外层搜索的总查询数，并指出 \(m\) 在乘积中发生了什么。
提示：总查询数是外层迭代次数与单次判定成本的乘积。
练习 2【最坏情形基线与下界】（→ 3.1 节）
计算朴素嵌套的总查询数：外层在 \(n-m+1\) 个候选偏移上做 Grover 搜索，内层判定器是 \(O(\sqrt m)\) 的 mismatch 搜索，说明总查询数为 \(O(\sqrt{(n-m+1)\,m})\le O(\sqrt{nm})\)。
详细写出 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 节）
在第 8 节的实例 \(T=\texttt{ACGTCGACG}\)、\(P=\texttt{TCGA}\) 上改用样本 \(S=\{1,3\}\)（对应 \(P[1]=\texttt C\)、\(P[3]=\texttt A\)）：逐一检验六个偏移 \(0\le s\le 5\)，指出幸存者，并对幸存者做一次完整验证。
取 \(P=\texttt{abababab}\)（\(m=8\)，周期 \(p=2\)）。任取一个不包含位置 \(0\) 与 \(1\) 的样本集合 \(S\)，证明存在两个相差 \(2\) 的偏移在任何以周期 \(2\) 重复 \(\texttt{ab}\) 的文本段上同时通过样本检验。这说明"每块至多一个候选"对周期模式必然失效；再简述识别周期后为什么只需验证一个代表偏移。
提示：在以周期 \(2\) 重复 \(\texttt{ab}\) 的文本段上，相差 \(2\) 的两个窗口逐字符相同。
练习 4【四步算法与参数平衡】（→ 4.3 节）
列出 Ramesh–Vinay 算法的四步，写出每一步的查询成本，并把它们相加验证总和为 \(\widetilde O(\sqrt n+\sqrt m)\)。
若块判定不使用样本检验，而是对块内约 \(m\) 个偏移逐个做 \(O(\sqrt m)\) 的完整验证：计算单次块判定成本与总查询数，并说明样本检验消灭的是哪一个因子。
提示：\(\sqrt{n/m}\times m^{3/2}=m\sqrt n\)，多出来的那个 \(m\) 正来自"逐偏移"。
练习 5【随机性消灭歧义与带噪 hidden shift 归约】（→ 5.1 节）
取 \(\sigma=2\)、\(n=2^{20}\)、\(m=60\)：计算两个固定窗口在全部 \(m\) 个位置上巧合相同的概率，再用 union bound 估计"存在一对完全相同的窗口"的概率上界，并判断偶然匹配是否构成干扰。
说明随机性为什么能把"模式出现在哪里"变成一个唯一确定的平移量；写出指纹函数需要满足的"平移协变"关系，并指出不满足该关系的坏位置有哪两个来源。
提示：对照 5.2 节的 \(g(x)\approx f(x+s)\)；坏位置来自边界效应与指纹碰撞。
练习 6【相位态的制备与噪声】（→ 5.3 节）
取 \(d=1\)、\(M=8\)、\(s=3\)：分别写出测得 \(k=2\) 与 \(k=4\) 时标志比特所处的相位态（用 5.3 节的相位约定）。
补全 5.3 节推导的两个细节：(a) 说明第 1 步的叠加态如何用一次受控 \(f\) 查询与一次受控 \(g\) 查询制备；(b) 验证第 5 步中"测得任意 \(k\) 的概率相同"，并解释为什么 \(k\) 的测量结果本身不泄露 \(s\)。
说明 5.4 节中"坏相位态"是如何产生的，以及为什么坏态比例只能被压得很小、但恒不为零。
提示：测量前两个频率分支的振幅模长都与 \(k\) 无关；坏态比例的上界依赖输入的随机分布承诺。
练习 7【Kuperberg 筛法与平均情形复杂度】（→ 6.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\) 的新态。
在平均情形总式 \(\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\) 次块检查的成本，指出超多项式差距来自哪个因子。
证明：对任何常数 \(c>0\) 与固定的 \(d\)，\(2^{O(d^{3/2}\sqrt{\log m})}=o(m^c)\)。（提示：两边取对数。）这个事实是"第二因子次多项式"的严格含义。
提示：仿照 6.3 节，把量子/经典成本之比写成 \(\frac{(\text{次多项式因子})}{(n/m)^{1/2}}\) 再比较增长速度。
练习 8【三种输入模型与完整验证】（→ 7 节）
分别用一句话说出字符 query、随机平均、整串量子输入三种模型各自的输入承诺与复杂度度量，为前两种模型各举一个本课得到的复杂度结论，并说明第三种模型的数字为何与前两者不可比。
构造一个小规模例子（字符表、文本、模式、样本集合自选），使得某个非匹配偏移通过了样本检验。由此说明：为什么无论最坏情形还是平均情形，候选指纹/样本匹配之后都必须做完整的 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.
Zoo 编号 215、66：Ashley Montanaro, Quantum Pattern Matching Fast on Average，使用 Kuperberg 筛法。
Zoo 编号 216：Bennett--Bernstein--Brassard--Vazirani 无结构查询下界。
Zoo 编号 435：Niroula--Nam 的整串量子输入模型算法。