# 交换性测试：黑盒群与矩阵集合上的量子行走 “所有生成元是否两两交换”看似只需枚举成对检查，却是理解量子行走多参数优化的好例子。本课处理两个表面相似、实则完全不同的输入模型： - **黑盒群模型**：给定 $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 量子行走搜索加上可增量更新的数据结构——但标记事件的定义、数据结构和参数平衡各不相同。把它们放在一起学，可以看清楚“行走的步数”与“每步的代价”是如何分别被优化的。 :::{admonition} 本课知识点 :class: tip 1. **[经典基线与查询下界](#classical-baseline)**——能计算成对检查的 $O(k^2)$ 与 Pak 随机算法的 $O(k)$，并用 Freivalds 型验证推出矩阵集合问题的 $\Theta(k^2n^2)$ 经典基线。 2. **[两个输入模型](#two-oracle-models)**——能写出群运算 oracle 与矩阵 entry oracle 的形式定义，并解释“一次矩阵乘法不免费”如何让维数 $n$ 进入查询复杂度。 3. **[中心、中心化子与逃逸引理](#escape-lemma)**——能写出中心与中心化子的定义并验证其为子群，再用“抓到坏生成元”的两步估计推导 $\Pr[g_u\notin H]=\Omega(\ell/k)$。 4. **[随机乘积证据](#product-witness)**——能把逃逸引理对 $Z(G)$ 与 $C(g_u)$ 各用一次，推导 $\Pr[g_ug_v\ne g_vg_u]=\Omega\big((\ell/k)^2\big)$，并说明标记比例的放大与代价。 5. **[乘积树数据结构](#product-tree)**——能构造平衡二叉乘积树，写出 $T_{\rm setup}=O(\ell)$、$T_{\rm update}=O(\log\ell)$、$T_{\rm check}=O(1)$，并解释增量更新的原理。 6. **[谱隙、参数平衡与最优性](#group-walk-balance)**——能把 $\delta=\Omega(1/(\ell\log\ell))$ 与 $\epsilon=\Omega((\ell/k)^2)$ 代入 Szegedy 成本公式，平衡得 $\ell=k^{2/3}$，并用 unique collision 约化说明其近最优性。 7. **[单对验证与两条直接路线](#matrix-two-routes)**——能写出对称指纹的单对交换性测试，推导 $O(kn^{5/3})$ 与 $O(k^{2/3}n^2)$ 两条路线，并确定各占优的参数区间。 8. **[行-列联合行走与三线比较](#matrix-row-column-walk)**——能从四对象见证推导 $\epsilon=\Omega((r/(kn))^4)$ 与 $Q(r)$，平衡得 $O(k^{4/5}n^{9/5})$，并沿三条标度线比较三条矩阵上界。 ::: ## 1. 问题从哪里来：背景与经典基线 ### 1.1 为什么要测试交换性 交换性（commutativity）是代数结构最基本的性质之一。判断一个群是否 Abel、一组矩阵是否两两交换，在群论计算、表示论预处理、算法工程里都会反复出现：例如许多群算法（包括本站[Abelian 隐藏子群问题](abelian-hidden-subgroup.md)中的傅里叶采样框架）只对交换群直接有效，面对一个黑盒给出的群，第一件事往往就是“它交换吗”。 这个问题对量子算法研究另有一层方法论价值：它是一个**性质测试（property testing）**问题——输入是一个庞然大物（由 $k$ 个生成元张成的整个群，或 $k$ 个 $n\times n$ 矩阵），我们只允许做少量查询，就要以高概率判断它是否具有某种全局性质。性质测试天然适合 Grover 型平方加速，但“坏证据”（一对不交换的元素）在搜索空间里的分布很稀疏，如何把证据“放大”又不引入过高的数据结构维护成本，是本课两条算法线的共同主题。 (classical-baseline)= ### 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 型，见[矩阵乘积验证](../ch09-algebra-number-theory/matrix-product-verification.md)），每次验证也要读 $\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)$ 之间的空隙。 (two-oracle-models)= ## 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)$ 不是量子算法的极限**。瓶颈不在“搜索”而在“证据的形状”——单个生成元对作为证据太“脆”了。下面两节构造更结构化的证据：随机生成元乘积。 (escape-lemma)= ### 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 节结算。 (product-witness)= ### 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), $$ 三个量的含义（详细推导见[矩阵乘积验证](../ch09-algebra-number-theory/matrix-product-verification.md)第 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}$），这就是平衡的来源。 (product-tree)= ### 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). $$ (group-walk-balance)= ### 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}$。 (matrix-two-routes)= ## 5. 矩阵集合：单对验证与两条直接路线 现在切换到 entry oracle 模型（第 2 节）。先看一对矩阵的情形：给定 $A,B\in\mathbb C^{n\times n}$，检查 $$ AB\stackrel?=BA. $$ 这正是[矩阵乘积验证](../ch09-algebra-number-theory/matrix-product-verification.md)的**对称版本**。那篇教程的算法在两个 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} 提示：每个群元素是生成元及其逆的字；对字长归纳，利用交换性把相邻字母换位。 **练习 2【两个输入模型】**（→ [第 2 节](#two-oracle-models)） 1. 基础：分别写出黑盒群模型与矩阵集合模型的输入、oracle 的形式定义与任务，并指出各自“一次基本操作”如何计费。 2. 进阶：若把第 4 节的黑盒群算法直接搬到矩阵群上——每次矩阵乘法都用 entry 查询朴素实现、忽略对数因子——总查询复杂度是多少？与第 5 节的哪条路线同阶？ > 提示：朴素计算一次 $n\times n$ 矩阵乘法需要读 $\Theta(n^2)$ 个 entry。 **练习 3【中心、中心化子与逃逸引理】**（→ [3.2 节](#escape-lemma)） 1. 基础：写出 $Z(G)$ 与 $C(h)$ 的定义，并验证二者都是 $G$ 的子群（单位元、乘法封闭、逆封闭）。 2. 基础：在 $S_3$ 中取生成元 $a=(12)$、$b=(123)$、$H=C(a)=\{e,a\}$，枚举 $\ell=2$ 的全部 $4$ 个有序元组，逐一计算乘积并统计 $g_u\notin H$ 的频率，与逃逸引理保证的 $\Omega(\ell/k)$ 比较。 3. 进阶：说明为何从“$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 节](#product-witness)） 1. 基础：写出标记状态的定义（一对元组 $(u,v)$，只要 $g_ug_v\ne g_vg_u$ 就标记），并解释标记比例如何从最坏情形的 $\Theta(1/k^2)$ 放大到 $\Omega((\ell/k)^2)$、付出的代价是什么。 2. 基础：在 $S_3$（$a=(12)$、$b=(123)$）中取 $\ell=1$：列出两个独立均匀随机生成元的全部 $4$ 种组合，计算实际不交换的概率，并与界 $\Omega((\ell/k)^2)$ 比较。 3. 进阶：补全两层逃逸的推导：先取 $H=Z(G)$，条件于 $g_u\notin Z(G)$ 后再取 $H=C(g_u)$，说明两层概率为何可以相乘、$u$ 与 $v$ 的独立性用在何处。 > 提示：$v$ 与 $u$ 独立，故固定 $g_u$ 后逃逸引理对 $v$ 仍然适用。 **练习 5【乘积树数据结构】**（→ [4.2 节](#product-tree)） 1. 基础：画出 $\ell=8$ 的乘积树，替换叶子 $g_{u_3}$ 后标出必须重算的内部节点，并写出 $T_{\rm setup}$、$T_{\rm update}$、$T_{\rm check}$ 的量级。 2. 进阶：设 $\ell=2^m$，证明一般情形的更新成本恰为 $m=\log_2\ell$ 次群乘法；若不用树、每步从头重乘，更新成本与最终的参数平衡会发生什么变化？ > 提示：不用树时 $T_{\rm update}=O(\ell)$，代入后总成本 $\widetilde O(\ell+k\sqrt\ell)$ 随 $\ell$ 递增。 **练习 6【谱隙、参数平衡与最优性】**（→ [4.3 节](#group-walk-balance)） 1. 基础：用赠券收集的直觉解释随机替换链的谱隙 $\delta=\Omega(1/(\ell\log\ell))$，并说出它与 Johnson 图行走谱隙的差别。 2. 基础：复述第 4.4 节的下界路线：unique collision 的 $\Omega(k^{2/3})$ 下界如何约化转移到交换性测试，“忽略对数因子后最优”指什么。 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 节](#matrix-two-routes)） 1. 基础：写出对称版本单对测试的比较式 $p_R^TA_RB^Sq_S\stackrel?=p_R^TB_RA^Sq_S$，并解释当差矩阵 $D=AB-BA\ne0$ 时随机双侧指纹为何以常数概率检出。 2. 进阶：推导两条路线的查询复杂度 $O(kn^{5/3})$ 与 $O(k^{2/3}n^2)$，并确定二者各占优时 $k$ 与 $n$ 应满足的大小关系。 > 提示：Grover 的搜索空间是 $\Theta(k^2)$ 个矩阵对；ED 型行走读一个“符号”（整个矩阵）需 $n^2$ 次查询。 **练习 8【行-列联合行走与三线比较】**（→ [6.2 节](#matrix-row-column-walk)） 1. 基础：写出 Itakura 行走的状态空间（行全集与列全集上各一个大小为 $r$ 的子集）与缓存内容，并列出 $T_{\rm setup}$、$T_{\rm update}$、$T_{\rm check}$ 与 $\delta$ 的量级。 2. 进阶：从“缓存需同时包含两条行与两条列”出发，推导 $\epsilon=\Omega\big((r/(kn))^4\big)$；再由 $Q(r)=rn+n^3k^2/r^{3/2}$ 求出最优 $r=k^{4/5}n^{4/5}$ 并验证第二项同阶。 3. 进阶：对 $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](https://arxiv.org/abs/quant-ph/0506265). - Zoo 编号 54：Yuki Kelly Itakura, [Quantum Algorithm for Commutativity Testing of a Matrix Set](https://arxiv.org/abs/quant-ph/0509206).