# 半环矩阵乘法：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{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}
$$

最后一个是 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. 小例子

取

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

在 $(\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 覆盖

- Zoo 编号 206：François Le Gall 与 Harumichi Nishimura, [Quantum Algorithms for Matrix Products over Semirings](https://arxiv.org/abs/1310.3898).
- Zoo 编号 19、155、157、161：矩阵验证、输出敏感 Boolean 乘法、路径/矩阵等价与 [graph-collision 改进](https://arxiv.org/abs/1112.5855)。