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

“所有生成元是否两两交换”看似只需枚举成对检查，却是理解量子行走多参数优化的好例子。本课分别处理两个不同输入模型：由 \(k\) 个生成元给出的黑盒群，以及由 entry oracle 给出的 \(k\) 个 \(n\times n\) 矩阵。前者达到近最优 \(\widetilde O(k^{2/3})\) 群操作；后者要同时搜索矩阵、行和列，得到 \(O(k^{4/5}n^{9/5})\) 查询上界。

1. 两个问题不能混为一谈

黑盒群问题给定 \(g_1,\ldots,g_k\) 和乘法/逆元 oracle，判断

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

是否 Abelian。生成元两两交换当且仅当整个群交换。

矩阵集合问题给定 entry oracle

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

判断所有 \(M_aM_b=M_bM_a\)。这里一次矩阵乘法不免费，维数 \(n\) 会进入查询复杂度。

2. 群交换性的随机乘积证据

直接检查 \(\binom{k}{2}\) 对生成元需 \(O(k^2)\) 群操作，Grover 搜索坏对降为 \(O(k)\)。Magniez--Nayak 使用更结构化的随机乘积。

从生成元索引中取有序 \(\ell\) 元组

\[ u=(u_1,\ldots,u_\ell),\qquad g_u=g_{u_1}\cdots g_{u_\ell}. \]

若群不交换，中心 \(Z(G)\) 是真子群。适当随机元组的乘积以约 \(\Theta(\ell/k)\) 概率逃离任一指定真子群；先让 \(g_u\notin Z(G)\)，再让独立 \(g_v\) 逃离 centralizer \(C(g_u)\)，可得

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

于是标记状态不是一对原始生成元，而是一对乘积 \((u,v)\)，只要其乘积不交换就标记。

3. 量子行走的数据与平衡

在有序无重复 \(\ell\) 元组的随机替换链上行走。每个状态维护一棵平衡二叉乘积树：叶子是 \(g_{u_i}\)，内部节点保存子区间乘积，根为 \(g_u\)。替换一个叶子只需沿根路径重算

\[ O(\log\ell) \]

次群操作，而不是重新乘 \(\ell\) 项。两个独立行走的谱隙满足

\[ \delta=\Omega(1/(\ell\log\ell)). \]

设置两棵树花 \(O(\ell)\)；检查根乘积是否交换只需常数次群操作。Szegedy 搜索成本因而为

\[ \widetilde O\!\left( \ell+\frac1{\sqrt{\delta\epsilon}} \right) =\widetilde O\!\left( \ell+\frac{k}{\sqrt\ell} \right). \]

平衡两项得到

\[ \ell=k^{2/3}, \qquad \widetilde O(k^{2/3}). \]

从 unique collision 可约化得到 \(\Omega(k^{2/3})\) 量子查询下界，所以忽略对数因子后最优。经典随机查询下界为 \(\Omega(k)\)，Pak 的线性随机算法也因而最优。

4. 单对矩阵为何先要乘积验证

对两矩阵 \(A,B\)，目标是检查

\[ AB=BA. \]

这就是矩阵乘积验证的对称版本：在Johnson 图验证算法中，把比较

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

改成

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

最坏查询上界仍为 \(O(n^{5/3})\)。再对 \(O(k^2)\) 个矩阵对做 Grover，得到直接上界 \(O(kn^{5/3})\)；另一条路线在矩阵索引上做 element-distinctness 型行走，得到 \(O(k^{2/3}n^2)\)。不同 \(k,n\) 区间由不同算法占优。

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

更精细的算法把所有 \(kn\) 条“带矩阵标签的行”作为一个全集，所有 \(kn\) 条带标签列作为另一个全集。分别选择 \(r\) 条行和 \(r\) 条列，缓存每条的 \(n\) 个 entry，故

\[ S=O(rn),\qquad U=O(n). \]

若 \(M_aM_b\ne M_bM_a\)，至少存在 \((i,j)\) 使

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

要在缓存中同时包含这两条行和两条列，最坏标记比例为

\[ \epsilon=Omega\!\left( \left(\frac r{kn}\right)^4 \right). \]

两个 Johnson 行走的谱隙仍为 \(\delta=\Theta(1/r)\)。检查只用已缓存向量做内积，不再查询 oracle。总查询成本

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

令两项平衡：

\[ r^{5/2}=n^2k^2 \quad\Longrightarrow\quad r=k^{4/5}n^{4/5}, \]

从而

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

这是 entry-query 上界；缓存 \(rn\) 个矩阵元素、相干内积和随机访问的门/空间成本仍须另计。论文给出的下界 \(\Omega(k^{1/2}n)\) 与该上界之间尚有参数相关的空隙。

6. 小结与习题

  • 群算法用随机生成元乘积放大非中心元素，再在元组链上量子行走。

  • 乘积树把一次状态更新从 \(O(\ell)\) 降到 \(O(\log\ell)\)。

  • 矩阵集合算法同时抽样带标签的行与列，标记事件需要四个对象共同出现。

  • 多参数问题应比较 \(kn^{5/3}\)、\(k^{2/3}n^2\) 与 \(k^{4/5}n^{9/5}\)，不能只给单一口号。

  1. 证明生成元两两交换推出整个生成群交换。

  2. 最小化 \(\ell+k/\sqrt\ell\) 的数量级。

  3. 推导矩阵算法的 \(\epsilon=(r/(kn))^4\) 与最优 \(r\)。

  4. 分别求 \(k=n^{1/2},n,n^2\) 时三种矩阵上界的指数并比较。

参考文献