量子矩阵乘积验证

给定三个 $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 节会给出所需的结论并解释其含义。

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

矩阵乘法是整个线性代数计算的瓶颈操作。两个 $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\ne 0$，那么一个随机向量 $r$ 大概率不在 $D$ 的核里，从而 $Dr\ne 0$ 会暴露这一点。

Freivalds 算法：

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

$$u=Br,v=Au,w=Cr;$$

3. 若 $v\ne w$，回答"$AB\ne 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\ne 0$"。下面这条引理给出错误概率界，它是整个 Freivalds 方法的核心。

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

${\mathrm{Pr}}_r[Dr\ne 0]\ge \frac{1}{2}.$

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

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

$$d\cdot r^{\prime }=\sum _j{d}_j{r}_j^{\prime }=\sum _{j\ne 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}\ne 0$ 矛盾。因此每一对中至少有一个向量满足 $d\cdot r\ne 0$，非零内积的比例至少是一半，即 $\mathrm{Pr}[d\cdot r\ne 0]\ge \frac{1}{2}$。Q.E.D.

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

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

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

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

1.2 一个 $2\times 2$ 小例子

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

$$A=\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right),B=\left(\begin{array}{cc}5& 6\\ 7& 8\end{array}\right).$$

真实的乘积是

$$AB=\left(\begin{array}{cc}1\cdot 5+2\cdot 7& 1\cdot 6+2\cdot 8\\ 3\cdot 5+4\cdot 7& 3\cdot 6+4\cdot 8\end{array}\right)=\left(\begin{array}{cc}19& 22\\ 43& 50\end{array}\right).$$

假设对方交来的答案是

$$C=\left(\begin{array}{cc}19& 22\\ 43& 51\end{array}\right),$$

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

$$D=AB-C=\left(\begin{array}{cc}0& 0\\ 0& -1\end{array}\right).$$

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

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

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

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

$$u=Br=\left(\begin{array}{c}5+6\\ 7+8\end{array}\right)=\left(\begin{array}{c}11\\ 15\end{array}\right),v=Au=\left(\begin{array}{c}1\cdot 11+2\cdot 15\\ 3\cdot 11+4\cdot 15\end{array}\right)=\left(\begin{array}{c}41\\ 93\end{array}\right),$$ $$w=Cr=\left(\begin{array}{c}19+22\\ 43+51\end{array}\right)=\left(\begin{array}{c}41\\ 94\end{array}\right).$$

$v\ne w$（第二个分量 $93\ne 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\ne 0$ 的 $r$）行不通：单次检查 $Dr$ 就要 $O(n^2)$ 时间，即使搜索本身只要常数步，总时间也没有改观。Buhrman–Špalek 的选择是把搜索空间取为子矩阵，而不是随机向量。

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

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

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

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

2.2 标记比例 $ϵ$

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

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

$$ϵ\ge {\left(\frac{k}{n}\right)}^2.$$

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

$$\mathrm{Pr}[i\in R]=\frac{\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)}{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}=\frac{(n-1)!}{(k-1)!(n-k)!}\cdot \frac{k!(n-k)!}{n!}=\frac{k}{n}.$$

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

$$\mathrm{Pr}[(R,S)\text{被标记}]\ge \mathrm{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$ 只有一个错误条目，此时 $ϵ\approx (k/n{)}^2$ 就是实际的标记比例，后面第 5 节的复杂度平衡就按这个最坏情形做。错误条目更多时 $ϵ$ 上升，算法只会更快（第 5 节末尾会回到这一点）。

3. Johnson 图与 Szegedy 量子行走

3.1 Johnson 图 $J(n,k)$

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

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

$$|R\cap R^{\prime }|=k-1⟺R^{\prime }=(R\setminus \{i_{\mathrm{out}}\})\cup \{i_{\mathrm{in}}\}$$

对某对 $i_{\mathrm{out}}\in R$、$i_{\mathrm{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,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$，顶点中被标记的比例为 $ϵ$。则存在一个量子行走算法，用 $O\left(\frac{1}{\sqrt{\delta ϵ}}\right)$ 步行走，判定标记顶点是否存在（单边有界错误：无标记时总回答”无”，有标记时以至少 $\frac{2}{3}$ 的概率回答”有”）。

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

$$T=O\left(T_{\mathrm{setup}}+\frac{1}{\sqrt{\delta ϵ}}(T_{\mathrm{update}}+T_{\mathrm{check}})\right),$$

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

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

3.4 步数估计

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

$$\frac{1}{\sqrt{\delta ϵ}}=\frac{1}{\sqrt{\frac{1}{k}\cdot \frac{k^2}{n^2}}}=\frac{1}{\sqrt{\frac{k}{n^2}}}=\frac{n}{\sqrt{k}}.$$

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

$$O\left(\frac{1}{\sqrt{\delta ϵ}}\right)=O\left(\frac{n}{\sqrt{k}}\right).$$

到这里已经能看出参数平衡的雏形：步数 $n/\sqrt{k}$ 随 $k$ 增大而减少（子集越大越容易罩住错误位置，$ϵ$ 上升是主因），但可以预期每步成本随 $k$ 增大而上升（要维护更大的子集）。最优的 $k$ 在两者之间。若最终取 $k=n^{2/3}$，则步数 $n/\sqrt{k}=n/n^{1/3}=n^{2/3}$ 恰好与 $k$ 同阶——这个”步数等于子集大小”的巧合正是平衡点的特征，第 5 节会严格解出它。但这一切都有一个前提：每步必须足够便宜。如果 $T_{\mathrm{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^{2}n$ 次标量乘法：即使 $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{array}{rl}{a}_R& =p{|}^{R}A{|}_R,\\ b_S& =B{|}^{S}q{|}_S,\\ c_{R,S}& =p{|}^{R}C{|}_R^{S}q{|}_S.\end{array}$$

记号 $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_{\mathrm{check}}=O(n).$$

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

$$a_R{b}_S=\left(p{|}^{R}A{|}_R\right)\left(B{|}^{S}q{|}_S\right)=p{|}^R\left(A{|}_{R}B{|}^S\right)q{|}_S,$$

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

$$p{|}^R(A{|}_{R}B{|}^S-C{|}_R^S)q{|}_S\stackrel{?}{=}0.$$

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

4.3 指纹的可靠性

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

$$\underset{p,q}{\mathrm{Pr}}[pEq\ne 0]\ge \frac{1}{4}.$$

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

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

$$\underset{q}{\mathrm{Pr}}[Eq\ne 0]\ge \frac{1}{2}.$$

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

$$\underset{p}{\mathrm{Pr}}[p\cdot w\ne 0\mid w\ne 0]\ge \frac{1}{2}.$$

两步独立，合起来 $\mathrm{Pr}[pEq\ne 0]\ge \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{4}$。Q.E.D.

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

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

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

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

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

• $a_R={\sum }_{i\in R}{p}_i{A}_{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_{\mathrm{setup}}=O(kn+k^2)=O(kn),$$

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

4.5 增量更新 $T_{\mathrm{update}}$

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

$$a_{R^{\prime }}=a_R-p_{i_{\mathrm{out}}}{A}_{i_{\mathrm{out}},\cdot }+p_{i_{\mathrm{in}}}{A}_{i_{\mathrm{in}},\cdot }.$$

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

$$b_{S^{\prime }}=b_S-q_{j_{\mathrm{out}}}{B}_{\cdot ,j_{\mathrm{out}}}+q_{j_{\mathrm{in}}}{B}_{\cdot ,j_{\mathrm{in}}},$$

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

$$c_{R^{\prime },S}=c_{R,S}-p_{i_{\mathrm{out}}}\sum _{j\in S}{C}_{i_{\mathrm{out}},j}{q}_j+p_{i_{\mathrm{in}}}\sum _{j\in S}{C}_{i_{\mathrm{in}},j}{q}_j,$$

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

$$T_{\mathrm{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)$ 上的子矩阵错误为

$$E=A{|}_{R}B{|}^S-C{|}_R^S=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right),$$

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

$$Eq=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right)\left(\begin{array}{c}{q}_1\\ q_2\end{array}\right)=\left(\begin{array}{c}0\\ q_2\end{array}\right),$$

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

$$pEq=p_1\cdot 0+p_2\cdot q_2=p_2{q}_2,$$

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

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

$$A=\left(\begin{array}{ccc}1& 0& 2\\ 0& 1& 1\\ 3& 1& 0\end{array}\right).$$

则 $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^{\prime }=\{1,3\}$。从头算是 $a_{R^{\prime }}=1\cdot (1,0,2)+0\cdot (3,1,0)=(1,0,2)$（注意 $p_3=0$）。用增量公式：

$$a_{R^{\prime }}=a_R-p_2{A}_{2,\cdot }+p_3{A}_{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_{\mathrm{setup}}+\frac{1}{\sqrt{\delta ϵ}}(T_{\mathrm{update}}+T_{\mathrm{check}})\right).$$

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

$$T_{\mathrm{setup}}=O(kn),T_{\mathrm{update}}+T_{\mathrm{check}}=O(n),\delta =\Theta (1/k),ϵ=\Theta (k^2/n^2),$$

以及第 3.4 节算好的步数 $1/\sqrt{\delta ϵ}=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$ 越大 $ϵ$ 越大，标记越密，搜索越快），每步成本 $n$ 与 $k$ 无关（这是第 4 节压缩数据结构的全部意义——$T_{\mathrm{update}}$ 和 $T_{\mathrm{check}}$ 里没有 $k$ 的影子）。

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

$$kn=\frac{n^2}{\sqrt{k}}⟹k\cdot \sqrt{k}=n⟹k^{3/2}=n⟹k=n^{2/3}.$$

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

$$kn=n^{2/3}\cdot n=n^{5/3},\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_{\mathrm{check}}=k^{2}n$，见第 4.1 节），总复杂度会变成

$$T=O\left(kn+\frac{n}{\sqrt{k}}\cdot k^{2}n\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$ 列时，$ϵ$ 从 $(k/n{)}^2$ 上升到 $\sim (wk/n{)}^2$ 量级，步数随之按 $1/\sqrt{ϵ}$ 下降；但改进有一个饱和点——错误再密集，标记比例也不可能超过 $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{|}_{R}B{|}^S=C{|}_R^S$ 都成立，进而对任何 $p,q$ 都有 $p{|}^{R}Eq{|}_S=0$（因为 $E=0$）。于是不存在任何（指纹意义下的）标记状态，行走中的相位翻转恒为恒等操作，均匀叠加在 Szegedy 行走下保持不变，干涉检测永远指示”无标记”，算法总回答”相等”。

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

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

代数结构的边界。算法适用于无零因子的交换环（论文以整环 (integral domain) 表述），整数环 $\mathbb{Z}$、任意域（如有理数、有限域）都是合法实例。限制的来源在指纹引理：Lemma 1 与 Lemma 4 的配对论证要求”非零元素 $d$ 使得 $x$ 与 $x\pm d$ 不可能同时为零”，并进而要求随机线性组合以常数概率非零；在含零因子的环上这类概率界可能退化，随机指纹的具体成功概率也依赖取样集合的大小与结构。本词条的常数（$\frac{1}{2}$、$\frac{1}{4}$）是按 $\{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 \frac{1}{2}$。
• 量子算法把验证改写为搜索：标记顶点是包含错误条目的行/列子集对 $(R,S)$，依据是限制的乘积等于乘积的限制（Lemma 2）。
• 搜索在乘积 Johnson 图 $J(n,k)\times J(n,k)$ 上进行；Johnson 图谱隙 $\delta =\Theta (1/k)$ 与标记比例 $ϵ\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. （配对论证）补全 Lemma 1 中未写出的细节：设 $d$ 为非零行向量、$d_{j_0}\ne 0$，证明把 $\{0,1{\}}^n$ 按”翻转第 $j_0$ 位”配对后，每对中至多有一个向量满足 $d\cdot r=0$，从而 $\mathrm{Pr}[d\cdot r\ne 0]\ge \frac{1}{2}$。取样集合换成 $\{-1,0,1\}$ 时，这个论证需要怎样修改？
2. （标记比例）对单个错误位置 $(i,j)$，用组合数恒等式 $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)/\left(\genfrac{}{}{0ex}{}{n}{k}\right)=k/n$ 严格推导 $\mathrm{Pr}[i\in R\text{且}j\in S]=(k/n{)}^2$。若 $D$ 有恰好 $w$ 个错误条目且两两不同行不同列，标记比例的下界是什么？
3. （谱隙）从 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)$。
4. （增量更新）设一步行走把 $R$ 中的 $i_{\mathrm{out}}$ 换成 $i_{\mathrm{in}}$、把 $S$ 中的 $j_{\mathrm{out}}$ 换成 $j_{\mathrm{in}}$。写出 $a_R$、$b_S$、$c_{R,S}$ 三个量的完整更新公式（注意 $c$ 在 $R$、$S$ 同时变化时有一处交叉项需要小心处理），并逐项统计运算次数，验证 $T_{\mathrm{update}}=O(n)$。
5. （复杂度平衡）对 $T(k)=kn+n^2/\sqrt{k}$ 做数量级平衡：令两项相等解出 $k=n^{2/3}$，并验证偏离平衡（$k=n^{1/2}$ 与 $k=n^{4/5}$）时总时间都严格变差。再计算：若标记检查改为显式计算子矩阵乘积（$T_{\mathrm{check}}=k^{2}n$），最好的 $k$ 能给出什么总时间？由此说明压缩检查的必要性。
6. （概念）解释为什么”标记检查不增加矩阵查询”仍可能消耗 $\Omega (n^2)$ 的门时间——即查询复杂度与时间复杂度的区别——并说明双侧指纹 + 增量更新是如何把二者同时压低的。

参考文献

• 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.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch09-algebra-number-theory/matrix-product-verification
• 内容遵循 CC BY-NC-SA 4.0 许可协议