交换性测试：黑盒群与矩阵集合上的量子行走¶

“所有生成元是否两两交换”看似只需枚举成对检查，却是理解量子行走多参数优化的好例子。本课处理两个表面相似、实则完全不同的输入模型：

黑盒群模型：给定 $k$ 个生成元和群运算 oracle，判断它们生成的群是否交换。Magniez–Nayak 算法达到近最优的 $\widetilde O(k^{2/3})$ 次群操作；
矩阵集合模型：给定 $k$ 个 $n\times n$ 矩阵的 entry oracle，判断它们是否两两交换。此时一次矩阵乘法不再免费，维数 $n$ 进入复杂度，Itakura 的算法给出 $O(k^{4/5}n^{9/5})$ 次 entry 查询。

两个算法共用同一套骨架——Szegedy 量子行走搜索加上可增量更新的数据结构——但标记事件的定义、数据结构和参数平衡各不相同。把它们放在一起学，可以看清楚“行走的步数”与“每步的代价”是如何分别被优化的。

本课知识点

经典基线与查询下界——能计算成对检查的 $O(k^2)$ 与 Pak 随机算法的 $O(k)$，并用 Freivalds 型验证推出矩阵集合问题的 $\Theta(k^2n^2)$ 经典基线。
两个输入模型——能写出群运算 oracle 与矩阵 entry oracle 的形式定义，并解释“一次矩阵乘法不免费”如何让维数 $n$ 进入查询复杂度。
中心、中心化子与逃逸引理——能写出中心与中心化子的定义并验证其为子群，再用“抓到坏生成元”的两步估计推导 $\Pr[g_u\notin H]=\Omega(\ell/k)$。
随机乘积证据——能把逃逸引理对 $Z(G)$ 与 $C(g_u)$ 各用一次，推导 $\Pr[g_ug_v\ne g_vg_u]=\Omega\big((\ell/k)^2\big)$，并说明标记比例的放大与代价。
乘积树数据结构——能构造平衡二叉乘积树，写出 $T_{\rm setup}=O(\ell)$、$T_{\rm update}=O(\log\ell)$、$T_{\rm check}=O(1)$，并解释增量更新的原理。
谱隙、参数平衡与最优性——能把 $\delta=\Omega(1/(\ell\log\ell))$ 与 $\epsilon=\Omega((\ell/k)^2)$ 代入 Szegedy 成本公式，平衡得 $\ell=k^{2/3}$，并用 unique collision 约化说明其近最优性。
单对验证与两条直接路线——能写出对称指纹的单对交换性测试，推导 $O(kn^{5/3})$ 与 $O(k^{2/3}n^2)$ 两条路线，并确定各占优的参数区间。
行-列联合行走与三线比较——能从四对象见证推导 $\epsilon=\Omega((r/(kn))^4)$ 与 $Q(r)$，平衡得 $O(k^{4/5}n^{9/5})$，并沿三条标度线比较三条矩阵上界。

1. 问题从哪里来：背景与经典基线¶

1.1 为什么要测试交换性¶

交换性（commutativity）是代数结构最基本的性质之一。判断一个群是否 Abel、一组矩阵是否两两交换，在群论计算、表示论预处理、算法工程里都会反复出现：例如许多群算法（包括本站Abelian 隐藏子群问题中的傅里叶采样框架）只对交换群直接有效，面对一个黑盒给出的群，第一件事往往就是“它交换吗”。

这个问题对量子算法研究另有一层方法论价值：它是一个**性质测试（property testing）**问题——输入是一个庞然大物（由 $k$ 个生成元张成的整个群，或 $k$ 个 $n\times n$ 矩阵），我们只允许做少量查询，就要以高概率判断它是否具有某种全局性质。性质测试天然适合 Grover 型平方加速，但“坏证据”（一对不交换的元素）在搜索空间里的分布很稀疏，如何把证据“放大”又不引入过高的数据结构维护成本，是本课两条算法线的共同主题。

1.2 经典算法能做到什么¶

先看黑盒群问题。回忆一个基本事实（练习 1 要求证明）：群 $G=\langle g_1,\ldots,g_k\rangle$ 交换，当且仅当生成元两两交换。

确定性算法：枚举全部 $\binom{k}{2}=\Theta(k^2)$ 对生成元，逐对检查 $g_ig_j\stackrel?=g_jg_i$，每对花费常数次群操作，总计 $O(k^2)$ 次群操作。这就是朴素基线。
随机算法：Pak 给出了一个 $O(k)$ 次的经典随机算法，思想与本课第 3 节的量子算法同源——用随机生成元乘积作为“非交换性证人”，只是没有量子行走的平方加速。
经典下界：可以证明任何经典随机算法都需要 $\Omega(k)$ 次查询（直觉：至少要“看到”相当一部分生成元，否则遗漏的那个恰好是关键见证）。因此 Pak 的线性算法在经典世界已经最优。

经典的结论是 $\Theta(k)$。量子算法要回答的问题是：能不能做到次线性？答案是 $\widetilde O(k^{2/3})$，而且忽略对数因子后不能再改进（第 4.4 节）。

矩阵集合问题的经典基线更贵：直接计算每对乘积需 $\Theta(k^2)$ 次矩阵乘法，即使每次只用随机指纹验证（Freivalds 型，见矩阵乘积验证），每次验证也要读 $\Theta(n^2)$ 个 entry，总计 $\Theta(k^2n^2)$ 次查询。量子算法面对的挑战是同时在 $k$（矩阵个数）和 $n$（维数）两个参数上压缩。

1.3 历史脉络¶

Pak 的经典线性随机算法确立了 $\Theta(k)$ 的经典基线；
Magniez 与 Nayak（参考文献 Zoo 139）于 2005 年给出黑盒群的 $\widetilde O(k^{2/3})$ 量子算法，并证明 $\Omega(k^{2/3})$ 量子查询下界，同时把经典下界钉在 $\Omega(k)$，从而宣告 Pak 算法经典最优；
Itakura（参考文献 Zoo 54）同年处理了矩阵集合模型，给出 $O(k^{4/5}n^{9/5})$ 的 entry 查询上界，并留下与下界 $\Omega(k^{1/2}n)$ 之间的空隙。

2. 两个问题不能混为一谈¶

在深入之前，必须把两个输入模型区分清楚，因为“一次操作算什么”直接决定复杂度表达式的形状。

黑盒群模型。 输入是 $k$ 个生成元 $g_1,\ldots,g_k$（例如以置换、矩阵或抽象标签的形式给出）和群运算 oracle：给定两个元素返回乘积，给定一个元素返回逆元。任务是判断

\[ G=\langle g_1,\ldots,g_k\rangle \]

是否为 Abel 群。这里一次群乘法或求逆计作一次基本操作，复杂度只依赖 $k$——群元素内部长什么样完全不进入账单。由“生成元两两交换当且仅当整个群交换”（练习 1），问题等价于在 $\Theta(k^2)$ 对潜在证据中搜索一对不交换的生成元。

矩阵集合模型。 输入是 $k$ 个 $n\times n$ 矩阵 $M_1,\ldots,M_k$，通过 entry oracle 访问：

\[ O_M:\ |\ell,i,j,0\rangle \mapsto|\ell,i,j,(M_\ell)_{ij}\rangle, \]

其中 $\ell\in[k]$ 指定矩阵、$(i,j)$ 指定行列位置，第四个寄存器在计算基上“写回”矩阵元（标准的可逆查询约定，保证整个映射是置换、从而是酉的）。任务是判断所有 $M_aM_b\stackrel?=M_bM_a$。

关键区别在于：这里一次矩阵乘法不免费。$M_aM_b$ 的一个 entry 是长度为 $n$ 的内积，朴素读取需要 $\Theta(n)$ 次 entry 查询；整个乘积矩阵有 $n^2$ 个 entry。因此维数 $n$ 必然进入查询复杂度，而且算法必须非常小心地控制“缓存了多少 entry、每步行走要重读多少 entry”。第 5、6 节的所有设计都由这一点驱动。

3. 黑盒群：从成对检查到随机乘积证据¶

3.1 朴素量子化：Grover 搜索坏对¶

既然确定性算法枚举 $\Theta(k^2)$ 对生成元，最直接的量子化就是对“生成元对”的集合做 Grover 搜索：搜索空间大小 $N=\Theta(k^2)$，标记项是满足 $g_ig_j\ne g_jg_i$ 的对，若群不交换至少存在一个。由 Grover 搜索的复杂度 $O(\sqrt N)$，查询次数为

\[ O\!\left(\sqrt{k^2}\right)=O(k). \]

每次查询就是取一对生成元、各乘一次再比较，常数次群操作。这已经是 $O(k)$——与经典下界 $\Omega(k)$ 同阶的线性复杂度。看起来量子优势消失了。

但 Magniez–Nayak 的观察是：$O(k)$ 不是量子算法的极限。瓶颈不在“搜索”而在“证据的形状”——单个生成元对作为证据太“脆”了。下面两节构造更结构化的证据：随机生成元乘积。

3.2 中心、中心化子与逃逸引理¶

我们需要两个标准的群论概念。

定义（中心）。群 $G$ 的中心是

\[ Z(G)=\{z\in G:\ zg=gz\ \ \forall g\in G\}, \]

即与所有元素交换的元素组成的集合。容易验证 $Z(G)$ 是 $G$ 的子群：单位元在其中；若 $z_1,z_2\in Z(G)$，则对任意 $g$ 有 $z_1z_2g=z_1gz_2=gz_1z_2$，故 $z_1z_2\in Z(G)$；逆元同理。

$G$ 交换当且仅当 $Z(G)=G$。因此若 $G$ 不交换，$Z(G)$ 是真子群——这正是随机化算法的突破口：真子群在群中所占“比例”有界（由 Lagrange 定理，真子群的阶至多是 $|G|/2$），随机元素有显著概率落在它外面。

定义（中心化子）。对 $h\in G$，其中心化子是

\[ C(h)=\{g\in G:\ gh=hg\}, \]

即所有与 $h$ 交换的元素。同样可验证 $C(h)$ 是子群，且 $h\notin Z(G)$ 等价于 $C(h)\subsetneq G$（存在某个元素不与 $h$ 交换）。

逃逸引理（直观版）。设 $H\subsetneq G$ 是任一真子群。从生成元中均匀随机、独立地取 $\ell$ 个（允许重复）组成有序元组 $u=(u_1,\ldots,u_\ell)$，记乘积

\[ g_u=g_{u_1}g_{u_2}\cdots g_{u_\ell}. \]

则

\[ \Pr[g_u\notin H]=\Omega\!\left(\frac{\ell}{k}\right), \qquad \ell\le k. \]

证明思路（只给出到量级 $\Omega(\ell/k)$ 为止的直觉；严格的常数论证见 Magniez–Nayak 原文，其中随机乘积的每个因子还随机取生成元或其逆）。因为 $H$ 是真子群，至少存在一个生成元 $g_j\notin H$——否则所有生成元都在 $H$ 中，它们生成的整个群 $G$ 都在 $H$ 中，与 $H\subsetneq G$ 矛盾。分两步估计：

第一步，元组中至少有一位取到 $j$ 的概率。每位独立均匀，故

\[ \Pr[\exists t:\ u_t=j]=1-\left(1-\frac1k\right)^\ell. \]

当 $\ell\le k$ 时，用 $1-(1-x)^\ell\ge \ell x-\binom{\ell}{2}x^2$（二项展开保留前两项，取 $x=1/k$）得到

\[ 1-\left(1-\frac1k\right)^\ell \ge \frac{\ell}{k}-\frac{\ell^2}{2k^2} \ge \frac{\ell}{2k}. \]

第二步，抓到 $g_j$ 之后会发生什么。把乘积看成在 $H$ 的左陪集上走动：每乘一个生成元，就从一个陪集跳到另一个陪集；由于 $g_j$ 把陪集 $H$ 映到不同的陪集 $g_jH\ne H$，元组中每出现一次 $g_j$（或其逆），乘积就获得一次被推离 $H$ 的机会。严格的配对/陪集随机游动论证（见原文）表明：条件于元组中至少出现一次 $g_j$，乘积落在 $H$ 外的概率至少是常数（原文给出 $\ge1/2$）。需要警惕一个常见错误：朴素地想用“若 $ps\in H$ 且 $pg_js\in H$ 则 $g_j\in H$”来配对是不严格的——从这两个条件只能推出共轭 $pg_jp^{-1}\in H$，而 $H$ 未必是正规子群，所以必须借助陪集随机游动或允许逆元的随机乘积来完成论证。两步相乘即得

\[ \Pr[g_u\notin H]\ \ge\ \text{常数}\cdot\frac{\ell}{2k}\ =\ \Omega\!\left(\frac{\ell}{k}\right). \]

直观地说：元组越长，越有机会“抓到”那个落在 $H$ 外的生成元；一旦抓到，乘积就有常数概率被它“拖出” $H$。元组长度 $\ell$ 就是随机证据的放大倍数，而它正是后面量子行走要维护的状态大小——放大与成本之间的权衡将在第 4.3 节结算。

3.3 随机乘积证据的碰撞概率¶

现在组装完整的证据。假设 $G$ 不交换。取两个独立的随机 $\ell$ 元组 $u,v$，考虑它们的乘积 $g_u,g_v$：

第一层逃逸：取 $H=Z(G)$。由 $G$ 不交换知 $Z(G)$ 是真子群，逃逸引理给出 $$ \Pr[g_u\notin Z(G)]=\Omega(\ell/k). $$
第二层逃逸：条件于 $g_u\notin Z(G)$，由中心化子的定义，$C(g_u)\subsetneq G$ 也是真子群。$v$ 与 $u$ 独立，对 $H=C(g_u)$ 再用一次逃逸引理： $$ \Pr[g_v\notin C(g_u)\mid g_u\notin Z(G)]=\Omega(\ell/k). $$
合取：两个事件同时发生时，由中心化子定义 $g_ug_v\ne g_vg_u$。两层概率相乘：

\[ \Pr[g_ug_v\ne g_vg_u] =\Omega\!\left(\left(\frac{\ell}{k}\right)^2\right). \]

于是搜索问题被重新表述为：标记状态不是一对原始生成元，而是一对元组 $(u,v)$，只要其乘积不交换就标记。我们付出的代价是状态空间从“$k$ 个生成元”膨胀成“$\ell$ 元组”，换来的是标记比例从最坏 $\Theta(1/k^2)$（只有一对坏生成元）放大到 $\Omega((\ell/k)^2)$。取 $\ell$ 是 $k$ 的多项式量级时，这是多项式级别的放大。

3.4 小例子：$S_3$ 中的逃逸¶

把上面的抽象论证在一个能手算的群里过一遍。取三阶对称群

\[ S_3=\{e,(12),(13),(23),(123),(132)\}, \]

它是最小的非 Abel 群。取生成元 $a=(12)$、$b=(123)$（对换与三循环生成整个 $S_3$），故 $k=2$。

中心。直接验证 $Z(S_3)=\{e\}$：例如 $(12)(13)=(132)\ne(123)=(13)(12)$，所以 $(12)$ 不在中心里；类似可排除其余非单位元。于是 $Z(S_3)$ 是极小的真子群，随机元素以概率 $5/6$ 逃逸——比引理保证的下界好得多（引理只保证 $\Omega(\ell/k)$ 这种与群结构无关的最坏情形界）。

中心化子。计算 $C(a)$：逐一检查六个元素，与 $a=(12)$ 交换的只有 $e$ 和 $a$ 自身（例如 $ab=(12)(123)=(23)$ 而 $ba=(123)(12)=(13)$，两者不等——按右到左复合：$(12)\circ(123)$ 把 $1\mapsto1,2\mapsto3,3\mapsto2$ 即 $(23)$；$(123)\circ(12)$ 把 $1\mapsto3,3\mapsto1,2\mapsto2$ 即 $(13)$）。所以 $C((12))=\{e,(12)\}$，确为真子群。

乘积证据。取 $\ell=1$（元组退化为单个生成元），独立均匀取两个生成元。引理给出不交换概率 $\Omega((1/2)^2)$；实际情形：四对 $(a,a),(a,b),(b,a),(b,b)$ 中 $(a,b),(b,a)$ 两对不交换，概率 $1/2$。最坏情形界与实际值有差距是正常的——引理要对所有群成立，包括那些非交换性隐藏得很深的群。

4. 量子行走：数据结构与参数平衡¶

4.1 Szegedy 搜索框架回顾¶

本课两种算法都用 Szegedy 量子行走搜索，其成本公式为

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

三个量的含义（详细推导见矩阵乘积验证第 4 节）：

$T_{\rm setup}$：制备行走的初始稳态叠加（含建立数据结构）的一次性成本；
$\delta$：行走 Markov 链的谱隙——链收敛越快，$\delta$ 越大，扩散（Grover 型旋转的模拟）越快；
$\epsilon$：稳态下标记顶点的比例——$\sqrt{\epsilon}$ 扮演 Grover 中初始成功振幅的角色，故步数里是 $1/\sqrt{\delta\epsilon}$；
$T_{\rm update},T_{\rm check}$：每走一步更新数据结构、检查当前顶点是否标记的成本。

设计自由度全在“选什么图、维护什么数据”上：放大 $\epsilon$ 往往要维护更大的状态（抬高 $T_{\rm setup}$ 与 $T_{\rm update}$），这就是平衡的来源。

4.2 行走的状态与乘积树¶

状态空间。行走定义在“有序、无重复的 $\ell$ 元组”上（每个位置是互不相同的生成元索引），转移规则是随机替换：均匀随机挑一个位置，用未使用的索引随机替换它。这是 Magniez–Nayak 选用的链（常称随机替换链），它混合良好且相邻状态只差一个位置——后者对增量更新至关重要。算法实际需要两个独立行走，分别维护 $u$ 和 $v$，标记判据是 $g_ug_v\ne g_vg_u$。

数据结构：平衡二叉乘积树。每个状态维护一棵平衡二叉树：叶子依次是 $g_{u_1},\ldots,g_{u_\ell}$，每个内部节点保存其子区间所有叶子的乘积，根节点就是 $g_u$。

为什么需要它？行走一步替换一个叶子，若每次都从头重乘 $\ell$ 项，$T_{\rm update}=O(\ell)$，参数平衡后总成本会退化为 $\widetilde O(k)$，优势尽失。用乘积树则只需重算从被替换叶子到根的路径上的节点：树高 $\lceil\log_2\ell\rceil$，每层一次群乘法，故

\[ T_{\rm update}=O(\log\ell). \]

举例：$\ell=8$，树有三层。替换 $g_{u_3}$ 时，只需更新“$g_{u_3}$ 与 $g_{u_4}$ 的父节点”$\to$“覆盖 $u_1\ldots u_4$ 的节点”$\to$“根”共 $3$ 个节点，其余五个叶子子树的乘积原样保留。

其余成本。建立两棵树的初始成本：每棵树有 $\ell$ 个叶子、约 $\ell$ 个内部节点，每个节点一次乘法，

\[ T_{\rm setup}=O(\ell). \]

检查标记：根节点已存有 $g_u$ 和 $g_v$，计算 $g_ug_v$ 与 $g_vg_u$ 各一次乘法再比较，

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

4.3 谱隙、标记比例与 $\ell=k^{2/3}$ 的由来¶

把各参数代入框架。随机替换链（两个独立行走的乘积链）的谱隙为

\[ \delta=\Omega\!\left(\frac{1}{\ell\log\ell}\right). \]

定性理解：链要等“每个位置都被刷新过”才近似混合，类似赠券收集问题，$\ell$ 个位置每个以 $1/\ell$ 速率被刷新，收集齐需要 $\Theta(\ell\log\ell)$ 步，谱隙即其倒数。这个 $\log\ell$ 正是随机替换链与更标准的 Johnson 图行走（谱隙 $\Theta(1/\ell)$）的差别，也是最终结果中 $\widetilde O$ 对数因子的来源之一。

标记比例由第 3.3 节：$\epsilon=\Omega((\ell/k)^2)$。代入步数：

\[ \frac1{\sqrt{\delta\epsilon}} =\frac{1}{\sqrt{\dfrac{1}{\ell\log\ell}\cdot\dfrac{\ell^2}{k^2}}} =\frac{k\sqrt{\ell\log\ell}}{\ell} =\widetilde O\!\left(\frac{k}{\sqrt{\ell}}\right). \]

注意分子的 $\ell^2$（来自 $\epsilon$）与分母的 $\ell$（来自 $\delta$）相约后净剩 $\sqrt\ell$ 在分母——元组越长，步数越少。总成本

\[ \widetilde O\!\left( T_{\rm setup}+\frac{T_{\rm update}+T_{\rm check}}{\sqrt{\delta\epsilon}} \right) =\widetilde O\!\left( \ell+\frac{k}{\sqrt\ell} \right), \]

其中 $T_{\rm update}=O(\log\ell)$ 被吸收进 $\widetilde O$。

参数平衡。总成本是“建立状态的固定成本 $\ell$”与“行走步数 $k/\sqrt\ell$”之和：$\ell$ 越大前者越贵、后者越便宜。令两项同阶：

\[ \ell=\frac{k}{\sqrt\ell} \ \Longleftrightarrow\ \ell^{3/2}=k \ \Longleftrightarrow\ \ell=k^{2/3}. \]

代回任一项：$\ell=k^{2/3}$，或验证 $k/\sqrt\ell=k/k^{1/3}=k^{2/3}$。总群操作数

\[ \widetilde O(k^{2/3}), \]

对比朴素 Grover 的 $O(k)$，这是多项式级别的改进；改进的全部来源是“随机乘积把标记比例从 $1/k^2$ 放大到 $(\ell/k)^2$”与“乘积树把状态维护压到对数成本”两个设计的叠加。

4.4 下界：为什么 $k^{2/3}$ 基本最优¶

Magniez–Nayak 还证明任何量子算法都需要 $\Omega(k^{2/3})$ 次查询。证明是从 unique collision 问题（在 $k$ 个输入中判断是否存在唯一一对碰撞）做约化：unique collision 已知有 $\Omega(k^{2/3})$ 的量子查询下界（它本质上就是 element distinctness 的下界），而交换性测试足够“表达”该问题，故下界转移。约化的技术细节超出本课范围，记住结论即可：

量子：$\widetilde O(k^{2/3})$ 对上 $\Omega(k^{2/3})$——忽略对数因子后最优；
经典：$\Omega(k)$ 查询下界，Pak 的 $O(k)$ 随机算法经典最优。

这正是 element distinctness 型问题典型的“$2/3$ 指数”签名：碰撞结构的量子搜索下界就是 $N^{2/3}$。

5. 矩阵集合：单对验证与两条直接路线¶

现在切换到 entry oracle 模型（第 2 节）。先看一对矩阵的情形：给定 $A,B\in\mathbb C^{n\times n}$，检查

\[ AB\stackrel?=BA. \]

这正是矩阵乘积验证的对称版本。那篇教程的算法在两个 Johnson 图的乘积上行走，维护随机指纹 $a_R,b_S,c_{R,S}$，把检查压缩为比较

\[ p_R^T A_RB^S q_S \stackrel?= p_R^TC_R^Sq_S, \]

其中 $R,S$ 是大小为 $k_{\rm sub}$ 的行/列子集，$p,q$ 是随机向量。对交换性测试，只需把右端的“$C$ 的指纹”替换为“反向乘积的指纹”：

\[ p_R^TA_RB^Sq_S \stackrel?= p_R^TB_RA^Sq_S. \]

若 $AB=BA$，两边对任意 $p,q$ 恒等；若 $AB\ne BA$，则差矩阵 $D=AB-BA\ne0$，随机双侧指纹以常数概率检出 $p^TDq\ne0$。行走的谱隙、更新成本的分析逐字照搬，最坏查询上界仍为

\[ O(n^{5/3}). \]

有了单对测试器，处理 $k$ 个矩阵有两条直接路线：

路线一：Grover 套验证。坏证据是满足 $M_aM_b\ne M_bM_a$ 的矩阵对，共 $\Theta(k^2)$ 个候选对。对每个对运行 $O(n^{5/3})$ 的验证作为标记判据，做 Grover 搜索：

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

路线二：矩阵索引上的 element-distinctness 型行走。把每个矩阵整体视作一个“符号”，任务是在 $k$ 个符号中找一对“碰撞”（不交换对）。Ambainis 的 element-distinctness 行走用 $O(k^{2/3})$ 次符号操作找到碰撞对；但这里读取一个“符号”意味着读入整个矩阵的 $n^2$ 个 entry，故

\[ O\!\left(k^{2/3}n^2\right). \]

两条路线在不同 $(k,n)$ 区间各占优劣（练习 8 要求具体比较）：$k$ 相对 $n$ 较大时 $k^{2/3}$ 的增速优于 $k$，路线二占优；$n$ 较大时 $n^{5/3}<n^2$，路线一占优。Itakura 的算法（下节）把两者之间的空间也利用起来。

6. 同时在矩阵、行和列上行走¶

6.1 证据的几何形状：四条带标签的向量¶

Itakura 算法的出发点是：坏证据不是一个矩阵对，而是一个 entry 级的见证。

引理。若 $M_aM_b\ne M_bM_a$，则至少存在一个位置 $(i,j)$ 使

\[ \operatorname{row}_i(M_a)\cdot \operatorname{col}_j(M_b) \ \ne\ \operatorname{row}_i(M_b)\cdot \operatorname{col}_j(M_a). \]

推导。左端即 $(M_aM_b)_{ij}=\sum_t (M_a)_{it}(M_b)_{tj}$（矩阵乘法的定义），右端即 $(M_bM_a)_{ij}$。两个矩阵不相等，当且仅当至少一个 entry 不相等。Q.E.D.

所以一个完整见证涉及四个对象：矩阵 $a$ 的第 $i$ 行、矩阵 $b$ 的第 $j$ 列（用于左端内积），以及矩阵 $b$ 的第 $i$ 行、矩阵 $a$ 的第 $j$ 列（用于右端）。算法要在缓存中同时抓住这四条向量，这正是指数 $4$（下面 $\epsilon$ 里的四次方）的几何来源。

6.2 状态空间与各项成本¶

把所有 $kn$ 条“带矩阵标签的行”

\[ \{(a,i):\ a\in[k],\ i\in[n]\} \]

作为一个全集，所有 $kn$ 条带标签列作为另一个全集。行走状态是：在行全集上选大小为 $r$ 的子集，在列全集上选大小为 $r$ 的子集（两个独立的 Johnson 图 $J(kn,r)$ 行走），并缓存每条入选行/列的全部 $n$ 个 entry。

逐项算成本：

Setup：$r$ 条行加 $r$ 条列，每条 $n$ 个 entry， $$ T_{\rm setup}=O(rn). $$
Update：行走一步替换一条行（或列），重新缓存它的 $n$ 个 entry， $$ T_{\rm update}=O(n). $$
Check：第 6.1 节的两个内积完全用已缓存向量计算，不再查询 oracle， $$ T_{\rm check}=O(1)\ \text{次查询} $$ （算术运算有，但 entry 查询为零——这里再次强调本算法优化的是查询复杂度）。
谱隙：Johnson 图 $J(kn,r)$ 的谱隙为 $\Theta(1/r)$，两个独立行走的乘积不改变量级， $$ \delta=\Theta\!\left(\frac1r\right). $$
标记比例：最坏情形只有唯一见证 $(a,b,i,j)$。缓存需同时包含行 $(a,i)$、行 $(b,i)$、列 $(b,j)$、列 $(a,j)$ 四个对象。每个对象被随机 $r$ 子集覆盖的概率约为 $r/(kn)$，四个近似独立，故 $$ \epsilon=\Omega\!\left(\left(\frac{r}{kn}\right)^4\right). $$

6.3 总查询成本与 $r$ 的平衡¶

先算行走步数：

\[ \frac1{\sqrt{\delta\epsilon}} =\frac{1}{\sqrt{\dfrac1r\cdot\left(\dfrac{r}{kn}\right)^4}} =\frac{1}{\sqrt{\dfrac{r^3}{k^4n^4}}} =\frac{k^2n^2}{r^{3/2}}. \]

每步 update 要 $O(n)$ 次查询（check 免费），故行走部分的总查询数为

\[ O\!\left(\frac1{\sqrt{\delta\epsilon}}\cdot n\right) =O\!\left(\frac{n^3k^2}{r^{3/2}}\right). \]

加上 setup 的 $O(rn)$，总查询成本

\[ Q(r)=O\!\left( rn+\frac{n^3k^2}{r^{3/2}} \right). \]

参数平衡。$r$ 越大，缓存越贵（第一项）、标记越密（第二项下降）。令两项同阶：

\[ rn=\frac{n^3k^2}{r^{3/2}} \ \Longleftrightarrow\ r^{5/2}=n^2k^2 \ \Longleftrightarrow\ r=(n^2k^2)^{2/5}=k^{4/5}n^{4/5}. \]

代回第一项：

\[ rn=k^{4/5}n^{4/5}\cdot n=k^{4/5}n^{9/5}, \]

第二项同阶（可自行验证：$n^3k^2/r^{3/2}=n^3k^2/(k^{6/5}n^{6/5})=k^{4/5}n^{9/5}$）。于是

\[ Q=O(k^{4/5}n^{9/5}). \]

6.4 小例子：$2\times2$ 矩阵的见证¶

取 $k=2,n=2$ 的最小非平凡实例：

\[\begin{split} M_1=\begin{pmatrix}0&1\\0&0\end{pmatrix}, \qquad M_2=\begin{pmatrix}0&0\\1&0\end{pmatrix}. \end{split}\]

完整算一遍两个乘积：

\[\begin{split} M_1M_2= \begin{pmatrix}0\cdot0+1\cdot1&0\cdot0+1\cdot0\\0\cdot0+0\cdot1&0\cdot0+0\cdot0\end{pmatrix} =\begin{pmatrix}1&0\\0&0\end{pmatrix}, \end{split}\]

\[\begin{split} M_2M_1= \begin{pmatrix}0\cdot0+0\cdot0&0\cdot1+0\cdot0\\1\cdot0+0\cdot0&1\cdot1+0\cdot0\end{pmatrix} =\begin{pmatrix}0&0\\0&1\end{pmatrix}. \end{split}\]

两者不等，第 6.1 节引理的见证取 $(i,j)=(1,1)$：左端 $\operatorname{row}_1(M_1)\cdot\operatorname{col}_1(M_2)=(0,1)\cdot(0,1)^T=1$，右端 $\operatorname{row}_1(M_2)\cdot\operatorname{col}_1(M_1)=(0,0)\cdot(0,0)^T=0$，确为 $1\ne0$。缓存要抓住的四个对象是行 $(M_1,1)$、行 $(M_2,1)$、列 $(M_2,1)$、列 $(M_1,1)$——全集共 $kn=4$ 条行与 $4$ 条列，这个小例子里 $r$ 取任何小于全集的值时标记比例都显著高于最坏界 $(r/4)^4$，再次说明最坏情形分析是保守的。

6.5 复杂度陈述的保留条款¶

两点必须说清楚，避免误读结果：

这是 entry 查询上界，不是时间/空间上界。算法要求缓存 $rn$ 个矩阵元素（$r=k^{4/5}n^{4/5}$ 时达 $\Theta(k^{4/5}n^{9/5})$ 个），check 阶段的内积用缓存数据相干计算，行走还需要对这些缓存做随机访问。这些步骤的门复杂度与空间成本仍须另计——与矩阵乘积验证中强调的“查询下降不自动等于时间下降”是同一类保留。
上下界之间有空隙。论文给出的量子查询下界是 $\Omega(k^{1/2}n)$，与上界 $O(k^{4/5}n^{9/5})$ 之间存在参数相关的空隙（例如 $k=n$ 时，下界 $n^{3/2}$ 对上界 $n^{13/5}$）。弥合这个空隙仍是开放方向。

7. 三条矩阵上界的统一比较¶

把三条路线放在一起：

\[ O(kn^{5/3}),\qquad O(k^{2/3}n^2),\qquad O(k^{4/5}n^{9/5}). \]

没有任何一条在所有参数区间占优，这正是多参数复杂度问题的常态：$k$ 大时倾向低 $k$ 指数的路线（行走），$n$ 大时倾向低 $n$ 指数的路线（验证），中间区域由 Itakura 的联合行走占优。练习 8 要求沿 $k=n^{1/2},n,n^2$ 三条线具体算出九个指数并排序，做完会对“不能只记单一口号”有直观体会。

8. 小结¶

要点回顾：

群交换性测试的经典复杂度是 $\Theta(k)$（Pak 算法 + 匹配下界）；量子算法用随机生成元乘积把非交换性证据放大到 $\Omega((\ell/k)^2)$，再用乘积树把行走状态维护压到 $O(\log\ell)$，平衡后得 $\widetilde O(k^{2/3})$，并由 unique collision 约化知其近最优。
乘积树是“查询省、时间也省”的关键数据结构：一次状态更新从 $O(\ell)$ 降到 $O(\log\ell)$。
矩阵集合模型中矩阵乘法不免费：单对验证 $O(n^{5/3})$，Grover 套验证 $O(kn^{5/3})$，element-distinctness 型行走 $O(k^{2/3}n^2)$。
Itakura 算法把带标签的行与列作为行走对象，标记事件需要四个对象（两行两列）同时入缓存，故 $\epsilon=(r/(kn))^4$；平衡 setup 与行走后得 $O(k^{4/5}n^{9/5})$ entry 查询。门/空间成本另计，且与下界 $\Omega(k^{1/2}n)$ 之间有空隙。
多参数问题应比较 $kn^{5/3}$、$k^{2/3}n^2$ 与 $k^{4/5}n^{9/5}$ 三条曲线，不能只给单一口号。

练习题¶

练习 1【经典基线与查询下界】（→ 1.2 节）

基础：写出成对检查确定性算法的复杂度，说明 $\binom{k}{2}=\Theta(k^2)$ 对生成元、每对常数次群操作的账单；再说明 Pak 随机算法用什么作为“非交换性证人”、复杂度为何是 $O(k)$。
基础：用 Freivalds 型随机验证计算矩阵集合问题的经典查询基线 $\Theta(k^2n^2)$，并指出两个因子各自的来源。
进阶：证明：$g_ig_j=g_jg_i$ 对所有 $i,j$ 成立，当且仅当整个生成群 $G=\langle g_1,\ldots,g_k\rangle$ 交换。

提示：每个群元素是生成元及其逆的字；对字长归纳，利用交换性把相邻字母换位。

练习 2【两个输入模型】（→ 第 2 节）

基础：分别写出黑盒群模型与矩阵集合模型的输入、oracle 的形式定义与任务，并指出各自“一次基本操作”如何计费。
进阶：若把第 4 节的黑盒群算法直接搬到矩阵群上——每次矩阵乘法都用 entry 查询朴素实现、忽略对数因子——总查询复杂度是多少？与第 5 节的哪条路线同阶？

提示：朴素计算一次 $n\times n$ 矩阵乘法需要读 $\Theta(n^2)$ 个 entry。

练习 3【中心、中心化子与逃逸引理】（→ 3.2 节）

基础：写出 $Z(G)$ 与 $C(h)$ 的定义，并验证二者都是 $G$ 的子群（单位元、乘法封闭、逆封闭）。
基础：在 $S_3$ 中取生成元 $a=(12)$、$b=(123)$、$H=C(a)=\{e,a\}$，枚举 $\ell=2$ 的全部 $4$ 个有序元组，逐一计算乘积并统计 $g_u\notin H$ 的频率，与逃逸引理保证的 $\Omega(\ell/k)$ 比较。
进阶：说明为何从“$ps\in H$ 且 $pg_js\in H$”只能推出 $pg_jp^{-1}\in H$ 而非 $g_j\in H$，并给出 $S_3$ 中一个真子群非正规的例子。

提示：把 $(pg_js)(ps)^{-1}$ 展开；再检验 $H=\{e,(12)\}$ 在 $S_3$ 中是否正规。

练习 4【随机乘积证据】（→ 3.3 节）

基础：写出标记状态的定义（一对元组 $(u,v)$，只要 $g_ug_v\ne g_vg_u$ 就标记），并解释标记比例如何从最坏情形的 $\Theta(1/k^2)$ 放大到 $\Omega((\ell/k)^2)$、付出的代价是什么。
基础：在 $S_3$（$a=(12)$、$b=(123)$）中取 $\ell=1$：列出两个独立均匀随机生成元的全部 $4$ 种组合，计算实际不交换的概率，并与界 $\Omega((\ell/k)^2)$ 比较。
进阶：补全两层逃逸的推导：先取 $H=Z(G)$，条件于 $g_u\notin Z(G)$ 后再取 $H=C(g_u)$，说明两层概率为何可以相乘、$u$ 与 $v$ 的独立性用在何处。

提示：$v$ 与 $u$ 独立，故固定 $g_u$ 后逃逸引理对 $v$ 仍然适用。

练习 5【乘积树数据结构】（→ 4.2 节）

基础：画出 $\ell=8$ 的乘积树，替换叶子 $g_{u_3}$ 后标出必须重算的内部节点，并写出 $T_{\rm setup}$、$T_{\rm update}$、$T_{\rm check}$ 的量级。
进阶：设 $\ell=2^m$，证明一般情形的更新成本恰为 $m=\log_2\ell$ 次群乘法；若不用树、每步从头重乘，更新成本与最终的参数平衡会发生什么变化？

提示：不用树时 $T_{\rm update}=O(\ell)$，代入后总成本 $\widetilde O(\ell+k\sqrt\ell)$ 随 $\ell$ 递增。

练习 6【谱隙、参数平衡与最优性】（→ 4.3 节）

基础：用赠券收集的直觉解释随机替换链的谱隙 $\delta=\Omega(1/(\ell\log\ell))$，并说出它与 Johnson 图行走谱隙的差别。
基础：复述第 4.4 节的下界路线：unique collision 的 $\Omega(k^{2/3})$ 下界如何约化转移到交换性测试，“忽略对数因子后最优”指什么。
进阶：详细推导第 4.3 节：代入 $\delta=\Omega(1/(\ell\log\ell))$、$\epsilon=\Omega((\ell/k)^2)$ 与 $T_{\rm update}=O(\log\ell)$，验证总成本为 $\widetilde O(\ell+k/\sqrt\ell)$，并最小化它得到 $\ell=k^{2/3}$。

提示：令 $\ell=k/\sqrt\ell$，即 $\ell^{3/2}=k$。

练习 7【单对验证与两条直接路线】（→ 第 5 节）

基础：写出对称版本单对测试的比较式 $p_R^TA_RB^Sq_S\stackrel?=p_R^TB_RA^Sq_S$，并解释当差矩阵 $D=AB-BA\ne0$ 时随机双侧指纹为何以常数概率检出。
进阶：推导两条路线的查询复杂度 $O(kn^{5/3})$ 与 $O(k^{2/3}n^2)$，并确定二者各占优时 $k$ 与 $n$ 应满足的大小关系。

提示：Grover 的搜索空间是 $\Theta(k^2)$ 个矩阵对；ED 型行走读一个“符号”（整个矩阵）需 $n^2$ 次查询。

练习 8【行-列联合行走与三线比较】（→ 6.2 节）

基础：写出 Itakura 行走的状态空间（行全集与列全集上各一个大小为 $r$ 的子集）与缓存内容，并列出 $T_{\rm setup}$、$T_{\rm update}$、$T_{\rm check}$ 与 $\delta$ 的量级。
进阶：从“缓存需同时包含两条行与两条列”出发，推导 $\epsilon=\Omega\big((r/(kn))^4\big)$；再由 $Q(r)=rn+n^3k^2/r^{3/2}$ 求出最优 $r=k^{4/5}n^{4/5}$ 并验证第二项同阶。
进阶：对 $k=n^{1/2}$、$k=n$、$k=n^2$ 三种标度，分别计算 $kn^{5/3}$、$k^{2/3}n^2$、$k^{4/5}n^{9/5}$ 关于 $n$ 的指数（共九个数），指出每条标度线上哪条路线最优，并解释随 $k$ 增大占优路线为何从“验证”转向“行走”。

提示：把 $k$ 代成 $n$ 的幂后直接比较指数；平衡 $r$ 时令 $rn$ 与 $n^3k^2/r^{3/2}$ 同阶。

参考文献¶

Zoo 编号 139：Frédéric Magniez 与 Ashwin Nayak, Quantum Complexity of Testing Group Commutativity.
Zoo 编号 54：Yuki Kelly Itakura, Quantum Algorithm for Commutativity Testing of a Matrix Set.