交换性测试

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

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

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

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

1.1 为什么要测试交换性

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

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

1.2 经典算法能做到什么

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

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

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

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

1.3 历史脉络

• Pak 的经典线性随机算法确立了 $\Theta (k)$ 的经典基线；
• Magniez 与 Nayak（参考文献 Zoo 139）于 2005 年给出黑盒群的 $\tilde{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,\dots ,g_k$（例如以置换、矩阵或抽象标签的形式给出）和群运算 oracle：给定两个元素返回乘积，给定一个元素返回逆元。任务是判断

$$G=⟨g_1,\dots ,g_k⟩$$

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

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

$$O_M:|\ell ,i,j,0⟩\mapsto |\ell ,i,j,(M_{\ell }{)}_{ij}⟩,$$

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

关键区别在于：这里一次矩阵乘法不免费。$M_a{M}_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_i{g}_j\ne g_j{g}_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_1{z}_{2}g=z_{1}g{z}_2=g{z}_1{z}_2$，故 $z_1{z}_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)⊊G$（存在某个元素不与 $h$ 交换）。

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

$$g_u=g_{u_1}{g}_{u_2}\cdots g_{u_{\ell }}.$$

则

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

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

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

$$\mathrm{Pr}[\exists t:u_t=j]=1-{\left(1-\frac{1}{k}\right)}^{\ell }.$$

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

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

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

$$\mathrm{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)$ 是真子群，逃逸引理给出 $$\mathrm{Pr}[g_u\notin Z(G)]=\Omega (\ell /k).$$
• 第二层逃逸：条件于 $g_u\notin Z(G)$，由中心化子的定义，$C(g_u)⊊G$ 也是真子群。$v$ 与 $u$ 独立，对 $H=C(g_u)$ 再用一次逃逸引理： $$\mathrm{Pr}[g_v\notin C(g_u)\mid g_u\notin Z(G)]=\Omega (\ell /k).$$
• 合取：两个事件同时发生时，由中心化子定义 $g_u{g}_v\ne g_v{g}_u$。两层概率相乘：

$$\mathrm{Pr}[g_u{g}_v\ne g_v{g}_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\mapsto 1,2\mapsto 3,3\mapsto 2$ 即 $(23)$；$(123)\circ (12)$ 把 $1\mapsto 3,3\mapsto 1,2\mapsto 2$ 即 $(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_{\mathrm{setup}}+\frac{1}{\sqrt{\delta ϵ}}\left(T_{\mathrm{update}}+T_{\mathrm{check}}\right)\right),$$

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

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

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

4.2 行走的状态与乘积树

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

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

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

$$T_{\mathrm{update}}=O(\log \ell ).$$

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

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

$$T_{\mathrm{setup}}=O(\ell ).$$

检查标记：根节点已存有 $g_u$ 和 $g_v$，计算 $g_u{g}_v$ 与 $g_v{g}_u$ 各一次乘法再比较，

$$T_{\mathrm{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 )$）的差别，也是最终结果中 $\tilde{O}$ 对数因子的来源之一。

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

$$\frac{1}{\sqrt{\delta ϵ}}=\frac{1}{\sqrt{\frac{1}{\ell \log \ell }\cdot \frac{{\ell }^2}{k^2}}}=\frac{k\sqrt{\ell \log \ell }}{\ell }=\tilde{O}\left(\frac{k}{\sqrt{\ell }}\right).$$

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

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

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

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

$$\ell =\frac{k}{\sqrt{\ell }}⟺{\ell }^{3/2}=k⟺\ell =k^{2/3}.$$

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

$$\tilde{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 的下界），而交换性测试足够“表达”该问题，故下界转移。约化的技术细节超出本词条范围，记住结论即可：

• 量子：$\tilde{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}_R{B}^S{q}_S\stackrel{?}{=}{p}_R^T{C}_R^S{q}_S,$$

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

$$p_R^T{A}_R{B}^S{q}_S\stackrel{?}{=}{p}_R^T{B}_R{A}^S{q}_S.$$

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

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

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

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

$$O\left(\sqrt{k^2}\cdot n^{5/3}\right)=O\left(k{n}^{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)$ 区间各占优劣（习题 6 要求具体比较）：$k$ 相对 $n$ 较大时 $k^{2/3}$ 的增速优于 $k$，路线二占优；$n$ 较大时 $n^{5/3}<n^2$，路线一占优。Itakura 的算法（下节）把两者之间的空间也利用起来。

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

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

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

引理。若 $M_a{M}_b\ne M_b{M}_a$，则至少存在一个位置 $(i,j)$ 使

$${\mathrm{row}}_i(M_a)\cdot {\mathrm{col}}_j(M_b)\ne {\mathrm{row}}_i(M_b)\cdot {\mathrm{col}}_j(M_a).$$

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

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

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

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

先算行走步数：

$$\frac{1}{\sqrt{\delta ϵ}}=\frac{1}{\sqrt{\frac{1}{r}\cdot {\left(\frac{r}{kn}\right)}^4}}=\frac{1}{\sqrt{\frac{r^3}{k^4{n}^4}}}=\frac{k^2{n}^2}{r^{3/2}}.$$

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

$$O\left(\frac{1}{\sqrt{\delta ϵ}}\cdot n\right)=O\left(\frac{n^3{k}^2}{r^{3/2}}\right).$$

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

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

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

$$rn=\frac{n^3{k}^2}{r^{3/2}}⟺r^{5/2}=n^2{k}^2⟺r=(n^2{k}^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^3{k}^2/r^{3/2}=n^3{k}^2/(k^{6/5}{n}^{6/5})=k^{4/5}{n}^{9/5}$）。于是

$$Q=O(k^{4/5}{n}^{9/5}).$$

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

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

$$M_1=\left(\begin{array}{cc}0& 1\\ 0& 0\end{array}\right),M_2=\left(\begin{array}{cc}0& 0\\ 1& 0\end{array}\right).$$

完整算一遍两个乘积：

$$M_1{M}_2=\left(\begin{array}{cc}0\cdot 0+1\cdot 1& 0\cdot 0+1\cdot 0\\ 0\cdot 0+0\cdot 1& 0\cdot 0+0\cdot 0\end{array}\right)=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),$$ $$M_2{M}_1=\left(\begin{array}{cc}0\cdot 0+0\cdot 0& 0\cdot 1+0\cdot 0\\ 1\cdot 0+0\cdot 0& 1\cdot 1+0\cdot 0\end{array}\right)=\left(\begin{array}{cc}0& 0\\ 0& 1\end{array}\right).$$

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

6.5 复杂度陈述的保留条款

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

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

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

把三条路线放在一起：

$$O(k{n}^{5/3}),O(k^{2/3}{n}^2),O(k^{4/5}{n}^{9/5}).$$

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

8. 小结与习题

要点回顾：

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

习题：

1. 生成元对充分性。证明：$g_i{g}_j=g_j{g}_i$ 对所有 $i,j$ 成立，当且仅当整个生成群 $G=⟨g_1,\dots ,g_k⟩$ 交换。（提示：每个群元素是生成元及其逆的字；对字长归纳，利用交换性把相邻字母换位。）
2. 群算法的平衡。详细推导第 4.3 节：代入 $\delta =\Omega (1/(\ell \log \ell ))$、$ϵ=\Omega ((\ell /k{)}^2)$ 与 $T_{\mathrm{update}}=O(\log \ell )$，验证总成本为 $\tilde{O}(\ell +k/\sqrt{\ell })$，并最小化它得到 $\ell =k^{2/3}$。
3. 乘积树的更新成本。设 $\ell =2^m$。画出 $\ell =8$ 的乘积树，说明替换一个叶子后哪些内部节点必须重算，并证明一般情形的更新成本恰为 $m={\log }_2\ell$ 次群乘法。若不用树、直接维护根乘积，更新成本是多少？这一差异如何影响第 4.3 节最终的指数？
4. 子群验证与逃逸实例。（a）验证 $Z(G)$ 与 $C(h)$ 确为 $G$ 的子群（检查单位元、乘法封闭、逆封闭）。（b）在 $S_3$ 中取生成元 $a=(12),b=(123)$、$H=C(a)=\{e,a\}$，枚举 $\ell =2$ 的全部 $4$ 个有序元组，逐一计算乘积并统计 $g_u\notin H$ 的频率，与逃逸引理保证的 $\Omega (\ell /k)$ 比较。（c）说明为何从“$ps\in H$ 且 $p{g}_{j}s\in H$”只能推出 $p{g}_j{p}^{-1}\in H$ 而非 $g_j\in H$，并给出 $S_3$ 中一个真子群非正规的例子。
5. 矩阵算法的推导。从“缓存需同时包含两条行与两条列”出发，推导 $ϵ=\Omega ((r/(kn){)}^4)$；再由 $Q(r)=rn+n^3{k}^2/r^{3/2}$ 求出最优 $r=k^{4/5}{n}^{4/5}$ 并验证第二项同阶。
6. 三线比较。对 $k=n^{1/2}$、$k=n$、$k=n^2$ 三种标度，分别计算 $k{n}^{5/3}$、$k^{2/3}{n}^2$、$k^{4/5}{n}^{9/5}$ 关于 $n$ 的指数（共九个数），指出每条标度线上哪条路线最优，并解释随 $k$ 增大占优路线为何从“验证”转向“行走”。

参考文献

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

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch10-hidden-structures/commutativity-testing
• 内容遵循 CC BY-NC-SA 4.0 许可协议