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

给定三个 $n\times n$ 矩阵 $A,B,C$，计算 $AB$ 很贵，但验证声称的结果是否满足 $AB=C$ 可能更容易。经典 Freivalds 算法用 $O(n^2)$ 时间完成随机验证；量子算法通过两个 Johnson 图上的行走把最坏时间降到 $O(n^{5/3})$。本课尤其强调一个常被忽略的区别：查询复杂度下降不自动保证真实运行时间下降，必须设计可增量更新的数据结构。

## 1. 经典基线：Freivalds 指纹

令

$$
D=AB-C.
$$

从有限集合随机选择列向量 $r$，依次计算

$$
u=Br,\qquad v=Au,\qquad w=Cr.
$$

若 $v\ne w$，必有 $AB\ne C$。若 $D\ne0$，随机 $r$ 落入核 $\ker D$ 的概率有常数上界；重复即可指数降低错误率。三次矩阵--向量乘法各需 $O(n^2)$ 标量操作，因此验证比直接使用朴素 $O(n^3)$ 乘法便宜。

Freivalds 是单边错误：正确乘积永不被拒绝，错误乘积可能因随机指纹碰撞而暂时通过。

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

选大小均为 $k$ 的集合

$$
R,S\subseteq[n].
$$

$R$ 指定 $A,C$ 的行，$S$ 指定 $B,C$ 的列。若子矩阵

$$
A|_R\,B|^S\ne C|_R^S,
$$

就称 $(R,S)$ 为标记状态。只要 $D$ 有一个错误位置 $(i,j)$，随机 $R,S$ 同时包含 $i,j$ 的概率约为

$$
\epsilon\approx\left(\frac{k}{n}\right)^2.
$$

算法在图

$$
J(n,k)\times J(n,k)
$$

上行走。Johnson 图 $J(n,k)$ 的顶点是所有 $k$ 元子集，相邻顶点只交换一个元素。一次行走同时替换一行和一列；乘积图的谱隙为

$$
\delta=\Theta(1/k).
$$

Szegedy 搜索检测标记顶点所需步数尺度为

$$
O\!\left(\frac1{\sqrt{\delta\epsilon}}\right)
=O\!\left(\frac n{\sqrt k}\right).
$$

取 $k=n^{2/3}$ 时，步数与 $k$ 同阶。这解释了指数 $2/3$ 从何而来，但尚未解释每步如何足够便宜。

## 3. 压缩子矩阵检查

若每次标记检查都显式计算 $A|_RB|^S$，时间会重新达到 $\Omega(n^2)$。算法改为随机选择行向量 $p$ 和列向量 $q$，维护

$$
\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}
$$

这里 $a_R$ 是长度 $n$ 的行向量，$b_S$ 是长度 $n$ 的列向量，$c_{R,S}$ 是标量。标记检查只需比较

$$
a_Rb_S\stackrel?=c_{R,S},
$$

即

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

若子矩阵正确，等式对任何 $p,q$ 都成立；若错误，随机双侧指纹以常数概率揭示差异。重复常数次即可补偿漏检。

初始化所有数据需

$$
O(kn+k^2)=O(kn)
$$

时间。行走只交换 $R,S$ 中各一个索引，因此 $a_R,b_S,c_{R,S}$ 可用被删/新增的行列增量更新，每步和每次相位标记均为 $O(n)$，而不是重新计算整个子矩阵。

## 4. 总复杂度的平衡

Szegedy 框架可写成

$$
T=O\!\left(
T_{\rm setup}
+\frac1{\sqrt{\delta\epsilon}}
(T_{\rm update}+T_{\rm check})
\right).
$$

在最坏只有一个错误条目时，代入

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

得到

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

令两项平衡：

$$
kn=\frac{n^2}{\sqrt k}
\quad\Longrightarrow\quad
k=n^{2/3},
$$

于是

$$
T=O(n^{5/3}).
$$

若错误条目有 $w$ 个且分布较分散，标记比例上升，期望时间还能降为论文给出的

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

型界。最坏结论仍保持 $O(n^{5/3})$。

## 5. 正确性与模型边界

当 $AB=C$ 时没有标记状态，相位翻转恒为恒等，均匀叠加在行走中保持不变，因此算法总回答“相等”。当乘积错误时，某些 $(R,S)$ 被标记；随机 $p,q$ 以常数概率使它们成为可检测状态，量子行走把这部分振幅与初始均匀态分离。Hadamard 干涉检测二者内积，常数次重复把拒绝概率提高到至少 $2/3$。

算法适用于无零因子的交换环（论文以 integral domain 表述）；随机指纹的具体概率也依赖取样集合。它解决的是**验证**而不是输出全部 $AB$。如果读入模型不允许对矩阵元素进行相干随机访问，查询与门时间还要加上数据访问成本。

## 6. 小结与习题

- 标记顶点是包含错误条目的行/列子集对。
- Johnson 图谱隙和标记比例共同决定量子行走步数。
- 双侧随机指纹把子矩阵乘法压成一个长度 $n$ 的内积。
- 取 $k=n^{2/3}$ 平衡初始化与行走成本，得到 $O(n^{5/3})$。

1. 对单个错误位置推导 $\Pr[i\in R,j\in S]=(k/n)^2$。
2. 将 $\delta=1/k$、$\epsilon=k^2/n^2$ 代入 Szegedy 步数公式。
3. 对 $kn+n^2/\sqrt{k}$ 关于 $k$ 做数量级平衡，验证最优指数为 $2/3$。
4. 解释为何“标记检查不增加矩阵查询”仍可能消耗 $\Omega(n^2)$ 门时间，以及双侧指纹如何解决它。

## 参考文献

- Zoo 编号 6：A. Ambainis 等，*Quantum Matrix Verification*，未发表手稿，2002。
- Zoo 编号 19：Harry Buhrman 与 Robert Špalek, [Quantum Verification of Matrix Products](https://arxiv.org/abs/quant-ph/0409035).
- Zoo 编号 85：Mario Szegedy, *Quantum Speed-up of Markov Chain Based Algorithms*, FOCS 2004.