量子矩阵乘积验证：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{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}\]

这里 \(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.

  • Zoo 编号 85：Mario Szegedy, Quantum Speed-up of Markov Chain Based Algorithms, FOCS 2004.