半环矩阵乘法：Grover 基线、阈值 Boolean 化与输出敏感算法

普通矩阵乘法依赖加法消去和环结构；许多图算法却工作在没有加法逆元的半环上，例如 Boolean、\((\min,+)\) 与 \((\max,\min)\)。Strassen 式代数技巧通常不能直接使用，但每个输出 entry 是 \(n\) 个候选的聚合，可先用 Grover 得到 \(\widetilde O(n^{5/2})\) 基线，再利用阈值、稀疏性和输出规模改善。

1. 半环乘法统一公式

半环 \((S,\oplus,\otimes)\) 满足加法交换幺半群、乘法幺半群和分配律，但不要求 \(a\) 有 \(\oplus\) 逆元。矩阵积定义为

\[ C_{ij}=\bigoplus_{k=1}^n A_{ik}\otimes B_{kj}. \]

三个重要例子：

\[\begin{split} \begin{array}{c|c|c|c} \text{半环}&\oplus&\otimes&C_{ij}\\\hline \text{Boolean}&\lor&\land&\bigvee_k(A_{ik}\land B_{kj})\\ (\max,\min)&\max&\min&\max_k\min(A_{ik},B_{kj})\\ (\min,+)&\min&+&\min_k(A_{ik}+B_{kj}) \end{array} \end{split}\]

最后一个是 distance product；反复平方可求 all-pairs shortest paths。\((\max,\min)\) 则给 bottleneck path 的最大最小边权。

2. 逐 entry Grover 的 \(n^{5/2}\) 基线

若 \(\oplus\) 是 OR、min 或 max，可用 Dürr--Høyer 最小/最大搜索在

\[ O(\sqrt n) \]

次候选计算内求一个 \(C_{ij}\)。共有 \(n^2\) 个输出 entry，所以

\[ T=\widetilde O(n^{5/2}). \]

这个算法几乎不利用 entry 间共享的 \(A_{ik},B_{kj}\)；它是比较基准，不保证胜过所有经典半环专用算法。量子速度提升要让许多输出共享阈值测试或碰撞数据。

3. \((\max,\min)\) 如何化为阈值 Boolean 乘积

对阈值 \(\lambda\) 定义 Boolean 矩阵

\[ A^{(\lambda)}_{ik}=1[A_{ik}\ge\lambda],\qquad B^{(\lambda)}_{kj}=1[B_{kj}\ge\lambda]. \]

则

\[ C_{ij}\ge\lambda \quad\Longleftrightarrow\quad (A^{(\lambda)}\cdot B^{(\lambda)})_{ij}=1 \]

（右侧在 Boolean 半环计算）。所以 \(C_{ij}\) 是使阈值产品为 1 的最大 \(\lambda\)。

若对每个 entry 单独二分阈值，仍重复工作。Le Gall--Nishimura 方法把排序后的权值分块：

  1. 用快速矩形 Boolean 乘法同时处理“整块是否有 witness”；

  2. 只对边界块中的少量未决 \((i,j,k)\) 做量子搜索；

  3. 调节块大小，使批量乘法与 residual search 成本平衡。

代入当时可用的矩形乘法指数，得到 Zoo 快照记录的

\[ \widetilde O(n^{2.473}) \]

时间，并同样求 all-pairs bottleneck paths。指数来自具体经典矩形乘法上界，未来若该上界改变，数值也应随之更新；算法结构仍是“阈值批处理 + 量子边界搜索”。

4. Distance product 的高位分解

对

\[ C_{ij}=\min_k(A_{ik}+B_{kj}), \]

单个阈值条件 \(A_{ik}+B_{kj}\le\lambda\) 不是两个独立 Boolean 条件。方法把数值按高位/区间分桶，用 dominance product 批量判断哪些 \(k\) 可能使和落入某区间，再对区间内部的低位候选量子搜索。

若只要求每个 entry 的 \(L\) 个最高有效位，Zoo 所据工作给出

\[ \widetilde O(2^{0.64L}n^{2.46}) \]

型量子时间，相比逐一枚举 \(2^L\) 桶降低位精度依赖。它不是“精确任意大整数 distance product”的统一 \(n^{2.46}\) 算法；\(L\) 和权值编码长度必须保留。

5. Boolean 输出敏感乘法

Boolean 情形中令

\[ \ell=|\{(i,j):C_{ij}=1\}|. \]

\(C_{ij}=1\) 等价于行支持与列支持有交：

\[ \operatorname{supp}(A_{i,*}) \cap\operatorname{supp}(B_{*,j})\ne\varnothing. \]

这可视为 graph collision。算法维护已发现的 1-entry，并用量子 walk/search 找到一个尚未报告的碰撞；对剩余标记数使用变长搜索并求和，得到

\[ \widetilde O(n\sqrt\ell) \]

查询上界。输出稀疏时显著小于 \(n^{5/2}\)。当 \(\ell\) 大时，写出 \(n^2\) 位输出本身成为时间下界，所以查询复杂度与总时间要分开。

一般 dense Boolean 乘法并没有仅凭该查询界就击败最快经典 dense 算法；重复 witness、数据结构更新和显式输出会主导。输入矩阵稀疏时，按非零 entry 构造邻接表并结合量子搜索，可在部分参数区域获得时间优势。

6. 小例子

取

\[\begin{split} A=\begin{pmatrix}5&1\\3&4\end{pmatrix},\qquad B=\begin{pmatrix}2&6\\7&0\end{pmatrix}. \end{split}\]

在 \((\max,\min)\) 半环：

\[ C_{11}=\max\{\min(5,2),\min(1,7)\}=\max\{2,1\}=2, \]
\[ C_{12}=\max\{\min(5,6),\min(1,0)\}=5. \]

阈值 \(\lambda=4\) 时，第一行到第二列存在 witness \(k=1\)，故 \(C_{12}\ge4\)；阈值 6 时失败，逐块缩窄即可定位值 5。

7. 小结与习题

  • 半环无加法逆元，普通快速矩阵乘法技巧不一定适用。

  • 对每个输出做量子 min/max 得到通用 \(\widetilde O(n^{5/2})\) 基线。

  • \((\max,\min)\) 用阈值 Boolean 乘法批处理，distance product 用数值分桶和 dominance。

  • Boolean 稀疏输出可用 graph collision 达到 \(\widetilde O(n\sqrt\ell)\) 查询。

  1. 证明 \((\max,\min)\) 的阈值等价式。

  2. 对给定 \(2\times2\) 例子算完整 \((\max,\min)\) 乘积。

  3. 解释为什么 dense 输出时 \(n\sqrt\ell\) 查询不等于亚二次总时间。

  4. 比较 entry oracle、非零邻接表 oracle 与显式数组输入。

参考文献与 Zoo 覆盖