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

“所有生成元是否两两交换”看似只需枚举成对检查，却是理解量子行走多参数优化的好例子。本课分别处理两个不同输入模型：由 $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 图验证算法](../ch09-algebra-number-theory/matrix-product-verification.md)中，把比较

$$
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$ 时三种矩阵上界的指数并比较。

## 参考文献

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