量子矩阵乘积验证：Johnson 图量子行走的 $O(n^{5/3})$ 算法¶

给定三个 $n\times n$ 矩阵 $A,B,C$，计算 $AB$ 很贵——朴素算法要 $O(n^3)$ 次标量运算，即使用上目前最快的矩阵乘法算法也远超 $O(n^2)$——但如果有人声称 $AB=C$，我们只是想验证这个等式是否成立，事情可能便宜得多。经典的 Freivalds 算法用随机指纹在 $O(n^2)$ 时间内完成验证（只读一遍输入，这已是经典极限）；量子算法则通过在两个 Johnson 图的乘积上做量子行走，把最坏情况下的真实运行时间降到 $O(n^{5/3})$。

本课分两条主线展开。第一条是组合搜索主线：把"验证"改写成"在行子集与列子集对 $(R,S)$ 中搜索一个能暴露错误的子矩阵"，再用 Szegedy 的马尔可夫链量子行走框架求解，得到步数 $O(n/\sqrt{k})$。第二条是数据结构主线：量子行走框架只告诉你"走多少步"，却不保证"每步有多便宜"。如果每一步都显式计算一个 $k\times k$ 子矩阵乘积，时间复杂度会立刻退回 $\Omega(n^2)$，量子优势荡然无存。本课尤其强调这个常被忽略的区别——查询复杂度下降不自动保证真实运行时间下降——而 Buhrman–Špalek 算法真正的技术贡献，正是设计了一套可用双侧随机指纹增量更新的压缩数据结构，把每步成本压到 $O(n)$。两条主线汇合后，用一个参数平衡得到 $O(n^{5/3})$。

读者需要的前置知识：Grover 搜索与振幅放大的基本框架（见Grover 算法），以及量子行走与马尔可夫链谱隙的基本概念（见量子行走）。不需要事先了解 Szegedy 框架的细节，本课第 3 节会给出所需的结论并解释其含义。

本课知识点

Freivalds 指纹算法与配对论证——能写出 Freivalds 算法的三步流程，并用配对论证证明单次检出概率至少 $\frac12$，说明其单边错误结构。
验证的搜索改写与标记比例——能证明"限制的乘积等于乘积的限制"，把验证 $AB=C$ 改写为"是否存在标记子集对"的搜索问题，并推导最坏情形标记比例 $\epsilon\ge(k/n)^2$。
Johnson 图与谱隙——能写出 Johnson 图 $J(n,k)$ 的顶点与相邻关系，并由特征值公式计算谱隙 $\delta=\Theta(1/k)$。
Szegedy 框架与步数估计——能写出 Szegedy 量子行走的步数公式与总时间结构，并代入 $\delta$、$\epsilon$ 推出行走步数 $O(n/\sqrt{k})$。
双侧随机指纹——能用随机向量 $p,q$ 构造 $a_R,b_S,c_{R,S}$，把子矩阵检查压缩为 $O(n)$ 的标量比较，并连用两次配对论证证明检出概率至少 $\frac14$。
指纹的增量更新——能写出一步交换元素后 $a_R,b_S,c_{R,S}$ 的增量更新公式，并验证每步行走的成本为 $O(n)$。
复杂度平衡——能通过令初始化项 $kn$ 与行走项 $n^2/\sqrt{k}$ 同阶解出 $k=n^{2/3}$，计算总时间 $O(n^{5/3})$，并解释缺少压缩检查时量子加速为何消失。
正确性与模型边界——能说明算法的单边错误结构，并指出其对环结构、计算模型与问题定义（验证而非计算）三方面的适用边界。

问题背景：验证为什么值得单独研究¶

矩阵乘法是整个线性代数计算的瓶颈操作。两个 $n\times n$ 矩阵相乘，按定义

\[ (AB)_{ij} = \sum_{l=1}^{n} A_{il}B_{lj}, \]

每个条目需要 $n$ 次乘法与 $n-1$ 次加法，共 $n^2$ 个条目，朴素算法总计 $O(n^3)$ 次标量运算。存在更快的算法（Strassen 及其后继者把指数压到 $3$ 以下），但即便是最快的已知算法，代价也仍然显著高于"把输入读一遍"的 $\Theta(n^2)$。

在许多应用场景里，我们并不需要亲自算出 $AB$。典型的情形是：某个不受信任的计算方（云服务器、协处理器、另一台机器）声称已经算出了 $AB=C$，把 $C$ 交给我们；我们想用一个比重新乘法便宜得多的程序来检查这份答案。这就是矩阵乘积验证 (matrix product verification) 问题：

给定 $n\times n$ 矩阵 $A,B,C$，判断 $AB=C$ 是否成立。要求算法允许以小概率出错，但必须比完整地计算 $AB$ 更快。

这个问题的历史值得一说。经典侧，Freivalds 在 20 世纪 70 年代末提出的随机指纹算法已经达到 $O(n^2)$，与"读完输入"的下界匹配，经典故事到此基本结束。量子侧，Ambainis 等人在 2002 年的未发表手稿（文末 Zoo 编号 6）中最早研究了矩阵验证的量子算法，在查询复杂度的意义下给出了优于经典的结果；但查询复杂度只计算"读了多少个矩阵元素"，不计算读写之间的算术与数据搬运，因此查询上的加速并不自动转化为真实运行时间的加速。Buhrman 与 Špalek（文末 Zoo 编号 19）把 Szegedy 的马尔可夫链量子行走框架（文末 Zoo 编号 85）与一套精心设计的增量数据结构结合起来，给出了真实运行时间 $O(n^{5/3})$ 的验证算法，这是本课要讲解的内容。

在正式进入推导之前，先用一句话概括整个算法的核心思想，后面的每一节都是在为这句话填细节：

不要直接验证 $AB=C$，而是在随机的行子集 $R$ 与列子集 $S$ 上检查子矩阵等式 $A|_R\,B|^S = C|_R^S$；用 Szegedy 量子行走在所有 $(R,S)$ 中搜索一对"能看出错误"的子集；为了让行走的每一步足够便宜，不存储子矩阵本身，只存储它被两个随机向量 $p,q$ 压缩后的指纹，并在行走时增量维护这些指纹。

1. 经典基线：Freivalds 指纹¶

1.1 算法与正确性分析¶

令

\[ D = AB - C. \]

验证 $AB=C$ 等价于验证 $D=0$。直接计算 $D$ 就是直接计算 $AB$，太贵；Freivalds 的想法是改为检验 $D$ 在一个随机方向上的投影：如果 $D\neq 0$，那么一个随机向量 $r$ 大概率不在 $D$ 的核里，从而 $Dr\neq 0$ 会暴露这一点。

Freivalds 算法：

从一个固定的有限集合（例如 $\{0,1\}$）中独立均匀地随机选择 $n$ 个分量，组成列向量 $r$；
依次计算

\[ u = Br,\qquad v = Au,\qquad w = Cr; \]

若 $v\neq w$，回答"$AB\neq C$"；若 $v=w$，回答"$AB=C$"（更准确地说是"未发现矛盾"）。

注意第 2 步的计算顺序至关重要：必须先算 $Br$ 再左乘 $A$，即算的是 $A(Br)$ 而不是 $(AB)r$。$Br$ 是"$n\times n$ 矩阵乘向量"，需 $n^2$ 次标量乘法与约 $n^2$ 次加法，即 $O(n^2)$；$Au$ 与 $Cr$ 同理。三次矩阵–向量乘法加一次向量比较，总成本 $O(n^2)$。若误算成 $(AB)r$，先算 $AB$ 就要 $O(n^3)$，整个验证就失去了意义。

算法的输出与 $D$ 的关系由

\[ v - w = A(Br) - Cr = (AB - C)r = Dr \]

给出（第二步只是矩阵乘法对加法的分配律）。因此"算法发现矛盾"当且仅当"$Dr\neq 0$"。下面这条引理给出错误概率界，它是整个 Freivalds 方法的核心。

Lemma 1（Freivalds 指纹界）. 设 $D$ 是非零的 $n\times n$ 矩阵，$r$ 的分量独立均匀地取自 $\{0,1\}$，则

\[ \Pr_r[\,Dr \neq 0\,] \ge \frac12. \]

证明。$D\neq 0$ 意味着 $D$ 有某一行是非零行向量，记为 $d$（取其第 $i$ 行，$d_j = D_{ij}$）。只要证明 $\Pr[\,d\cdot r \neq 0\,]\ge \frac12$ 即可，因为 $d\cdot r\neq 0$ 蕴含 $Dr$ 的第 $i$ 个分量非零，从而 $Dr\neq 0$。

设 $d_{j_0}\neq 0$。把所有 $2^n$ 个可能的 $r$ 两两配对：$r$ 与 $r'$ 一对，当且仅当它们仅在第 $j_0$ 个分量上不同（即 $r'_{j_0} = 1 - r_{j_0}$，其余分量完全相同）。这 $2^n$ 个向量恰好被划分成 $2^{n-1}$ 对。对每一对，

\[ d\cdot r' = \sum_j d_j r'_j = \sum_{j\neq j_0} d_j r_j + d_{j_0}(1 - r_{j_0}) = d\cdot r \pm d_{j_0}. \]

（若 $r_{j_0}=0$ 则取 $+$ 号，若 $r_{j_0}=1$ 则取 $-$ 号；两种情形相差的值都是 $\pm d_{j_0}$。）假如这一对中两个内积都为零，则两式相减得 $\pm d_{j_0}=0$，与 $d_{j_0}\neq 0$ 矛盾。因此每一对中至少有一个向量满足 $d\cdot r\neq 0$，非零内积的比例至少是一半，即 $\Pr[\,d\cdot r\neq 0\,]\ge\frac12$。Q.E.D.

这个配对论证是本课反复出现的技术原型：后面第 4 节分析双侧指纹时，用的还是同一个论证，只是连用两次。

单边错误 (one-sided error)。由引理立即读出 Freivalds 算法的错误结构：

若 $AB=C$（即 $D=0$），则对任何 $r$ 都有 $Dr=0$，算法永远回答"相等"，永不误报；
若 $AB\neq C$，算法单次运行以至少 $\frac12$ 的概率发现矛盾，但可能恰好选中一个落在 $\ker D$ 里的 $r$ 而漏报。

也就是说，"正确乘积永不被拒绝，错误乘积可能因随机指纹碰撞而暂时通过"。要把漏报概率压低，只需独立重复：重复 $t$ 次（每次重新随机选 $r$），全都未发现问题才接受，则错误接受的概率至多为 $2^{-t}$。取常数次的 $t$（比如 $t=3$ 使错误率降到 $\frac18$ 以下）即可把错误率压到任何常数以下，总时间仍是 $O(n^2)$。

1.2 一个 $2\times2$ 小例子¶

把上面的分析用具体数字走一遍。取

\[\begin{split} A = \begin{pmatrix}1 & 2\\ 3 & 4\end{pmatrix},\qquad B = \begin{pmatrix}5 & 6\\ 7 & 8\end{pmatrix}. \end{split}\]

真实的乘积是

\[\begin{split} AB = \begin{pmatrix}1\cdot5+2\cdot7 & 1\cdot6+2\cdot8\\ 3\cdot5+4\cdot7 & 3\cdot6+4\cdot8\end{pmatrix} = \begin{pmatrix}19 & 22\\ 43 & 50\end{pmatrix}. \end{split}\]

假设对方交来的答案是

\[\begin{split} C = \begin{pmatrix}19 & 22\\ 43 & 51\end{pmatrix}, \end{split}\]

即只有 $(2,2)$ 位置的条目是错的（$51$ 应为 $50$）。此时

\[\begin{split} D = AB - C = \begin{pmatrix}0 & 0\\ 0 & -1\end{pmatrix}. \end{split}\]

现在模拟 Freivalds 算法。$r$ 有四种等可能的取值，我们逐个算 $Dr$：

$r=(1,0)^T$：$Dr = (0\cdot1+0\cdot0,\ 0\cdot1+(-1)\cdot0)^T = (0,0)^T$——漏报，算法回答"相等"；
$r=(0,1)^T$：$Dr = (0\cdot0+0\cdot1,\ 0\cdot0+(-1)\cdot1)^T = (0,-1)^T$——发现矛盾；
$r=(1,1)^T$：$Dr = (0,\ -1)^T$——发现矛盾；
$r=(0,0)^T$：$Dr=(0,0)^T$——漏报（这个零向量对任何 $D$ 都漏报）。

四种取值中有两种发现矛盾，检出概率恰为 $\frac12$，与 Lemma 1 的界吻合（引理只说"至少一半"，本例恰好取到等号）。注意检出失败的两种情形里，$(0,0)^T$ 是平凡的，真正"倒霉"的情形只有 $r=(1,0)^T$。

再把算法的三步完整算一遍（以 $r=(1,1)^T$ 为例）：

\[\begin{split} u = Br = \begin{pmatrix}5+6\\ 7+8\end{pmatrix} = \begin{pmatrix}11\\ 15\end{pmatrix},\qquad v = Au = \begin{pmatrix}1\cdot11+2\cdot15\\ 3\cdot11+4\cdot15\end{pmatrix} = \begin{pmatrix}41\\ 93\end{pmatrix}, \end{split}\]

\[\begin{split} w = Cr = \begin{pmatrix}19+22\\ 43+51\end{pmatrix} = \begin{pmatrix}41\\ 94\end{pmatrix}. \end{split}\]

$v\neq w$（第二个分量 $93\neq 94$），算法正确地拒绝。请读者对照验证：$v$ 恰好是 $(AB)r$，所以 $v-w=Dr$，一切自洽。

1.3 经典极限与量子机会¶

Freivalds 算法的 $O(n^2)$ 在经典世界是最优的：任何（哪怕允许随机性的）验证算法都必须读完输入的相当部分——若有一个条目完全没被读到，对手就可以在那个条目上做手脚而不被发现，而矩阵共有 $\Theta(n^2)$ 个条目。所以经典验证的复杂度故事已经讲完：$\Theta(n^2)$。

量子算法的机会恰恰在于打破"必须读完每个条目"的经典直觉：振幅叠加允许我们"同时"探查所有位置，Grover 型的搜索可以把某些二次加速带进这个问题。但本课反复强调的警示也在这里生效：查询次数的平方根加速只是潜力，要变成真实时间的加速，必须让量子行走的每一步都足够便宜。这正是第 4 节的任务。我们先在第 2、3 节搭好搜索的骨架。

2. 搜索对象：行子集与列子集¶

2.1 把验证改写成搜索¶

量子行走搜索需要一个有限的搜索空间和一个"标记"谓词。直接照搬 Freivalds（在 $2^n$ 个 $r$ 里 Grover 搜索一个满足 $Dr\neq0$ 的 $r$）行不通：单次检查 $Dr$ 就要 $O(n^2)$ 时间，即使搜索本身只要常数步，总时间也没有改观。Buhrman–Špalek 的选择是把搜索空间取为子矩阵，而不是随机向量。

固定一个参数 $k$（$1\le k\le n$，最后会取 $k=n^{2/3}$），搜索空间是所有大小为 $k$ 的子集对

\[ R,S\subseteq[n],\qquad |R|=|S|=k, \]

其中 $[n]=\{1,2,\dots,n\}$。约定如下记号：

$A|_R$：$A$ 只保留 $R$ 中的行得到的 $k\times n$ 矩阵；
$B|^S$：$B$ 只保留 $S$ 中的列得到的 $n\times k$ 矩阵；
$C|_R^S$：$C$ 只保留 $R$ 中的行与 $S$ 中的列得到的 $k\times k$ 矩阵。

标记状态的定义。若子矩阵等式不成立，即

\[ A|_R\,B|^S \ne C|_R^S, \]

就称 $(R,S)$ 为标记状态 (marked state)。这一定义之所以合理，依赖一个简单但关键的恒等式：

Lemma 2（限制的乘积等于乘积的限制）. 对任意 $R,S\subseteq[n]$，

\[ (AB)|_R^S = A|_R\,B|^S. \]

证明。比较两边 $(a,b)$ 位置的条目（$a,b\in\{1,\dots,k\}$，记 $R$ 的第 $a$ 个元素为 $i_a$、$S$ 的第 $b$ 个元素为 $j_b$）。左边按定义是 $(AB)_{i_a j_b}$；由矩阵乘法的定义，

\[ (AB)_{i_a j_b} = \sum_{l=1}^{n} A_{i_a l}\,B_{l j_b}. \]

右边，$A|_R$ 的第 $a$ 行就是 $A$ 的第 $i_a$ 行，$B|^S$ 的第 $b$ 列就是 $B$ 的第 $j_b$ 列，所以右边的 $(a,b)$ 条目也是 $\sum_l A_{i_a l}B_{l j_b}$。两边逐项相等。Q.E.D.

Lemma 2 说明：$(i,j)$ 位置的错误（即 $(AB)_{ij}\neq C_{ij}$）只与 $A$ 的第 $i$ 行和 $B$ 的第 $j$ 列有关，与矩阵的其余部分无关。因此，只要 $i\in R$ 且 $j\in S$，子矩阵 $A|_RB|^S$ 与 $C|_R^S$ 在对应位置上就必然不同，$(R,S)$ 必为标记状态。反过来，若 $AB=C$，由 Lemma 2 所有子矩阵等式都成立，没有任何标记状态。于是：

$AB=C$ ⟺ 不存在标记状态；$AB\neq C$ ⟺ 存在标记状态（只要 $k\ge 1$）。

验证问题就此被精确地改写成了搜索问题：判断 $(R,S)$ 的集合中是否存在标记状态。

2.2 标记比例 $\epsilon$¶

量子行走搜索的效率由两个量控制：标记状态占总状态的比例 $\epsilon$，以及行走图的谱隙 $\delta$。本节算前者。

Lemma 3（单错误情形的标记比例）. 设 $D=AB-C$ 在 $(i,j)$ 位置有一个非零条目（即 $(AB)_{ij}\neq C_{ij}$）。若 $R,S$ 各自独立均匀地从所有 $k$ 元子集中选取，则 $(R,S)$ 为标记状态的概率至少为

\[ \epsilon \ge \left(\frac{k}{n}\right)^2. \]

证明。由上节讨论，只要 $i\in R$ 且 $j\in S$，$(R,S)$ 就是标记状态。计算 $i\in R$ 的概率：$k$ 元子集共 $\binom{n}{k}$ 个，其中包含指定元素 $i$ 的子集共 $\binom{n-1}{k-1}$ 个（先固定 $i$，再从剩下 $n-1$ 个元素中选 $k-1$ 个），因此

\[ \Pr[i\in R] = \frac{\binom{n-1}{k-1}}{\binom{n}{k}} = \frac{(n-1)!}{(k-1)!(n-k)!}\cdot\frac{k!(n-k)!}{n!} = \frac{k}{n}. \]

同理 $\Pr[j\in S]=\frac{k}{n}$。$R$ 与 $S$ 独立选取，故

\[ \Pr[(R,S)\ \text{被标记}] \ge \Pr[i\in R\ \text{且}\ j\in S] = \frac{k}{n}\cdot\frac{k}{n} = \left(\frac{k}{n}\right)^2. \]

不等号是因为其他错误条目（如果还有）只会增加标记概率。Q.E.D.

最坏情形是 $D$ 只有一个错误条目，此时 $\epsilon\approx(k/n)^2$ 就是实际的标记比例，后面第 5 节的复杂度平衡就按这个最坏情形做。错误条目更多时 $\epsilon$ 上升，算法只会更快（第 5 节末尾会回到这一点）。

3. Johnson 图与 Szegedy 量子行走¶

3.1 Johnson 图 $J(n,k)$¶

搜索空间 $\{(R,S)\}$ 是一个指数大的离散集合，要在其上做量子行走，先要给出一个图结构，让"走一步"对应一个可以廉价实现的局部操作。

Johnson 图 (Johnson graph) $J(n,k)$ 的顶点集是 $[n]$ 的全部 $k$ 元子集（共 $\binom{n}{k}$ 个顶点）；两个顶点 $R,R'$ 相邻，当且仅当它们恰好相差一个元素，即

\[ |R\cap R'| = k-1 \quad\Longleftrightarrow\quad R' = (R\setminus\{i_{\rm out}\})\cup\{i_{\rm in}\} \]

对某对 $i_{\rm out}\in R$、$i_{\rm in}\notin R$ 成立。换句话说，一步行走 = 从当前子集中删去一个元素、加入一个新元素（"交换一个元素"）。从任一顶点出发，有 $k$ 种选择删哪个、$n-k$ 种选择加哪个，所以 $J(n,k)$ 是 $k(n-k)$ 正则图。

我们的行走发生在乘积图

\[ J(n,k)\times J(n,k) \]

上：顶点是子集对 $(R,S)$，一步行走同时在 $R$ 中交换一个元素、在 $S$ 中交换一个元素。这正对应验证问题的结构——错误位置 $(i,j)$ 由行与列共同决定，行子集和列子集必须一起演化。

3.2 谱隙 $\delta=\Theta(1/k)$¶

马尔可夫链（随机行走）的谱隙 (spectral gap) 定义为其转移矩阵最大特征值（正则图上归一化后为 $1$）与次大特征值之差。谱隙衡量随机行走"忘掉初始位置、收敛到平稳分布"的速度；在 Szegedy 框架中，它直接决定量子行走的步数。本小节推导 Johnson 图的谱隙。

$J(n,k)$ 是高度对称的图（它属于一类称为结合方案 (association scheme) 的结构），其邻接矩阵的全部特征值有已知的封闭表达式：对 $k\le n/2$，特征值为

\[ \lambda_j = (k-j)(n-k-j) - j,\qquad j=0,1,\dots,k, \]

且严格递减（$\lambda_0>\lambda_1>\cdots$）。这个公式本身的推导需要结合方案的表示论，超出本课范围；我们把它作为已知事实引用，但从它出发计算谱隙只需一行算术。$j=0$ 给出

\[ \lambda_0 = k(n-k), \]

这正应该等于图的正则度（正则图邻接矩阵的最大特征值恒等于度数，对应的特征向量是全一向量），与上节的度数计算一致，是一个自洽性检查。$j=1$ 给出

\[ \lambda_1 = (k-1)(n-k-1) - 1 = kn - k^2 - k - n + k + 1 - 1 = k(n-k) - n. \]

（第一步展开 $(k-1)(n-k-1)$，第二步合并同类项。）把邻接矩阵除以度数 $k(n-k)$ 得到归一化的随机行走转移矩阵，其谱隙为

\[ \delta_J = \frac{\lambda_0 - \lambda_1}{\lambda_0} = \frac{n}{k(n-k)}. \]

当 $k\le n/2$ 时 $n-k\ge n/2$，于是

\[ \frac{1}{k} \le \frac{n}{k(n-k)} \le \frac{2}{k}, \]

即 $\delta_J=\Theta(1/k)$。

乘积链（$R$ 与 $S$ 各走一步）的特征值是两个因子链特征值的乘积，其谱隙等于两者中较小的那个（这是一个关于乘积马尔可夫链的标准事实）；两个因子相同，故乘积图 $J(n,k)\times J(n,k)$ 的谱隙仍是

\[ \delta = \Theta(1/k). \]

直觉上这也合理：一次交换只改动 $k$ 个元素中的一个，要把一个 $k$ 元子集"洗匀"大约需要 $k$ 步量级的交换，混合时间（以及谱隙的倒数）与 $k$ 同阶。

3.3 Szegedy 搜索框架¶

现在引用 Szegedy 的通用定理（文末 Zoo 编号 85；另见本站的量子行走），它可以看作 Grover 搜索对一般马尔可夫链的推广：

Szegedy 量子行走搜索（结论性陈述）. 设一个遍历对称马尔可夫链的谱隙为 $\delta$，顶点中被标记的比例为 $\epsilon$。则存在一个量子行走算法，用 $$ O\!\left(\frac{1}{\sqrt{\delta\epsilon}}\right) $$ 步行走，判定标记顶点是否存在（单边有界错误：无标记时总回答"无"，有标记时以至少 $\frac23$ 的概率回答"有"）。

与经典的随机行走命中时间 $\Theta(1/(\delta\epsilon))$ 相比，这是一个二次加速——与 Grover 对朴素采样的加速完全同源。框架本身只负责"把谱隙与标记比例翻译成步数"，每一步的代价由使用者负责。把步数与每步代价写在一起，总时间复杂度形如

\[ T = O\!\left( T_{\rm setup} + \frac{1}{\sqrt{\delta\epsilon}}\, \bigl(T_{\rm update} + T_{\rm check}\bigr) \right), \]

其中三项各有明确的职责，后文会逐项填充：

$T_{\rm setup}$：制备所有顶点的均匀叠加（对应随机行走的平稳分布），并把每个顶点附带的数据结构初始化好的一次性成本；
$T_{\rm update}$：实现一步行走的成本——不仅要在相邻顶点间移动振幅，还要把附带的数据结构从旧顶点增量更新到新顶点；
$T_{\rm check}$：实现"标记相位翻转"的成本——判断当前顶点是否被标记，若是则翻转其振幅的相位。

3.4 步数估计¶

把 $\delta=\Theta(1/k)$（第 3.2 节）与最坏情形的 $\epsilon=\Theta(k^2/n^2)$（Lemma 3）代入步数公式：

\[ \frac{1}{\sqrt{\delta\epsilon}} = \frac{1}{\sqrt{\dfrac{1}{k}\cdot\dfrac{k^2}{n^2}}} = \frac{1}{\sqrt{\dfrac{k}{n^2}}} = \frac{n}{\sqrt{k}}. \]

（第一步代入，第二步约去一个 $k$，第三步把根号拆开。）于是 Szegedy 搜索检测标记顶点所需步数的尺度为

\[ O\!\left(\frac{1}{\sqrt{\delta\epsilon}}\right) = O\!\left(\frac{n}{\sqrt{k}}\right). \]

到这里已经能看出参数平衡的雏形：步数 $n/\sqrt{k}$ 随 $k$ 增大而减少（子集越大越容易罩住错误位置，$\epsilon$ 上升是主因），但可以预期每步成本随 $k$ 增大而上升（要维护更大的子集）。最优的 $k$ 在两者之间。若最终取 $k=n^{2/3}$，则步数 $n/\sqrt{k}=n/n^{1/3}=n^{2/3}$ 恰好与 $k$ 同阶——这个"步数等于子集大小"的巧合正是平衡点的特征，第 5 节会严格解出它。但这一切都有一个前提：每步必须足够便宜。如果 $T_{\rm check}$ 本身是 $\Omega(n^2)$，那么总时间至少是 $(n/\sqrt{k})\cdot n^2\gg n^2$，比经典算法还慢。下一节解决这个生死攸关的问题。

4. 压缩子矩阵检查¶

4.1 朴素检查为什么不行¶

按定义检查一个顶点 $(R,S)$ 是否被标记，最直接的办法是显式计算 $k\times n$ 矩阵 $A|_R$ 与 $n\times k$ 矩阵 $B|^S$ 的乘积，再与 $C|_R^S$ 逐元比较。这一个 $k\times k$ 的矩阵乘积需要 $k\cdot k\cdot n=k^2n$ 次标量乘法：即使 $k$ 取最优的 $n^{2/3}$，单次检查也要 $n^{7/3}$ 量级——比整个经典 Freivalds 算法还贵。即使把检查压到"只算一个随机位置的条目"（$O(n)$ 一次内积），也只能检测该位置的错误，无法覆盖子矩阵中任意位置的错误。

更根本的困难在于：标记检查在量子行走中是以相位翻转预言机的形式被调用的，调用次数等于行走步数 $n/\sqrt{k}$。任何 $\Omega(n^2)$ 量级的单步成本都会让总时间重新达到 $\Omega(n^2)$ 甚至更高，量子行走的二次加速被完全吃掉。结论：绝不能显式地计算或存储子矩阵乘积。

4.2 双侧随机指纹¶

出路是对 Freivalds 思想做一次"双侧"推广：不再检查子矩阵等式本身，而是检查它被两个随机向量压缩后的标量等式。在算法开始时（只选一次），随机选取一个行向量 $p$ 和一个列向量 $q$（分量独立均匀地取自有限集合，如 $\{0,1\}$），然后对每个顶点 $(R,S)$ 维护如下三个量：

\[\begin{split} \begin{aligned} a_R &= p|^R\, A|_R,\\ b_S &= B|^S\, q|_S,\\ c_{R,S} &= p|^R\, C|_R^S\, q|_S. \end{aligned} \end{split}\]

记号 $p|^R$ 表示把行向量 $p$ 只保留 $R$ 中的分量（长度 $k$），$q|_S$ 同理。逐个看清这三个量的形状：

$a_R$：长度 $k$ 的行向量 $p|^R$ 乘 $k\times n$ 矩阵 $A|_R$，结果是长度 $n$ 的行向量。展开写就是 $a_R=\sum_{i\in R} p_i\,A_{i,\cdot}$，即 $R$ 中各行的加权和；
$b_S$：$n\times k$ 矩阵 $B|^S$ 乘长度 $k$ 的列向量 $q|_S$，结果是长度 $n$ 的列向量，即 $b_S=\sum_{j\in S} q_j\,B_{\cdot,j}$；
$c_{R,S}=\sum_{i\in R,\,j\in S} p_i\,C_{ij}\,q_j$ 是一个标量。

于是每个顶点附带的数据总量只有 $O(n)$（两个长度 $n$ 的向量加一个标量），与 $k\times k$ 的子矩阵相比是数量级的压缩。标记检查只需比较

\[ a_R\,b_S \stackrel{?}{=} c_{R,S}, \]

左边是两个长度 $n$ 向量的内积，$O(n)$ 次运算；右边是一个标量的读取，$O(1)$。因此

\[ T_{\rm check} = O(n). \]

这个等式为什么等价于（在随机意义下）原来的子矩阵检查？把定义展开：

\[ a_R\,b_S = \bigl(p|^R A|_R\bigr)\bigl(B|^S q|_S\bigr) = p|^R\,\bigl(A|_R\,B|^S\bigr)\,q|_S, \]

（第一步只是代入定义，第二步用矩阵乘法的结合律。）与 $c_{R,S}$ 的定义相减，检查等式等价于

\[ p|^R\,\bigl(A|_R\,B|^S - C|_R^S\bigr)\,q|_S \stackrel{?}{=} 0. \]

记 $E=A|_RB|^S-C|_R^S$（$k\times k$ 的"子矩阵错误"），检查就是问标量 $p|^R E\, q|_S$ 是否为零。这正是 Freivalds 指纹，只是从"矩阵右乘一个随机向量"升级为"矩阵左右各乘一个随机向量"——双侧指纹 (two-sided fingerprint)。

4.3 指纹的可靠性¶

Lemma 4（双侧指纹界）. 设 $E$ 是非零的 $k\times k$ 矩阵，$p,q$ 的分量独立均匀地取自 $\{0,1\}$，则

\[ \Pr_{p,q}[\,p E q \neq 0\,] \ge \frac14. \]

证明。分两步，每步都是 Lemma 1 的配对论证。

第一步，先右乘 $q$。$E\neq 0$ 意味着 $E$ 有某一列是非零列向量，记为 $e$（长度 $k$）。向量 $Eq$ 在 $e$ 所对应方向上的分量是 $e\cdot q$。由 Lemma 1 的配对论证（把 $e$ 当作那里的 $d$），$\Pr_q[\,e\cdot q\neq 0\,]\ge\frac12$，因此

\[ \Pr_q[\,Eq \neq 0\,] \ge \frac12. \]

第二步，固定任意一个满足 $w:=Eq\neq0$ 的结果，再左乘 $p$。$w$ 是非零列向量，$pEw=p\cdot w$ 是 $p$ 与 $w$ 的内积；再用一次配对论证（这次在 $p$ 上做，把 $w$ 当作 $d$），

\[ \Pr_p[\,p\cdot w \neq 0 \mid w\neq 0\,] \ge \frac12. \]

两步独立，合起来 $\Pr[\,pEq\neq0\,]\ge\frac12\cdot\frac12=\frac14$。Q.E.D.

把 Lemma 4 翻译回算法的语言：

若子矩阵等式成立（$E=0$），则对任何 $p,q$ 都有 $p|^RE\,q|_S=0$，指纹检查恒通过——不会误报；
若子矩阵等式不成立（$E\neq0$），随机 $p,q$ 以至少 $\frac14$ 的常数概率使指纹非零，从而该顶点在指纹意义下"看起来是标记的"。

$\frac14$ 是个常数，它的具体数值不重要（取样集合的大小会影响它，见第 6 节），重要的是它与 $n,k$ 无关：漏检的后果只是把有效的标记比例乘上一个常数因子，而常数因子不影响 $O(\cdot)$ 复杂度。更稳妥的做法是把整个算法用独立重选的 $p,q$ 重复常数次，把漏检概率指数压低。因此本课余下部分都把"标记"理解为"被指纹揭示的标记"，标记比例仍记作 $\epsilon=\Theta(k^2/n^2)$（最坏情形）。

4.4 初始化成本 $T_{\rm setup}$¶

算法开始时需要为均匀叠加中的顶点准备数据结构。量子行走的标准做法是先制备所有 $(R,S)$ 的均匀叠加（这只需要对索引寄存器做 Hadamard 类的操作与拒绝采样，成本是关于 $n$ 的低阶项），再为每个顶点计算 $a_R,b_S,c_{R,S}$。从头计算一个顶点的数据：

$a_R=\sum_{i\in R}p_iA_{i,\cdot}$：$k$ 个长度 $n$ 的向量相加（带标量系数），$O(kn)$；
$b_S$：同理 $O(kn)$；
$c_{R,S}$：先算 $p|^R C|_R^S$（长度 $k$ 向量乘 $k\times k$ 矩阵，$O(k^2)$），再与 $q|_S$ 做内积（$O(k)$），共 $O(k^2)$。

合计

\[ T_{\rm setup} = O(kn + k^2) = O(kn), \]

其中第二个等号是因为 $k\le n$ 时 $k^2\le kn$。

4.5 增量更新 $T_{\rm update}$¶

这是整个算法最精巧的一步。行走一步把 $(R,S)$ 变成 $(R',S')$，其中 $R'=(R\setminus\{i_{\rm out}\})\cup\{i_{\rm in}\}$（$S$ 同理）。如果每个顶点都从头重算 $a_{R'}$，就要 $O(kn)$，总复杂度立刻爆炸。关键观察是：$a_R$ 是求和形式 $\sum_{i\in R}p_iA_{i,\cdot}$，一次交换只改变求和式中的一项，因此

\[ a_{R'} = a_R - p_{i_{\rm out}}\,A_{i_{\rm out},\cdot} + p_{i_{\rm in}}\,A_{i_{\rm in},\cdot}. \]

减去旧行的贡献、加上新行的贡献，各是 $O(n)$ 次标量运算，所以 $a$ 的更新是 $O(n)$。同理

\[ b_{S'} = b_S - q_{j_{\rm out}}\,B_{\cdot,j_{\rm out}} + q_{j_{\rm in}}\,B_{\cdot,j_{\rm in}}, \]

也是 $O(n)$。标量 $c_{R,S}=\sum_{i\in R,j\in S}p_iC_{ij}q_j$ 的更新稍细：交换 $R$ 中的一个元素 $i_{\rm out}\to i_{\rm in}$ 时，双重求和里所有含 $i_{\rm out}$ 的项（共 $|S|=k$ 项）被含 $i_{\rm in}$ 的 $k$ 项替换，即

\[ c_{R',S} = c_{R,S} - p_{i_{\rm out}}\sum_{j\in S}C_{i_{\rm out},j}\,q_j + p_{i_{\rm in}}\sum_{j\in S}C_{i_{\rm in},j}\,q_j, \]

每个内层求和是 $O(k)$；交换 $S$ 中的一个元素同理是 $O(k)$。把三者相加，

\[ T_{\rm update} = O(n) + O(n) + O(k) = O(n), \]

最后一步用了 $k\le n$。于是每步行走和每次相位标记都只需 $O(n)$，而不是重新计算整个子矩阵。

还有一层量子实现上的细节值得点明：行走是相干地作用于所有顶点的叠加的，因此上述更新必须可逆地（用酉线路）完成。增量更新恰好适合这一点——"减去一项、加上一项"可以做成受控的可逆算术，而不需要为旧顶点保留整份垃圾数据。本课按量子行走文献的标准做法，假定矩阵元素可以被相干地随机访问（量子 RAM 模型）；这一假设的边界见第 6 节。

4.6 一个指纹小例子¶

用最小规模的数字把第 4.2–4.3 节走一遍。取 $k=2$，假设某个顶点 $(R,S)$ 上的子矩阵错误为

\[\begin{split} E = A|_R\,B|^S - C|_R^S = \begin{pmatrix}0 & 0\\ 0 & 1\end{pmatrix}, \end{split}\]

即子矩阵只有右下角一个条目是错的。$p$（行向量）与 $q$（列向量）各等可能地取 $\{0,1\}^2$ 中的四个值。计算 $pEq$：先算

\[\begin{split} Eq = \begin{pmatrix}0 & 0\\ 0 & 1\end{pmatrix}\begin{pmatrix}q_1\\ q_2\end{pmatrix} = \begin{pmatrix}0\\ q_2\end{pmatrix}, \end{split}\]

所以 $Eq\neq0$ 当且仅当 $q_2=1$，概率恰为 $\frac12$（对应 Lemma 4 证明的第一步）。再左乘 $p$：

\[ pEq = p_1\cdot0 + p_2\cdot q_2 = p_2q_2, \]

非零当且仅当 $p_2=q_2=1$，联合概率恰为 $\frac14$（第二步：给定 $q_2=1$，需要 $p_2=1$，条件概率 $\frac12$）。四个 $(p,q)$ 组合中只有一个，即 $p=(0,1)$、$q=(0,1)$，能检出这个错误——Lemma 4 的 $\frac14$ 在本例取到等号。反过来，如果 $E=0$（子矩阵等式成立），则无论 $p,q$ 取什么，$pEq=0$ 恒成立，指纹永不误报。单边错误的结构在小例子里一目了然。

再演示一次增量更新。设 $n=3$、$k=2$，$R=\{1,2\}$，$p=(1,1,0)$，且

\[\begin{split} A = \begin{pmatrix}1 & 0 & 2\\ 0 & 1 & 1\\ 3 & 1 & 0\end{pmatrix}. \end{split}\]

则 $p|^R=(1,1)$（取 $p$ 的第 $1,2$ 分量），

\[ a_R = 1\cdot(1,0,2) + 1\cdot(0,1,1) = (1,1,3). \]

现在行走一步，把 $R$ 中的元素 $2$ 换成 $3$，即 $R'=\{1,3\}$。从头算是 $a_{R'}=1\cdot(1,0,2)+0\cdot(3,1,0)=(1,0,2)$（注意 $p_3=0$）。用增量公式：

\[ a_{R'} = a_R - p_2A_{2,\cdot} + p_3A_{3,\cdot} = (1,1,3) - 1\cdot(0,1,1) + 0\cdot(3,1,0) = (1,0,2). \]

两法结果一致，但增量法只做了两个长度 $n$ 的向量加减，$O(n)$；从头算是 $k$ 个向量相加，$O(kn)$。$k$ 大时差距就是第 5 节复杂度平衡里"每步 $O(n)$ 而非 $O(kn)$"的来源。

5. 总复杂度的平衡¶

现在把所有零件装进 Szegedy 框架的总公式

\[ T = O\!\left( T_{\rm setup} + \frac{1}{\sqrt{\delta\epsilon}}\, \bigl(T_{\rm update} + T_{\rm check}\bigr) \right). \]

在最坏情形（$D$ 只有一个错误条目）下，逐项代入前四节的结果：

\[ T_{\rm setup}=O(kn),\qquad T_{\rm update}+T_{\rm check}=O(n),\qquad \delta=\Theta(1/k),\qquad \epsilon=\Theta(k^2/n^2), \]

以及第 3.4 节算好的步数 $1/\sqrt{\delta\epsilon}=O(n/\sqrt{k})$，得到

\[ T = O\!\left(kn + \frac{n}{\sqrt{k}}\cdot n\right) = O\!\left(kn + \frac{n^2}{\sqrt{k}}\right). \]

这个表达式的结构非常清晰，两个因子各有一段来历：

第一项 $kn$：初始化。$k$ 越大，要建立的指纹越长（$k$ 行求和，每行长度 $n$）。它随 $k$ 单调上升。
第二项 $n^2/\sqrt{k}$：行走。其中步数 $n/\sqrt{k}$ 随 $k$ 下降（$k$ 越大 $\epsilon$ 越大，标记越密，搜索越快），每步成本 $n$ 与 $k$ 无关（这是第 4 节压缩数据结构的全部意义——$T_{\rm update}$ 和 $T_{\rm check}$ 里没有 $k$ 的影子）。

一项随 $k$ 增、一项随 $k$ 减，最优的 $k$ 在两项同阶处取得（这是平衡两个幂律项的标准原理：若 $k$ 偏离平衡点，较大的那一项都会超过平衡值）。令两项相等：

\[ kn = \frac{n^2}{\sqrt{k}} \quad\Longrightarrow\quad k\cdot\sqrt{k} = n \quad\Longrightarrow\quad k^{3/2} = n \quad\Longrightarrow\quad k = n^{2/3}. \]

（第一步两边同除以 $n$ 并同乘 $\sqrt{k}$；第二、三步只是幂的整理。）代回任一项：

\[ kn = n^{2/3}\cdot n = n^{5/3},\qquad \frac{n^2}{\sqrt{k}} = \frac{n^2}{n^{1/3}} = n^{5/3}, \]

两项果然同阶，于是

\[ \boxed{\,T = O\!\left(n^{5/3}\right)\,} \]

比经典最优的 $\Theta(n^2)$ 快了 $n^{1/3}$ 的因子。作为自洽性检查：此时步数 $n/\sqrt{k}=n^{2/3}=k$，即"行走步数恰好等于子集大小"，正应了第 3.4 节的预告——这不是巧合，而是"初始化项 $kn$ 与行走项同阶"这一平衡条件的直接推论（$kn=n^2/\sqrt{k}$ 两边除以 $n$ 正是 $k=n/\sqrt{k}$）。

为什么压缩检查是不可或缺的？ 回过头看，如果不用第 4 节的指纹，而是每次检查都显式计算子矩阵乘积（$T_{\rm check}=k^2n$，见第 4.1 节），总复杂度会变成

\[ T = O\!\left(kn + \frac{n}{\sqrt{k}}\cdot k^2n\right) = O\!\left(kn + n^2 k^{3/2}\right). \]

第二项随 $k$ 上升，平衡被打破：为了压低它只能把 $k$ 往小取，而 $k=O(1)$ 时第二项是 $O(n^2)$——恰好退回经典复杂度，量子加速完全消失。这就是为什么本课说"必须设计可增量更新的数据结构"不是工程修饰，而是算法成立的先决条件。

错误更多时的改进。以上按最坏情形（单个错误）分析。若 $D$ 有 $w$ 个错误条目且分布较分散，能罩住错误的 $(R,S)$ 对显著增多：粗略地说，$w$ 个错误散布在约 $w$ 行、$w$ 列时，$\epsilon$ 从 $(k/n)^2$ 上升到 $\sim(wk/n)^2$ 量级，步数随之按 $1/\sqrt{\epsilon}$ 下降；但改进有一个饱和点——错误再密集，标记比例也不可能超过 $1$，且高度集中的错误（挤在少数几行里）并不能成比例地帮助搜索。把这一效应做严格后，论文给出的期望时间界为

\[ O\!\left( \frac{n^{5/3}} {\min(w,\sqrt{n})^{1/3}} \right). \]

这里 $\min(w,\sqrt n)$ 的截断正是上述饱和效应的体现；推导需要更精细地统计"行错误数×列错误数"的联合分布，超出本课范围，我们只引用结论。无论 $w$ 多大，这个界都不会比 $w=1$ 的最坏结论 $O(n^{5/3})$ 更差。

6. 正确性与模型边界¶

把散落于各节的正确性论证收拢成一个完整的画面，再明确算法的适用边界。

完备性（$AB=C$ 时永不错拒）。若 $AB=C$，由 Lemma 2，所有子矩阵等式 $A|_RB|^S=C|_R^S$ 都成立，进而对任何 $p,q$ 都有 $p|^RE\,q|_S=0$（因为 $E=0$）。于是不存在任何（指纹意义下的）标记状态，行走中的相位翻转恒为恒等操作，均匀叠加在 Szegedy 行走下保持不变，干涉检测永远指示"无标记"，算法总回答"相等"。

可靠性（$AB\neq C$ 时以高概率拒绝）。若 $D\neq0$，任取一个错误位置 $(i,j)$：由 Lemma 3，至少 $(k/n)^2$ 比例的 $(R,S)$ 对上子矩阵错误 $E\neq0$；由 Lemma 4，随机 $p,q$ 以至少 $\frac14$ 的概率把这些对变成指纹可检的标记状态。两件事合起来，有效的标记比例是 $\Theta(k^2/n^2)$（常数因子被吸收）。Szegedy 定理保证量子行走以至少 $\frac23$ 的单次概率把"存在标记"与"无标记"区分开——机制上，行走把标记顶点上的振幅与初始均匀叠加所对应的平稳态分离开，末段再做一次 Hadamard 型的干涉测量，检测末态与初始均匀态的内积是否偏离 $1$。把整条算法（含重新随机选取 $p,q$）独立重复常数次，即可把单边错误率压到任意常数以下，比如拒绝概率至少 $2/3$。

单边错误的定性。与 Freivalds 一样，本算法是单边错误：相等的乘积永不被拒绝，不相等的乘积可能因"随机 $p,q$ 恰好掩盖了所有错误"而被暂时接受，重复运行指数压低这一概率。

代数结构的边界。算法适用于无零因子的交换环（论文以整环 (integral domain) 表述），整数环 $\mathbb{Z}$、任意域（如有理数、有限域）都是合法实例。限制的来源在指纹引理：Lemma 1 与 Lemma 4 的配对论证要求"非零元素 $d$ 使得 $x$ 与 $x\pm d$ 不可能同时为零"，并进而要求随机线性组合以常数概率非零；在含零因子的环上这类概率界可能退化，随机指纹的具体成功概率也依赖取样集合的大小与结构。本课的常数（$\frac12$、$\frac14$）是按 $\{0,1\}$ 取样算的，换成别的取样集合结论仍是"常数"，只是数值不同。

计算模型的边界。复杂度 $O(n^{5/3})$ 是在"矩阵元素可被相干地随机访问"的模型（量子 RAM / 量子查询模型）下成立的：第 4 节的增量更新要在叠加态上对任意指定的矩阵条目做受控读取。如果读取模型不允许这种相干随机访问（例如矩阵存在经典磁带、只能顺序读取），查询与门时间还要加上数据访问成本，$n^{5/3}$ 的结论不再自动成立。

问题本身的边界。本算法解决的是验证而非计算：它输出"$AB=C$ 是否成立"的一个比特，不输出 $AB$ 的全部 $n^2$ 个条目（输出本身就要 $\Omega(n^2)$ 时间，不可能做到 $n^{5/3}$）。它回答的是"信不信这份答案"，而不是"答案是什么"。

7. 小结¶

验证 $AB=C$ 不必计算 $AB$：经典 Freivalds 用随机向量指纹 $Dr\stackrel?=0$ 在 $O(n^2)$ 内完成，单边错误，配对论证给出检出概率 $\ge\frac12$。
量子算法把验证改写为搜索：标记顶点是包含错误条目的行/列子集对 $(R,S)$，依据是限制的乘积等于乘积的限制（Lemma 2）。
搜索在乘积 Johnson 图 $J(n,k)\times J(n,k)$ 上进行；Johnson 图谱隙 $\delta=\Theta(1/k)$ 与标记比例 $\epsilon\approx(k/n)^2$ 共同决定量子行走步数 $O(n/\sqrt{k})$。
双侧随机指纹 $p,q$ 把 $k\times k$ 子矩阵乘法压成一个长度 $n$ 的内积，检查成本 $O(n)$；交换一个元素时指纹可增量维护，更新成本同为 $O(n)$——这是查询加速能变成时间加速的关键。
取 $k=n^{2/3}$ 平衡初始化 $kn$ 与行走 $n^2/\sqrt{k}$，得到 $O(n^{5/3})$；错误更多时界改进为 $O(n^{5/3}/\min(w,\sqrt n)^{1/3})$。

练习题¶

练习 1【Freivalds 指纹算法与配对论证】（→ 1.1 节）

取第 1.2 节的矩阵 $A,B$ 与错误答案 $C$（仅 $(2,2)$ 条目错为 $51$），对 $r=(0,1)^T$ 依次计算 $u=Br$、$v=Au$、$w=Cr$，验证 $v-w=Dr$，并判断本次运行是否发现错误。
补全 Lemma 1 中未写出的细节：设 $d$ 为非零行向量、$d_{j_0}\neq 0$，证明把 $\{0,1\}^n$ 按"翻转第 $j_0$ 位"配对后，每对中至多有一个向量满足 $d\cdot r=0$，从而 $\Pr[d\cdot r\neq 0]\ge\frac12$。取样集合换成 $\{-1,0,1\}$ 时，这个论证需要怎样修改？

提示：固定其余分量后 $d\cdot r$ 是 $r_{j_0}$ 的一次式，一次方程 $c+d_{j_0}x=0$ 至多有一个解，故三个取值中至少两个给出非零内积。

练习 2【验证的搜索改写与标记比例】（→ 2.1 节）

设 $n=4$、$k=2$、$R=\{1,3\}$、$S=\{2,4\}$。写出 $A|_R$、$B|^S$、$C|_R^S$ 各是多少行多少列，并说明：若唯一的错误条目位于 $(1,4)$ 位置，为什么 $(R,S)$ 必是标记状态。
对单个错误位置 $(i,j)$，用组合数恒等式 $\binom{n-1}{k-1}/\binom{n}{k}=k/n$ 严格推导 $\Pr[i\in R\ \text{且}\ j\in S]=(k/n)^2$。若 $D$ 有恰好 $w$ 个错误条目且两两不同行不同列，标记比例的下界是什么？

提示：分别估计"至少一个错误行落入 $R$"与"至少一个错误列落入 $S$"的概率，行与列的选取相互独立，且 $\Pr[R\ \text{避开全部}w\ \text{个错误行}]=\binom{n-w}{k}/\binom{n}{k}$。

练习 3【Johnson 图与谱隙】（→ 3.2 节）

计算 $J(5,2)$ 的顶点数与正则度，并列出子集 $\{1,2\}$ 的全部邻居。
从 Johnson 图邻接矩阵特征值 $\lambda_j=(k-j)(n-k-j)-j$ 出发，验证 $\lambda_1=k(n-k)-n$，并证明 $k\le n/2$ 时归一化谱隙 $n/(k(n-k))$ 落在 $[1/k,\,2/k]$ 内，即 $\delta=\Theta(1/k)$。

提示：$k\le n/2$ 时 $n/2\le n-k\le n$，故 $kn/2\le k(n-k)\le kn$，取倒数放缩。

练习 4【Szegedy 框架与步数估计】（→ 3.4 节）

把 $\delta=\Theta(1/k)$ 与 $\epsilon=\Theta(k^2/n^2)$ 代入 $1/\sqrt{\delta\epsilon}$，逐步化简得到 $O(n/\sqrt{k})$；再取 $k=n^{2/3}$，写出步数的具体量级。
解释为什么"标记检查不增加矩阵查询"仍可能消耗 $\Omega(n^2)$ 的门时间——即查询复杂度与时间复杂度的区别——并说明双侧指纹 + 增量更新是如何把二者同时压低的。

提示：总时间公式把 $(T_{\rm update}+T_{\rm check})$ 乘了 $n/\sqrt{k}$ 倍；若 $T_{\rm check}=\Omega(n^2)$，仅此一项就是 $\Omega(n^{5/2})$。

练习 5【双侧随机指纹】（→ 4.2 节）

写出 $a_R$、$b_S$、$c_{R,S}$ 的定义式，指出各自是行向量、列向量还是标量以及长度，并解释检查 $a_R\,b_S\stackrel{?}{=}c_{R,S}$ 为什么只需 $O(n)$ 次运算。
构造一个非零的 $2\times 2$ 矩阵 $E$，使得对一切行向量 $p$ 都有 $pE\binom{1}{1}=0$；由此说明只在一侧随机（$q$ 固定为全 1 向量）时指纹可能完全失效，而双侧随机（Lemma 4）保证检出概率至少 $\frac14$。

提示：只需让 $E\binom{1}{1}=\binom{0}{0}$，即 $E$ 的每一行分量之和为零。

练习 6【指纹的增量更新】（→ 4.5 节）

在第 4.6 节的例子中再走一步：从 $R'=\{1,3\}$ 出发把元素 $1$ 换成 $2$，分别用从头计算与增量公式求新的 $a$，验证两者一致。
设一步行走把 $R$ 中的 $i_{\rm out}$ 换成 $i_{\rm in}$、把 $S$ 中的 $j_{\rm out}$ 换成 $j_{\rm in}$。写出 $a_R$、$b_S$、$c_{R,S}$ 三个量的完整更新公式（注意 $c$ 在 $R$、$S$ 同时变化时有一处交叉项需要小心处理），并逐项统计运算次数，验证 $T_{\rm update}=O(n)$。

提示：把 $c$ 的更新拆成"先换 $R$、再换 $S$"两个各改 $k$ 项的子步骤复合。

练习 7【复杂度平衡】（→ 5 节）

分别取 $k=1$ 与 $k=n$，计算 $T(k)=kn+n^2/\sqrt{k}$ 的量级，说明两个极端选取都退化为 $\Theta(n^2)$。
对 $T(k)=kn+n^2/\sqrt{k}$ 做数量级平衡：令两项相等解出 $k=n^{2/3}$，并验证偏离平衡（$k=n^{1/2}$ 与 $k=n^{4/5}$）时总时间都严格变差。再计算：若标记检查改为显式计算子矩阵乘积（$T_{\rm check}=k^2n$），最好的 $k$ 能给出什么总时间？由此说明压缩检查的必要性。

提示：显式检查时 $T=O(kn+n^2k^{3/2})$，第二项随 $k$ 单调上升，只能把 $k$ 压到常数。

练习 8【正确性与模型边界】（→ 6 节）

复述正确性的两条主线：$AB=C$ 时算法为何永不误拒（依次引用 Lemma 2 与"指纹恒为零"）；$AB\neq C$ 时有效标记比例为何仍是 $\Theta(k^2/n^2)$。
证明任何输出 $AB$ 全部 $n^2$ 个条目的算法至少需要 $\Omega(n^2)$ 时间，并说明本算法为何不受此下界限制；再指出复杂度 $O(n^{5/3})$ 的成立依赖哪两个模型假设。

提示：输出规模本身就是 $n^2$；模型假设见第 6 节最后三段（无零因子的交换环、矩阵元素的相干随机访问）。

参考文献¶

Zoo 编号 6：A. Ambainis 等，Quantum Matrix Verification，未发表手稿，2002。
Zoo 编号 19：Harry Buhrman 与 Robert Špalek, Quantum Verification of Matrix Products.
Zoo 编号 85：Mario Szegedy, Quantum Speed-up of Markov Chain Based Algorithms, FOCS 2004.

量子矩阵乘积验证：Johnson 图量子行走的 \(O(n^{5/3})\) 算法¶