半环矩阵乘法

矩阵乘法是组合算法中最常用的”聚合机器”。在环（如实数、整数、有限域）上，我们有 Strassen 型快速乘法，把 $n\times n$ 乘法的代价从 $n^3$ 压到 $O(n^{\omega })$（$\omega <2.373$）。但图算法真正需要的那些代数结构——Boolean 半环上的可达性、$(\min ,+)$ 半环上的最短路、$(\max ,\min )$ 半环上的瓶颈路径——都没有加法逆元，统称半环。减法与消去一旦不可用，Strassen 式的代数重组通常随之失效（第 1.3 节会把这句话拆开讲清楚），经典世界因此长期停留在接近 $n^3$ 的算法上。

量子侧的情形更有意思。半环矩阵积的每个输出 entry 是 $n$ 个候选的聚合：$C_{ij}={⨁}_k(A_{ik}\otimes B_{kj})$。而”在 $n$ 个候选中做 OR、取 min、取 max”恰好都是量子搜索能平方根加速的操作，于是立即得到一个通用的 $\tilde{O}(n^{5/2})$ 基线。本词条的主线就是追问：这个 $5/2$ 是不是终点？ 答案是否定的，而且不同半环给出三条不同的路：

1. $(\max ,\min )$ 乘积：阈值 Boolean 化 + 分块 + 矩形矩阵乘法，时间 $\tilde{O}(n^{2.473})$（第 4 节）；
2. 距离乘积（$(\min ,+)$）：高位分解 + 支配乘积，时间 $\tilde{O}(2^{0.64L}{n}^{2.46})$，其中 $L$ 是所需的有效位数（第 5 节）；
3. Boolean 乘积：输出敏感 + 图碰撞，查询 $\tilde{O}(n\sqrt{\ell })$，其中 $\ell$ 是输出中 1 的个数（第 6 节）。

三条路共享同一个方法论：让许多输出 entry 共享同一批”阈值测试”或”碰撞搜索”，再用参数平衡决定”批量处理”与”零星量子搜索”的比重。这与collision 与元素唯一性词条中”建表成本 vs 搜索成本”的平衡是同一门手艺，只是这里的两个竞争项换成了”经典矩形乘法”与”量子枚举”。

前置知识。 我们默认读者已学完的 Grover 算法与振幅放大（特别是”$N$ 个条目、$t$ 个目标时搜索成本 $\tilde{O}(\sqrt{N/t})$“这一结论），并了解查询模型的记账约定：一次 oracle 调用计一次查询，其余门操作另行计时间。第 6 节会用到图碰撞（graph collision）问题，我们会在使用处给出定义，不必预先阅读该教程；同章的collision 教程对量子行走的讲解有助于理解背景，但同样不是必需的。

1. 问题、模型与经典基线

1.1 半环与统一的乘法公式

定义（半环）。 一个半环 $(S,\oplus ,\otimes )$ 由集合 $S$ 与两个二元运算组成，满足：

• $(S,\oplus )$ 是交换幺半群：$\oplus$ 满足结合律与交换律，有零元 $0$（$a\oplus 0=a$）；
• $(S,\otimes )$ 是幺半群：$\otimes$ 满足结合律，有单位元 $1$；
• $\otimes$ 对 $\oplus$ 满足分配律：$a\otimes (b\oplus c)=(a\otimes b)\oplus (a\otimes c)$，$0$ 是吸收元（$a\otimes 0=0$）。

与环唯一的差别是：不要求 $a$ 有 $\oplus$ 逆元。也就是没有减法。

$n\times n$ 矩阵在半环上的乘积逐 entry 定义为

$$C_{ij}=\underset{k=1}{\overset{n}{⨁}}{A}_{ik}\otimes B_{kj},$$

本词条的三个主角是：

$$\begin{array}{cccc}\text{半环}& \oplus & \otimes & C_{ij}\\ \text{Boolean}& \vee & \wedge & {\bigvee }_k(A_{ik}\wedge B_{kj})\\ (\max ,\min )& \max & \min & {\max }_k\min (A_{ik},B_{kj})\\ (\min ,+)& \min & +& {\min }_k(A_{ik}+B_{kj})\end{array}$$

这三个乘积都不是抽象练习：

• Boolean 乘积是计算传递闭包 (transitive closure) 的核心：邻接矩阵的 $r$ 次幂刻画”两步、四步、……可达”。
• $(\min ,+)$ 乘积称为距离乘积 (distance product)。把边权矩阵反复做 $(\min ,+)$ 自乘（“反复平方”），$\lceil {\log }_{2}n\rceil$ 轮后即得所有点对的最短路：长度至多 $2^r$ 的路径的最优值，恰是矩阵平方 $r$ 次后的 entry。
• $(\max ,\min )$ 乘积给出全点瓶颈路径 (all-pairs bottleneck paths)：一条路径的”宽度”是它所经边的最小权，两段路径拼接后宽度是 $\min$，取所有中转方式的最优是 $\max$——正是一个 $(\max ,\min )$ 乘积。它也以”关系的合成 (composition of relations)“之名出现在模糊逻辑中。

若某个 $k$ 使 $A_{ik}\otimes B_{kj}$ “贡献”了 $C_{ij}$（Boolean 情形即 $A_{ik}=B_{kj}=1$），称 $k$ 为 $C_{ij}$ 的一个 witness。输出 witness 与只输出数值是两类任务，后文会看到它们难度不同。

1.2 计算模型与记账

输入矩阵以 entry oracle 给出，两种等价形式都常见：

$$O_A:|i,j,z⟩\mapsto |i,j,z\oplus A_{ij}⟩\text{或}{O}_A:|i,j,0⟩\mapsto |i,j,A_{ij}⟩,$$

一次对 $O_A$ 或 $O_B$ 的调用计为一次查询。除此之外要区分两种记账：

• 查询复杂度：只数 oracle 调用，与输入无关的门操作免费。第 6 节的输出敏感算法采用这种记账。
• 时间复杂度：数所有计算步骤，其中把每次 oracle 调用计为 $1$。第 3–5 节的算法采用这种记账。Le Gall–Nishimura 明确说明：这对应于”输入可以被量子叠加地随机访问”的情形（即相干随机访问 / QRAM 类假设）。这是一个模型依赖的保留条款——在没有这种访问方式的电路模型里，读入输入本身就可能主导成本。

还有一笔账必须预先声明：输出是 $n^2$ 个 entry 的矩阵，任何算法把它写出来都要 $\Omega (n^2)$ 时间。因此所有亚立方的界都应读作”计算并输出矩阵”的界，而第 6 节会专门讨论输出规模 $\ell$ 如何反过来成为下界。

1.3 经典算法能做到哪里：一个例外与两个瓶颈

Boolean 是例外。 虽然 Boolean 半环同样没有减法，但它可以”免费”嵌入整数环：把 $A,B$ 当作整数矩阵做普通乘法，则

$$(AB{)}_{ij}=\sum _{k=1}^n{A}_{ik}{B}_{kj}\ge 1⟺\exists k:A_{ik}{B}_{kj}=1⟺C_{ij}=1,$$

中间的等价用了”每个乘积项是 $0$ 或 $1$，且非负，因此和不小于 $1$ 当且仅当某项为 $1$“。中间量至多是 $n$，用 $O(\log n)$ 位即可精确表示，故 Boolean 乘积可在 $\tilde{O}(n^{\omega })$ 时间内经典完成。这是半环中已知能用环乘法技巧的少数特例。

Strassen 式技巧为什么对其他半环失效？ Strassen 算法的本质是把 $2\times 2$ 块乘法写成 $7$ 个”和差积”的组合，例如中间量 $(a_{11}+a_{22})(b_{11}+b_{22})$，最后再用减法重组出各个块。这里有两处硬依赖：中间量需要做差（$a_{11}-a_{12}$ 这类表达式在半环里无定义），重组时需要消去（同类项相减留下想要的部分）。在 $(\min ,+)$ 与 $(\max ,\min )$ 中，"$-a$"不存在，双线性恒等式的整个重组流程无从执行。需要强调：这不是证明了下界——只是已知的代数技巧全部失效，问题的难度被转移到了组合算法上。

两个瓶颈（本词条写作所据论文时代的纪录）：

• $(\max ,\min )$ 乘积：最好的经典算法属于 Duan–Pettie，时间 $\tilde{O}(n^{(3+\omega )/2})=O(n^{2.687})$；
• 距离乘积：在不对输入做任何假设的前提下，没有任何真正亚立方（$n^{3-o(1)}$ 以下）的经典算法为人所知。它与最短路等一批问题的著名子立方等价性说明这不是孤立的漏洞，而是一整片困难的代数结构。

顺带一提与第 6 节相关的第三个经典事实：Boolean 乘法在稀疏输入上有 Yuster–Zwick 的组合算法，我们在第 6.6 节与量子算法对照。

1.4 历史脉络

把本词条用到的线索按时间排好：

• 2006，Buhrman–Špalek（Zoo 19）：首次研究矩阵积的量子复杂度，给出”验证 $AB=C$“的 $O(n^{3/2})$ 查询上界。验证的量子下界至今仍是公开问题（写作时最好的下界约为 $\Omega (n^{1.055})$）。
• 2010，Vassilevska Williams–Williams（Zoo 157）：证明路径、矩阵、三角形等一系列问题之间的子立方等价性，划定了”哪些问题一起难”的版图。
• 2012，Le Gall（Zoo 155）：输出敏感的 Boolean 乘法量子算法，以输出中 1 的个数 $\ell$ 为参数。
• 2012，Jeffery–Kothari–Magniez（Zoo 161）：把 Boolean 乘法化为图碰撞实例，得到对所有 $\ell$ 都成立的 $\tilde{O}(n\sqrt{\ell })$ 查询界与匹配下界——第 6 节的主角。
• 2013，Le Gall–Nishimura（Zoo 206）：本词条主线。给出 $(\max ,\min )$ 的 $\tilde{O}(n^{2.473})$、距离乘积高 $L$ 位的 $\tilde{O}(2^{0.64L}{n}^{2.46})$，是首批在 Boolean 之外的半环上突破 $\tilde{O}(n^{5/2})$ 直觉基线的量子算法，也是首批在不假设稀疏性的前提下全面快于当时最好经典算法的半环乘法量子算法；其技术同时把经典距离乘积的 $2^L$ 因子改进到 $2^{0.96L}$。

2. 三个量子搜索原语

后文所有复杂度都由三个原语拼成，先把它们和成本写清楚。设搜索空间 $U$，$|U|=N$，标记函数 $f:U\to \{0,1\}$，标记元素个数 $t_f=|f^{-1}(1)|$。

原语一：搜索（已知标记数的下界）。 若已知 $t_f\ge t$，则振幅放大给出 $\tilde{O}(\sqrt{N/t})$ 次查询找到一个标记元素（$\tilde{O}$ 吸收把错误概率压到 $1/\mathrm{poly}(N)$ 所需重复的对数因子）；若 $t_f=0$ 则可确定地宣告无解。

原语二：枚举全部（变长搜索求和）。

Lemma 1（quantum enumeration / SearchAll）. 存在量子算法找出 $U$ 中全部 $t_f$ 个标记元素，查询数

$$\tilde{O}\left(\sqrt{N/t_f}+\sqrt{N/(t_f-1)}+\cdots +\sqrt{N/1}\right)=\tilde{O}\left(\sqrt{N(t_f+1)}\right).$$

证明。策略：维护剩余集合 $V$ 与计数 $t$（初始 $t=N$ 的保守估计）。反复用原语一在 $V$ 上搜索；找到一个标记元素就输出并从 $V$ 删除、$t$ 减一；失败则把 $t$ 减半再试。当剩余标记数恰为 $s$ 时，一次成功搜索成本 $\tilde{O}(\sqrt{N/s})$，故总成本为左边部分和。对右边：对每个 $s\ge 1$ 有

$$\frac{1}{\sqrt{s}}\le 2(\sqrt{s}-\sqrt{s-1}),$$

因为 $\sqrt{s}-\sqrt{s-1}=\frac{1}{\sqrt{s}+\sqrt{s-1}}\ge \frac{1}{2\sqrt{s}}$。对 $s=1,\dots ,t_f$ 求和，右边望远镜相消得 ${\sum }_{s=1}^{t_f}\frac{1}{\sqrt{s}}\le 2\sqrt{t_f}$，于是部分和 $\le \sqrt{N}\cdot 2\sqrt{t_f}=O(\sqrt{N{t}_f})$。$t_f=0$ 时算法在 $t$ 降到 $1$ 后确定地宣告无解。Q.E.D.

这个”变长搜索再求和”的账本在后文出现两次（第 4.3 节的块内枚举、第 6 节的输出敏感枚举），它是”输出敏感”三个字的量化形式：成本随实际解数 $t_f$ 而非空间大小 $N$ 的平方根增长。

原语三：最小/最大搜索（Dürr–Høyer）。 给定 $g:U\to \mathbb{R}$，可用 $\tilde{O}(\sqrt{N})$ 次查询找到 $\arg \min g$（或 $\arg \max$）。机制：维护当前阈值 $M=g(x_0)$（$x_0$ 任取），反复用变长 Grover 在 $\{x:g(x)<M\}$ 中找一个元素，找到就更新 $M$ 重来，搜不到就说明 $M$ 已是全局最小。阈值每更新一轮，候选集严格缩小，总查询数为 $\tilde{O}(\sqrt{N})$（Dürr–Høyer 1996，见文末参考文献）。一个有用的变体：$g$ 若是已知的经典信息（比如图论量），只有”哪些元素被标记”是未知的，则同样的过程找到”被标记元素中 $g$ 最大者”，成本仍是 $\tilde{O}(\sqrt{N})$——第 6.3 节会用到。

工具：矩形乘法指数。 对正数 $k_1,k_2,k_3$，记 $\omega (k_1,k_2,k_3)$ 为”把 $n^{k_1}\times n^{k_2}$ 矩阵乘 $n^{k_2}\times n^{k_3}$ 矩阵”所需算术操作的指数上界；$\omega =\omega (1,1,1)$ 是方阵乘法指数（本词条引用的数值均取论文写作时的 $\omega <2.373$，此后略有改进，但不影响叙事）。两个派生量：$\alpha =\sup \{k:\omega (1,k,1)=2\}$（已知 $\alpha >0.302$）与 $\beta =\frac{\omega -2}{1-\alpha }$。我们只用到四条标准性质：

• 齐次性与对称性：$\omega (k{k}_1,k{k}_2,k{k}_3)=k\omega (k_1,k_2,k_3)$，且对三个参数的任意置换不变；
• 单调性：$\omega (k_1,k_2,k_3+k_4)\le \omega (k_1,k_2,k_3)+k_4$；
• 朴素下界：$\omega (k_1,k_2,k_3)\ge \max \{k_1+k_2,k_1+k_3,k_2+k_3\}$（逐项相乘本来就需要这么多操作）；
• 对 $\alpha \le k\le 1$：$\omega (1,k,1)\le 2+\beta (k-\alpha )$。

第 4、5 节复杂度里那些”非整”的指数（$2.473$、$2.458$、$0.640$）全部来自把 $\omega (\cdot ,\cdot ,\cdot )$ 的这些界代入平衡方程——读者现在只需要记住：矩形乘法的指数函数是可查表的已知量，平衡方程解出来后代入即可。

3. 逐 entry Grover：$\tilde{O}(n^{5/2})$ 通用基线

Proposition 2. 设半环 $(S,\oplus ,\otimes )$ 满足：(i) $n$ 个数的 $\oplus$ 聚合可用 $\tilde{O}(\sqrt{n})$ 次查询完成（$\oplus$ 为 $\vee$ 时用原语一，为 $\min /\max$ 时用原语三）；(ii) 每个 $\otimes$ 可在 $\mathrm{polylog}$ 时间内实现。则 $n\times n$ 半环乘积可在 $\tilde{O}(n^{5/2})$ 时间（每查询计 $1$）内以高概率算出。

证明。固定 $(i,j)$，把 $C_{ij}={⨁}_{k=1}^n(A_{ik}\otimes B_{kj})$ 看作在候选集 $\{1,\dots ,n\}$ 上、以"$A_{ik}\otimes B_{kj}$"为权值的聚合问题：

• $\oplus =\vee$：$C_{ij}=1$ 当且仅当存在标记的 $k$（标记条件 $A_{ik}\wedge B_{kj}=1$），原语一给出 $\tilde{O}(\sqrt{n})$；
• $\oplus =\min$ 或 $\max$：对权值 $g(k)=A_{ik}\otimes B_{kj}$ 用原语三，$\tilde{O}(\sqrt{n})$。

每次候选评估需要 $2$ 次查询（读 $A_{ik}$、$B_{kj}$）加 $\mathrm{polylog}$ 算术，故单个 entry 成本 $\tilde{O}(\sqrt{n})$；$n^2$ 个 entry 逐个处理，总代价 $\tilde{O}(n^{5/2})$。Q.E.D.

这个基线覆盖 Boolean、$(\max ,\min )$、$(\min ,+)$ 三个半环，而且照搬了经典”三重循环”的结构。它有两个明显的浪费：

1. 数据不共享。同一个 $A_{ik}$ 出现在整行 $n$ 个输出 entry 的候选列表里，逐 entry 处理等于把它读 $n$ 次；
2. 判断不共享。判断"$C_{ij}\ge \lambda$"对一族阈值 $\lambda$ 是高度相关的 Boolean 量（第 4.1 节），逐 entry 二分阈值会重复做大量几乎相同的乘法。

对照经典基线还能看清它的位置：对 Boolean，$\tilde{O}(n^{5/2})$ 被 $\tilde{O}(n^{\omega })$ 完全压制，没有价值；对 $(\max ,\min )$ 与距离乘积，它当时是量子一侧最好的已知界，且已经优于当时最好的经典算法（$2.687$ 与”无亚立方算法”）。改进的方向因此也很明确：要么让阈值判断被许多 entry 共享（第 4、5 节），要么让碰撞搜索被许多输出共享（第 6 节）。

4. $(\max ,\min )$ 乘积：阈值化、支配乘积与 $n^{2.473}$

4.1 阈值 Boolean 化

Lemma 3（阈值等价）. 对阈值 $\lambda$ 定义 Boolean 矩阵

$$A_{ik}^{(\lambda )}=1[A_{ik}\ge \lambda ],B_{kj}^{(\lambda )}=1[B_{kj}\ge \lambda ],$$

（$1[\cdot ]$ 为指示函数。）则在 Boolean 半环中计算 $A^{(\lambda )}\cdot B^{(\lambda )}$，有

$$C_{ij}\ge \lambda ⟺(A^{(\lambda )}\cdot B^{(\lambda )}{)}_{ij}=1,$$

且 $C_{ij}=\max \{\lambda :(A^{(\lambda )}\cdot B^{(\lambda )}{)}_{ij}=1\}$（在输入权值集合上取）。

证明。核心是 $\min$ 的阈值分解：对实数 $a,b$，

$$\min (a,b)\ge \lambda ⟺a\ge \lambda \text{且}b\ge \lambda ,$$

因为 $\min (a,b)$ 是两者中较小者，它不小于 $\lambda$ 当且仅当较小者不小于 $\lambda$，等价于两者都不小于 $\lambda$。于是逐条等价：

$$C_{ij}=\underset{k}{\max }\min (A_{ik},B_{kj})\ge \lambda ⟺\exists k:\min (A_{ik},B_{kj})\ge \lambda ⟺\exists k:A_{ik}\ge \lambda \wedge B_{kj}\ge \lambda ,$$

最后一个条件恰是”$(i,k)$ 在 $A^{(\lambda )}$ 中为 $1$ 且 $(k,j)$ 在 $B^{(\lambda )}$ 中为 $1$“，即 Boolean 乘积的 entry 为 $1$。第二句由 $\{\lambda :C_{ij}\ge \lambda \}$ 是向下封闭的集合（$C_{ij}\ge {\lambda }^{\prime }\ge \lambda \Rightarrow C_{ij}\ge \lambda$）直接得到：最大的可行 $\lambda$ 恰是 $C_{ij}$ 自身可能取到的值。Q.E.D.

这个引理说明 $(\max ,\min )$ 乘积可以被”一族 Boolean 乘积”回答。朴素的用法是对每个 entry 二分 $\lambda$，但每次二分都要重新做一次几乎一样的 $n^3$ 级工作。真正需要的是把一族阈值判断批量地塞进少量几次矩阵乘法——这正是下一步。

4.2 支配乘积与还原恒等式

Boolean 阈值化把”$A_{ik}$ 与 $B_{kj}$ 都要过关”写成两个独立条件。$(\max ,\min )$ 的算法实际使用的是它的”单边”版本，称为支配 (dominance) 比较 $A_{ik}\le B_{kj}$。形式化地，对取值于 $\mathbb{Z}\cup \{\infty \}$ 的 $A$ 与 $\mathbb{Z}\cup \{-\infty \}$ 的 $B$：

• 存在支配乘积 $A\ast B$ 是 Boolean 矩阵：$(A\ast B{)}_{ij}=1$ 当且仅当存在 $k$ 使 $A_{ik}\le B_{kj}$；
• 截断支配乘积（本词条记作 $A\oslash B$；原论文用一个专门的截断符号）：

$$(A\oslash B{)}_{ij}=\max \{A_{ik}:A_{ik}\le B_{kj}\}$$

（若集合为空取 $-\infty$，即”所有 $A_{ik}$ 都严格大于 $B_{kj}$”）。

Lemma 4（还原恒等式）. 设 $C$ 是 $(\max ,\min )$ 乘积，则

$$C_{ij}=\max \{(A\oslash B{)}_{ij},(B^{\mathsf{T}}\oslash A^{\mathsf{T}}{)}_{ji}\},$$

其中 $\mathsf{T}$ 表示转置。因此 $(\max ,\min )$ 乘积可归约为两次截断支配乘积。

证明。先把每个 $\min$ 拆到”取的是哪一边”。对每个 $k$：

$$\min (A_{ik},B_{kj})=\{\begin{array}{ll}{A}_{ik},& A_{ik}\le B_{kj},\\ B_{kj},& B_{kj}<A_{ik}\end{array}$$

（等号归入第一种情形，两种情形互斥且覆盖所有 $k$。）于是

$$C_{ij}=\max \{\underset{k:A_{ik}\le B_{kj}}{\max }{A}_{ik},\underset{k:B_{kj}<A_{ik}}{\max }{B}_{kj}\}.$$

第一个内层 $\max$ 正是 $(A\oslash B{)}_{ij}$ 的定义。第二个内层 $\max$ 是”$B_{kj}\le A_{ik}$（含等号）的那些 $k$ 中 $B_{kj}$ 的最大值”；而 $(B^{\mathsf{T}}\oslash A^{\mathsf{T}}{)}_{ji}=\max \{B_{jk}^{\mathsf{T}}:B_{jk}^{\mathsf{T}}\le A_{kj}^{\mathsf{T}}\}=\max \{B_{kj}:B_{kj}\le A_{ik}\}$，与它只差等号处的归属——但等号处 $B_{kj}=A_{ik}$，这个值已经出现在第一个内层 $\max$ 中（因为 $A_{ik}\le B_{kj}$ 成立），所以外面再取 $\max$ 时两种归属给出同一结果。Q.E.D.

为什么要绕道支配比较？因为支配比较可以移项：对任意常数 $x,y$，比较 $A_{ik}\le B_{kj}+x-y$ 与移位后的比较 $A_{ik}-x\le B_{kj}-y$ 是同一件事：

$$A_{ik}\le B_{kj}+x-y⟺A_{ik}-x\le B_{kj}-y.$$

单边比较的两侧各自平移后仍是同类比较，于是”一族阈值”可以被编码成”一族平移过的矩阵”（第 5 节正是这么用的）；而双边阈值条件 $A_{ik}\ge \lambda \wedge B_{kj}\ge \lambda$ 无法这样平移拆分。此外，第 4.3 节的分块技巧也只在单边比较上顺畅。

4.3 批量化：广义存在支配乘积

定义（广义存在支配乘积）. 给定 $u$ 个矩阵 $A^{(1)},\dots ,A^{(u)}$（取值 $\mathbb{Z}\cup \{\infty \}$）与 $v$ 个矩阵 $B^{(1)},\dots ,B^{(v)}$（取值 $\mathbb{Z}\cup \{-\infty \}$），其广义存在支配乘积是 $n\times n$ 矩阵 $C$：

$$C_{ij}=\text{字典序最大的}(x,y)\in \{1,\dots ,u\}\times \{1,\dots ,v\}\text{使得}(A^{(x)}\ast B^{(y)}{)}_{ij}=1,$$

若无这样的 $(x,y)$ 则取 $(0,0)$。$u=v=1$ 时就是普通的存在支配乘积。

它是一次性回答”一族支配判断”的机器。Le Gall–Nishimura 的核心是一个分块算法：

Lemma 5（分块分解）. 把所有 $A$ 侧有限 entry 排序后切成 $t$ 个连续块 $L_1,\dots ,L_t$（每块至多 $m_1/t$ 个值，$m_1$ 为 $A$ 侧有限 entry 总数）。对每块 $r$ 定义带通矩阵 ${\bar{A}}_r^{(x)}[i,k]=1[A_{ik}^{(x)}\in L_r]$ 与阈值矩阵 ${\bar{B}}_r^{(y)}[k,j]=1[B_{kj}^{(y)}\ge \max L_r]$。则

$$(A^{(x)}\ast B^{(y)}{)}_{ij}=1⟺\underset{\text{跨块 witness}}{\underbrace{\exists r,k:{\bar{A}}_r^{(x)}[i,k]\wedge {\bar{B}}_r^{(y)}[k,j]}}\text{或}\underset{\text{同块 witness}}{\underbrace{\exists r,k:A_{ik}^{(x)}\in L_r\wedge B_{kj}^{(y)}\in [\min L_r,\max L_r)\wedge A_{ik}^{(x)}\le B_{kj}^{(y)}}}.$$

证明。（$\Leftarrow$）跨块情形：$A_{ik}^{(x)}\in L_r$ 给出 $A_{ik}^{(x)}\le \max L_r$（$\max L_r$ 是该块的最大值），而 $\bar{B}$ 的条件给出 $B_{kj}^{(y)}\ge \max L_r$，串联即 $A_{ik}^{(x)}\le B_{kj}^{(y)}$。同块情形直接就是支配条件。

（$\Rightarrow$）设 $k$ 是 witness：$A_{ik}^{(x)}\le B_{kj}^{(y)}$。设 $A_{ik}^{(x)}\in L_r$。若 $B_{kj}^{(y)}\ge \max L_r$，则是跨块情形（用这个 $r$ 与 $k$）。否则 $B_{kj}^{(y)}<\max L_r$，与 $A_{ik}^{(x)}\le B_{kj}^{(y)}$ 及 $A_{ik}^{(x)}\ge \min L_r$ 联立得 $B_{kj}^{(y)}\in [\min L_r,\max L_r)$，是同块情形。Q.E.D.

两个部分的成本结构完全不同，这正是算法的精妙之处：

• 跨块部分是纯 Boolean 的。对每对 $(x,y)$，${\bigvee }_r({\bar{A}}_r^{(x)}\cdot {\bar{B}}_r^{(y)})$ 可以把所有 $(x,y,r)$ 一次性拼成一个大乘法：把块指标 $r$ 与矩阵指标 $x,y$ 都堆进矩阵的行列里，得到一个 $(nu)\times (nt)$ 矩阵乘 $(nt)\times (nv)$ 矩阵的 Boolean 乘积，代价

  $n^{\omega (1+{\log }_{n}u,1+{\log }_{n}t,1+{\log }_{n}v)}.$

  三个指数就是三个”堆叠方向”的维度取对数。

• 同块部分是稀疏的，交给量子枚举。每个 $B$ 侧有限 entry 的数值只落入唯一一个块的值域 $[\min L_r,\max L_r)$，而该块、该行的 $A$ 侧 entry 平均只有约 $\frac{m_1/t}{n}=\frac{m_1}{nt}$ 个，故”同块候选三元组”总数约为 $\frac{m_1{m}_2}{nt}$（$m_2$ 为 $B$ 侧有限 entry 总数）。按 Lemma 1 的 SearchAll 记账，枚举出全部”使某个 $(i,j)$ 被击中的同块 witness”的成本为 $\sqrt{\frac{m_1{m}_2}{nt}\cdot (\text{解数})}$；解数有两部分：矩阵对个数 $uv$（每对至少要确认有无解）与被更新的输出 entry 数（至多 $n^2$）。用 Cauchy–Schwarz 合并后得到两项：

  $\sqrt{\frac{m_1{m}_{2}n}{t}}\text{与}\sqrt{\frac{m_1{m}_{2}uv}{tn}}.$

  （如何把行分布不均的块整理成可 $\mathrm{polylog}$ 时间随机访问的数据结构，是论文附录的技术核心；此处按成本结构引用其结论。）

Proposition 6（Le Gall–Nishimura：广义支配乘积的复杂度）. 对任意参数 $t\in \{1,\dots ,m_1\}$，广义存在支配乘积可在

$$\tilde{O}\left(\sqrt{\frac{m_1{m}_{2}n}{t}}+\sqrt{\frac{m_1{m}_{2}uv}{tn}}+n^{\omega (1+{\log }_{n}u,1+{\log }_{n}t,1+{\log }_{n}v)}\right)$$

时间内以高概率算出。

三个竞争项的直观分工：$t$ 越大，块越细，同块候选越少、量子枚举越便宜（前两项随 $t$ 递减）；但堆叠维度 $(nu)\times (nt)\times (nv)$ 越大，经典矩形乘法越贵（第三项随 $t$ 递增）。最优的 $t$ 让两类成本同阶——这就是原文所说”调节块大小，使批量乘法与 residual search 成本平衡”的准确含义。

4.4 算法组装与参数平衡

现在把广义支配乘积接回 $(\max ,\min )$。由 Lemma 4 只需计算 $A\oslash B$（转置版本对称）。对 $A\oslash B$ 的每个 entry，值 $C_{ij}$ 是”被支配的 $A_{ik}$ 中的最大值”，算法分两步：

Step 1（定位块）. 把 $A$ 的每一行 $i$ 单独排序、切成 $s=\lceil n/g\rceil$ 个连续块 $R_1^i,\dots ,R_s^i$（每块至多 $g$ 个元素）；令 $A_r[i,k]=A_{ik}$ 若 $A_{ik}\in R_r^i$，否则 $\infty$。对每个 $(i,j)$ 求最大的 $r_{ij}$ 使 $(A_r\ast B{)}_{ij}=1$：这恰是广义存在支配乘积（取 $u=s$、$v=1$、族 $\{A_r\}$ 与 $\{B\}$，按 $(x)$ 的降字典序）。由于所有 $A_r$ 的有限 entry 总数 $m_1\le s\cdot ng=n^2$、$m_2\le n^2$，代入 Proposition 6 得（矩阵族大小那一项在此情形被另外两项支配，见下面的核对）：

$$\tilde{O}\left(\frac{n^{5/2}}{\sqrt{t}}+n^{\omega (2-\delta ,1+\gamma ,1)}\right),g=n^{\delta },t=n^{\gamma }.$$

逐因子说明：第一项是 $\sqrt{m_1{m}_{2}n/t}=\sqrt{n^4\cdot n/t}$；第二项的三个指数来自左矩阵 $(n\cdot s)\times (nt)$ 的行数 $1+{\log }_{n}s=2-\delta$、公共维 $1+{\log }_{n}t=1+\gamma$、右矩阵列数 $1$。被支配的第三项为 $\sqrt{m_1{m}_2\cdot s/(tn)}=n^{(4+1-\delta -\gamma -1)/2}=n^{2-(\delta +\gamma )/2}$，在 $\delta +\gamma =1$ 时恰为 $n^{3/2}$，确实可忽略。

Step 2（块内取最大）. 由 Step 1，

$$C_{ij}=\max \{A_{ik}:A_{ik}\in R_{r_{ij}}^i,A_{ik}\le B_{kj}\},$$

（证明同 Lemma 5 的分类：使 $A_{ik}\le B_{kj}$ 的最大 $A_{ik}$ 要么在最大的可行块里，要么不存在。）候选集 $R_{r_{ij}}^i$ 至多 $g$ 个元素，对它用 Dürr–Høyer 最大搜索，每个 entry 花 $\tilde{O}(\sqrt{g})$，共 $n^2$ 个 entry：

$$\tilde{O}\left(n^2\sqrt{g}\right)=n^{2+\delta /2}.$$

平衡。 总成本（构造分块矩阵的预处理 $n^{2}s=n^{3-\delta }$ 由第 2 节的朴素下界 $\omega (2-\delta ,1+\gamma ,1)\ge (2-\delta )+1=3-\delta$ 归入第三项）为

$$\tilde{O}\left(\frac{n^{5/2}}{\sqrt{t}}+n^{\omega (2-\delta ,1+\gamma ,1)}+n^{2+\delta /2}\right).$$

$\gamma$ 增大时第一项减、第二项增，最优在两者相等处：

$$\omega (2-\delta ,1+\gamma ,1)=\frac{5-\gamma }{2}(\text{平衡一}).$$

再把第三项拉平（一升一降的两项之和在相等处取最优量级，与 collision 词条的平衡同理）：

$$\frac{5-\gamma }{2}=2+\frac{\delta }{2}⟺5-\gamma =4+\delta ⟺\gamma +\delta =1(\text{平衡二}).$$

把 $\delta =1-\gamma$ 代入平衡一（此时 $2-\delta =1+\gamma$）：

$$\gamma +2\omega (1+\gamma ,1+\gamma ,1)=5.$$

这个方程的解需要矩形乘法指数的界。用第 2 节的性质逐步化开：

$$\omega (1+\gamma ,1+\gamma ,1)\stackrel{\text{置换}}{=}\omega (1,1+\gamma ,1+\gamma )\stackrel{\text{齐次}}{=}(1+\gamma )\omega \left(1,1,\frac{1}{1+\gamma }\right)\stackrel{\text{置换}}{=}(1+\gamma )\omega \left(1,\frac{1}{1+\gamma },1\right)\le (1+\gamma )\left(2+\beta (\frac{1}{1+\gamma }-\alpha )\right),$$

最后一步用了 $\omega (1,k,1)\le 2+\beta (k-\alpha )$。代回方程整理得

$$\gamma \ge \frac{1+2\alpha \beta -2\beta }{5-2\alpha \beta },\text{复杂度}\tilde{O}\left(n^{(5-\gamma )/2}\right)=\tilde{O}\left(n^{(12-6\alpha \beta +\beta )/(5-2\alpha \beta )}\right).$$

数值演示（代入论文写作时的界 $\omega <2.373$、$\alpha >0.302$，按等号取值）：$\beta =\frac{0.373}{0.698}\approx 0.534$，$\alpha \beta \approx 0.161$，于是

$$\gamma \ge \frac{1+0.322-1.068}{5-0.322}=\frac{0.254}{4.678}\approx 0.054,\frac{5-\gamma }{2}\le \mathrm{2.473.}$$

这就得到 Zoo 快照记录的

$$\boxed{\tilde{O}\left(n^{2.473}\right)}$$

（存在支配乘积本身按同一路线可得 $\tilde{O}(n^{(5+\omega )/3})\le O(n^{2.458})$；当时最好的经典存在支配乘法是 $O(n^{2.684})$。）

保留条款（原文明确指出，必须随结论一起引用）：$2.473$ 不是算法的内在常数，而是”把当时可用的矩形乘法指数代入平衡方程”得到的快照值；若经典矩形乘法上界改进，数值应随之更新，但算法结构——“阈值批处理 + 量子边界搜索”——不变。此外这是第 1.2 节所述时间模型下的结论（相干随机访问计单位成本），不是纯查询界。

4.5 应用：全点瓶颈路径

$(\max ,\min )$ 乘法的一个 entry 回答”经某条指定中转边的最大瓶颈”；完整的全点瓶颈路径只需反复平方：令 $D^{(1)}$ 为边权矩阵（无边处 $-\infty$），$D^{(2r)}=D^{(r)}{\otimes }_{(\max ,\min )}{D}^{(r)}$，则 $D_{ij}^{(r)}$ 是”至多 $r$ 条边的路径”的最大瓶颈（归纳：一条至多 $2r$ 条边的路径在中点拆成两段至多 $r$ 条边的路径，瓶颈相接处取 $\min$，对中点取 $\max$）。路径至多 $n-1$ 条边，故 $\lceil {\log }_2(n-1)\rceil$ 次平方足够，总时间 $\tilde{O}(T(n))$。于是全点瓶颈路径也得到 $\tilde{O}(n^{2.473})$，优于当时最好的经典 $O(n^{2.687})$。

5. 距离乘积：高位分解与 $2^{0.64L}{n}^{2.46}$

5.1 阈值为什么失效，以及移项技巧

对距离乘积 $C_{ij}={\min }_k(A_{ik}+B_{kj})$，第 4.1 节的阈值化失效：条件

$$A_{ik}+B_{kj}\le \lambda$$

不能拆成”$A$ 侧一个条件 $\wedge$ $B$ 侧一个条件”——和式的两端可以互相补偿，这是 $(\min ,+)$ 与 $(\max ,\min )$ 的本质差别。但支配比较的移项性质（第 4.2 节）恰好救场：对任意平移量 $x,y$，

$$A_{ik}+B_{kj}\le x+y⟺(A_{ik}-x)\le (-B_{kj}+y).$$

左移 $A$、翻转 $B$，和式阈值就变成了单边支配比较，两边的平移量可以各自取不同粒度——这就是”高位分解”的全部秘密。

5.2 区间定位

设所有权值非负有限（取值为负或 $\infty$ 的一般情形，原文用一次额外的支配乘法单独判别，此处从简），取 $W$ 为 2 的幂且 $W>\max A_{ik}+\max B_{kj}$，于是每个 $C_{ij}<W$，可用 ${\log }_{2}W$ 位表示。目标不是算出全部位，而是前 $L$ 位：等价地，找到 $d\in \{1,\dots ,2^L\}$ 使 $C_{ij}\in [(d-1)\Delta ,d\Delta )$，其中 $\Delta =W/2^L$。

对 $x,y\in \{0,\dots ,2^{L/2}-1\}$（设 $L$ 为偶数；奇数情形类似）定义平移矩阵

$$A_x^{\prime }[i,k]=A_{ik}-x\cdot \frac{W}{2^{L/2}},B_y^{\prime }[k,j]=-B_{kj}+y\cdot \frac{W}{2^L}.$$

Lemma 7（区间定位）. 设 $d=d_1\cdot 2^{L/2}+d_2$（$0\le d_1,d_2<2^{L/2}$），并令 $D_d=A_{d_1}^{\prime }{\ast }_{<}{B}_{d_2}^{\prime }$ 为严格存在支配乘积（把 $\le$ 换成 $<$）。则

$$D_d[i,j]=0⟺\underset{k}{\min }(A_{ik}+B_{kj})\ge d\cdot \Delta .$$

因此 $C_{ij}\in [(d-1)\Delta ,d\Delta )$ 当且仅当 $d$ 是使 $D_d[i,j]=1$ 的最小正整数（前 $L$ 位即 $d-1$）。

证明。逐个等价：

$$D_d[i,j]=1⟺\exists k:A_{d_1}^{\prime }[i,k]<B_{d_2}^{\prime }[k,j]⟺\exists k:A_{ik}-d_1\frac{W}{2^{L/2}}<-B_{kj}+d_2\frac{W}{2^L},$$

移项得

$$⟺\exists k:A_{ik}+B_{kj}<d_1\frac{W}{2^{L/2}}+d_2\frac{W}{2^L}=d_1\cdot 2\Delta +d_2\cdot \Delta =d\Delta ,$$

（中间用了 $\frac{W}{2^{L/2}}=2\Delta$ 与 $\frac{W}{2^L}=\Delta$。）取否定即第一条断言。对第二条：$\{d:D_d[i,j]=1\}=\{d:{\min }_k(A_{ik}+B_{kj})<d\Delta \}$ 关于 $d$ 向上封闭（$d$ 越大阈值越高越容易小于它），故最小可行 $d$ 满足 $\min <(d)\Delta$ 且 $\min \ge (d-1)\Delta$，即 $C_{ij}\in [(d-1)\Delta ,d\Delta )$。Q.E.D.

5.3 高半/低半拆分与一次广义支配乘积

朴素做法（Vassilevska–Williams 一系的经典路线）是把 $2^L$ 个阈值 $d\Delta$ 各做一次存在支配乘法，代价 $\tilde{O}(2^L{n}^{(3+\omega )/2})\le \tilde{O}(2^L{n}^{2.69})$。量子的改进分两层：

1. 拆位。把 $d$ 的高 $L/2$ 位 $d_1$ 与低 $L/2$ 位 $d_2$ 分给两侧：阈值 $d\Delta =d_1\cdot 2\Delta +d_2\cdot \Delta$ 中，粗粒度 $2\Delta$ 的平移放在 $A$ 侧（$x=d_1$），细粒度 $\Delta$ 的平移放在 $B$ 侧（$y=d_2$）。于是 $2^L$ 个阈值变成 $2^{L/2}$ 个 $A$ 型矩阵与 $2^{L/2}$ 个 $B$ 型矩阵的配对族。
2. 批量化。对这个族（$u=v=2^{L/2}$）调用第 4.3 节的广义存在支配乘积，按使 $D_d=1$ 的最小 $d$ 取序（把字典序反过来即可，论文指出证明对任意全序成立），一次算出所有 $(i,j)$ 的 $d$。

5.4 复杂度与 $0.640$ 的来历

族的大小让 $m_1\le 2^{L/2}{n}^2$、$m_2\le 2^{L/2}{n}^2$。代入 Proposition 6 并略去被支配的矩阵族项：

$$\tilde{O}\left(\frac{n^{5/2}{2}^{L/2}}{\sqrt{t}}+n^{\omega (1+\mu /2,1+\gamma ,1+\mu /2)}\right),\mu ={\log }_n{2}^L,t=n^{\gamma }.$$

（第一项是 $\sqrt{m_1{m}_{2}n/t}=\sqrt{2^L{n}^5/t}$；第二项的维度是 $(n\cdot 2^{L/2})\times (nt)$ 乘 $(nt)\times (n\cdot 2^{L/2})$。）$\gamma$ 一升一降，最优在

$$5+\mu -\gamma =2\omega (1+\mu /2,1+\gamma ,1+\mu /2)$$

此时复杂度为 $\tilde{O}(n^{(5+\mu -\gamma )/2})$。用第 2 节的性质把右端的 $\omega$ 化开（每步标注依据）：

$$\omega (1+\mu /2,1+\gamma ,1+\mu /2)\stackrel{\text{置换}}{=}\omega (1+\mu /2,1+\mu /2,1+\gamma )\stackrel{\text{单调性}}{\le }\omega (1+\mu /2,1+\mu /2,1)+\gamma \stackrel{\text{齐次性}}{=}(1+\mu /2)\omega \left(1,1,\frac{1}{1+\mu /2}\right)+\gamma ,$$

再置换一次中间两个参数、并用 $\omega (1,k,1)\le 2+\beta (k-\alpha )$（此处 $k=\frac{1}{1+\mu /2}=\frac{2}{2+\mu }$）：

$$\omega (1+\mu /2,1+\gamma ,1+\mu /2)\le \gamma +(1+\mu /2)\left(2+\beta (\frac{2}{2+\mu }-\alpha )\right).$$

代入平衡方程解出

$$\gamma \ge \frac{(\alpha \beta -1)\mu +(1-2\beta +2\alpha \beta )}{3},\text{复杂度}\tilde{O}\left(n^{\frac{5+\omega }{3}+\frac{4-\alpha \beta }{6}\mu }\right).$$

数值演示（同样的 $\omega <2.373,\alpha >0.302$）：常数部分 $\frac{5+2.373}{3}=2.4577$，$\mu$ 的系数 $\frac{4-0.161}{6}=0.640$。于是

$$\tilde{O}\left(2^{0.640L}{n}^{(5+\omega )/3}\right)\le O\left(2^{0.640L}{n}^{2.458}\right),$$

而 Zoo 快照将其记录为 $\tilde{O}(2^{0.64L}{n}^{2.46})$。对照经典：朴素逐桶是 $O(2^L{n}^{2.69})$；同一套分块技术反过来还把经典算法改进到 $O(2^{0.960L}{n}^{2.687})$——把对 $2^L$ 的线性依赖降为亚线性，是这篇工作”量子技术反哺经典”的一面。

5.5 精度依赖的保留条款

引用这一结果时有三条必须随行的限制（原文均明确指出）：

1. 只输出前 $L$ 位。它不是”精确任意大小整数距离乘积”的统一 $n^{2.46}$ 算法；$L$（以及权值编码长度 $\log W$）必须作为参数保留在复杂度里。
2. 适用区间。平凡量子算法 $\tilde{O}(n^{5/2})$ 已能算出全部位，因此该算法只在 $2^{0.64L}{n}^{2.46}\le n^{5/2}$（特别地 $2^L\le n^2$）的范围内有意义；$L$ 过大时应回退到平凡算法。
3. 时间模型。与第 4 节相同，是相干随机访问计单位成本的时间界，不是纯查询界。

6. Boolean：输出敏感、图碰撞与 $\tilde{O}(n\sqrt{\ell })$ 查询

6.1 输出敏感的记账

Boolean 情形引入第二个复杂度参数：

$$\ell =|\{(i,j):C_{ij}=1\}\Vert ,$$

即输出中 1 的个数。理想的目标是”输出多稀疏、算法多便宜”。本节采用纯查询模型（第 1.2 节），引用的是 Jeffery–Kothari–Magniez 的结果（Zoo 161）。

先看朴素算法，把 §3 的基线改造成输出敏感版。把搜索对象从”entry”换成”1-entry”：用 Lemma 1 的 SearchAll 在 $n^2$ 个位置对 $(i,j)$ 上枚举全部 $\ell$ 个”有 witness 的位置对”，每次检验”$(i,j)$ 是否有 witness”本身是一次对 $k\in [n]$ 的 Grover 搜索（$\tilde{O}(\sqrt{n})$）：

$$\tilde{O}\left(\sqrt{n^2\cdot \ell }\times \sqrt{n}\right)=\tilde{O}\left(n^{3/2}\sqrt{\ell }\right)$$

次查询。这正是 Buhrman–Špalek 2006 年给出的界。$n^{3/2}$ 那个多余的平方根来自”外层搜索每检验一个 $(i,j)$ 都要重新扫一遍 $k$“——witness 的信息没有跨 entry 复用。去掉它就是接下来的任务。

6.2 化为图碰撞

回忆 $C_{ij}=1$ 当且仅当行支撑与列支撑相交：

$$C_{ij}=1⟺\mathrm{supp}(A_{i,\ast })\cap \mathrm{supp}(B_{\ast ,j})\ne \varnothing .$$

把”相交”结构显式地写成图。维护一个尚未完成的部分结果矩阵 $\tilde{C}$（初始为全 $0$，每当确认 $C_{ij}=1$ 就置 ${\tilde{C}}_{ij}=1$）。对每个 $k\in [n]$ 定义二部图 $G_k$：

• 顶点：左部 $\mathcal{A}=[n]$（行指标 $i$）、右部 $\mathcal{B}=[n]$（列指标 $j$）；
• 边集：$(i,j)\in E(G_k)$ 当且仅当 ${\tilde{C}}_{ij}=0$——即邻接矩阵是 $\tilde{C}$ 的逐 entry 补；
• 两侧的未知标记：$f_A(i)=A_{ik}$（$A$ 的第 $k$ 列）、$f_B(j)=B_{kj}$（$B$ 的第 $k$ 行）。

Lemma 8. $(i,j)$ 是 $G_k$ 的一个图碰撞（两侧都标记且 $(i,j)$ 是边）当且仅当 $k$ 是 $C_{ij}=1$ 的一个 witness 且 ${\tilde{C}}_{ij}=0$。此外 $G_k$ 的非边数（$=\tilde{C}$ 中 1 的个数）至多为 $\ell$。

证明。图碰撞条件是 $A_{ik}=f_A(i)=1$、$B_{kj}=f_B(j)=1$、$(i,j)\in E(G_k)$，即 $A_{ik}=B_{kj}=1$ 且 ${\tilde{C}}_{ij}=0$。前两条等价于 $k$ witness 了 $C_{ij}=1$（Boolean 乘积定义），第三条说明这个 1 还没被记录。非边数：非边即 $\tilde{C}$ 的 1-entry，而 $\tilde{C}⪯C$，故不超过 $\ell$。Q.E.D.

于是算法轮廓：寻找一个”在某个 $G_k$ 中有碰撞”的 $k$，把该图的所有碰撞记入 $\tilde{C}$，把 $k$ 从候选中删除，重复直到没有这样的 $k$。关键观察是 $G_k$ 永远近乎完全二部图（非边至多 $\ell$）。一般图上的图碰撞最优要用 Johnson 图量子行走 $O(n^{2/3})$（见图碰撞教程），但近乎完全图上便宜得多——这与 §3”不共享”的批评正相反，是共享碰撞数据的正面例子。

6.3 稠密图上找全部图碰撞

先看完全二部图有多容易：分别用 SearchAll 找出左部全部 $t_A$ 个标记点与右部全部 $t_B$ 个标记点，输出 $f_A^{-1}(1)\times f_B^{-1}(1)$。碰撞数 $\lambda =t_A{t}_B$，成本

$$\tilde{O}\left(\sqrt{n{t}_A}+\sqrt{n{t}_B}\right)=\tilde{O}\left(\sqrt{n\lambda }\right),$$

（因为 $t_A,t_B\ge 1$ 且 $t_A,t_B\le \lambda =t_A{t}_B$，两个平方根都不超过 $\sqrt{n\lambda }$）。

一般”近完全”图的算法（记非边数为 $m$，碰撞数 $\lambda$）：

1. 找最高度标记点。顶点度数是已知的经典信息（图已知），标记未知——用第 2 节原语三的变体在 $\tilde{O}(\sqrt{n})$ 次查询内找到左部度最大的标记点 $r$。

2. 情形一（$r$ 的非邻居少，$c_r\le \sqrt{m}$）：

   • (a) 在 $r$ 的邻居中 SearchAll 找全部标记点，输出碰撞对 $(r,\cdot )$：$\tilde{O}(\sqrt{n\lambda })$；
   • (b) 直接读出 $r$ 的全部 $c_r\le \sqrt{m}$ 个非邻居的标记：$O(\sqrt{m})$。至此右部的标记情况完全已知；
   • (c) 令 ${\mathcal{A}}^{\prime }=\{i:i\text{ 有一个标记的邻居}\}$（图已知，故 ${\mathcal{A}}^{\prime }$ 可经典计算），SearchAll 找 ${\mathcal{A}}^{\prime }$ 中全部标记点：$\tilde{O}(\sqrt{n\lambda })$。

3. 情形二（$c_r\ge \sqrt{m}$）：度排在 $r$ 前的顶点都未标记（$r$ 是最高度的标记点），可整批丢弃；剩下的 $n-r+1$ 个左部顶点每个的非邻居数 $\ge c_r\ge \sqrt{m}$，故

   $$(n-r+1)\cdot \sqrt{m}\le \sum _i{c}_i=m⟹n-r+1\le \sqrt{m},$$

   把它们全部读出只要 $O(\sqrt{m})$；随后与 (c) 同理在”有标记邻居的右部点”里 SearchAll：$\tilde{O}(\sqrt{n\lambda })$。

Theorem 9（AllGC）. 上述算法输出非完全二部图 $G$ 上的全部图碰撞，查询数 $\tilde{O}(\sqrt{n\lambda }+\sqrt{m})$；若只需判断是否存在碰撞，把 SearchAll 换成单次搜索，得 $\tilde{O}(\sqrt{n}+\sqrt{m})$。

证明（完备性）。情形一中，任何碰撞 $(i,j)$：若 $i=r$ 则被 (a) 输出；若 $i\ne r$，则 $i$ 标记且有标记邻居 $j$，被 (c) 输出（(b) 保证右部信息完整，使 ${\mathcal{A}}^{\prime }$ 正确）。情形二中左部标记点全被读出，(c) 覆盖所有碰撞。各步成本已逐一标注。Q.E.D.

6.4 总账：Cauchy–Schwarz 收拢成 $n\sqrt{\ell }$

主循环：设共进行 $T$ 轮”成功”（找到 $k$ 并记录新 1-entry），第 $j$ 轮新发现 ${\lambda }_j$ 个碰撞，第 $j$ 轮开始时剩余候选 $t_j$。三个基本事实：

1. 每轮成功至少消耗一个 $k$，且 $k$ 至多 $n$ 个，故 $T\le n$；每个 1-entry 至少被记一次，每轮至少记一个，故 $T\le \ell$。合并 $T\le \min \{n,\ell \}$。
2. ${\sum }_{j=1}^T{\lambda }_j=\ell$（最终 $\tilde{C}=C$）。
3. 由 Cauchy–Schwarz：${\sum }_j\sqrt{{\lambda }_j}\le \sqrt{T{\sum }_j{\lambda }_j}=\sqrt{T\ell }$。

还需要第四个事实：第 $j$ 轮成功开始时，剩余的”有效 $k$“至少有 $T-j+1$ 个——每轮成功恰好删去一个 $k$，而总共要成功 $T$ 轮，故倒数第 $T-j+1$ 轮之前不可能耗尽；于是搜索参数满足 $t_j\ge T-j+1$。

成功轮的成本：找到 $k$ 的外层搜索（按当前估计 $t_j$）加一次 AllGC。失败轮的 $t$ 每轮减半，成本是几何衰减，被常数倍的最近一次成功轮吸收。逐项累计：

$$\sum _{j=1}^T\sqrt{\frac{n}{t_j}}\cdot (\sqrt{n}+{\sqrt{m}}_j)\le (\sqrt{n}+\sqrt{\ell })\sqrt{n}\sum _{j=1}^T\frac{1}{\sqrt{T-j+1}}\le 2(n+\sqrt{n\ell })\sqrt{T}\le \tilde{O}\left(n\sqrt{T}+\sqrt{n\ell T}\right),$$

（用 $m_j\le \ell$、$t_j\ge T-j+1$、${\sum }_{s=1}^T{s}^{-1/2}\le 2\sqrt{T}$。）AllGC 部分累计：

$$\sum _{j=1}^T(\sqrt{n{\lambda }_j}+\sqrt{\ell })\le \sqrt{n}\cdot \sqrt{T\ell }+T\sqrt{\ell }=\tilde{O}\left(\sqrt{n\ell T}+T\sqrt{\ell }\right).$$

合并后三类项 $n\sqrt{T},\sqrt{n\ell T},T\sqrt{\ell }$，代入 $T\le \min \{n,\ell \}$ 逐一验证：

• $n\sqrt{T}\le n\sqrt{\ell }$（$T\le \ell$）；
• $\sqrt{n\ell T}$：若 $\ell \le n$ 则 $T\le \ell$ 给 $\sqrt{n}\ell \le n\sqrt{\ell }$（两边平方即 $\ell \le n$）；若 $\ell \ge n$ 则 $T\le n$ 给 $n\sqrt{\ell }$；
• $T\sqrt{\ell }\le n\sqrt{\ell }$。

$$\boxed{\text{Boolean 乘法的查询复杂度为}\tilde{O}\left(n\sqrt{\ell }\right)\text{（对所有 }\ell \text{ 成立）}}$$

6.5 下界与紧性

Theorem 10（下界）. Boolean 乘法的查询复杂度为 $\Omega \left(n\sqrt{\min \{\ell ,n^2-\ell \}}\right)$。

证明（归约）. 从 $\ell$-Threshold 问题归约：给定 $N=n^2$ 位 oracle $f$，判断标记数是否 $\ge \ell$。构造 Boolean 乘法实例：$A=I$（单位阵，无需查询），$B$ 编码 $f$。则 $C=AB=B$，数一数 $C$ 中 1 的个数即得答案。多项式方法给出 $N$ 位 $\ell$-Threshold 需要 $\Omega (\sqrt{N\min \{\ell ,N-\ell \}})=\Omega (n\sqrt{\min \{\ell ,n^2-\ell \}})$ 次查询。Q.E.D.

对任意常数 $\epsilon <1$ 与 $\ell \le \epsilon n^2$，上界 $\tilde{O}(n\sqrt{\ell })$ 与下界 $\Omega (n\sqrt{\ell })$ 匹配（至多对数因子）：输出敏感 Boolean 乘法在稀疏输出的全部区间上是最优的。这是 Jeffery–Kothari–Magniez 论文的标志性结论，而且它的算法没有用任何量子行走——绕开了此前基于三角形查找的整套技术路线。

6.6 查询不等于时间：稀疏输入才是真正的优势区

Dense 输出的账。 当 $\ell =\Theta (n^2)$ 时 $n\sqrt{\ell }=\Theta (n^2)$，恰好等于写输出的规模——查询优势被输出淹没。更严格地说：这一系列工作把查询 $\tilde{O}(n\sqrt{\ell })$ 实现为时间 $\tilde{O}(n\sqrt{\ell }+\ell \sqrt{n})$；取 $\ell =\Theta (n^2)$ 得 $\Theta (n^{5/2})$，反而慢于经典 $\tilde{O}(n^{\omega })$。原因有三层：重复的 witness 数据结构要维护、$\tilde{C}$ 的更新是经典开销、显式输出 $n^2$ 位本身构成时间下界。所以”一般 dense Boolean 乘法并没有仅凭该查询界就击败最快经典 dense 算法”——查询与时间必须分开报告，这与本词条导言的告诫一致。

稀疏输入的时间优势。 当输入矩阵稀疏（设各有至多 $m$ 个非零 entry）而输出未必稀疏时，把非零 entry 组织成邻接表式的访问结构，量子枚举可以加速经典组合算法中的枚举步骤。Le Gall–Nishimura 给出的时间界是分段函数（$m$ 从小到大）：

$$\begin{array}{ccc}\text{非零 entry 数 }m& \text{量子时间}& \text{当时最好经典（Yuster–Zwick）}\\ m\le n^{1.151}& \tilde{O}(n^2)& \tilde{O}(n^2)\\ n^{1.151}\le m\le n^{\omega -1/2}& \tilde{O}(m^{0.517}{n}^{1.406})& \tilde{O}(m^{0.697}{n}^{1.199})\\ n^{\omega -1/2}\le m\le n^2& \tilde{O}(n^{\omega })& \tilde{O}(n^{\omega })\end{array}$$

中间一段是量子严格占优的区域。一个具体的对照点：取 $m=O(n^{(1+\omega )/2})=O(n^{1.686})$，量子时间为 $O(n^{2.277})$，而经典算法在该点已是 $\tilde{O}(n^{\omega })>n^{2.37}$。

7. 数值小例子

7.1 $(\max ,\min )$ 乘积与阈值扫描

取原文的小例子

$$A=\left(\begin{array}{cc}5& 1\\ 3& 4\end{array}\right),B=\left(\begin{array}{cc}2& 6\\ 7& 0\end{array}\right).$$

完整乘积。 逐 entry 把 $n=2$ 个候选算尽：

$$C_{11}=\max \{\min (5,2),\min (1,7)\}=\max \{2,1\}=2,C_{12}=\max \{\min (5,6),\min (1,0)\}=\max \{5,0\}=5,$$ $$C_{21}=\max \{\min (3,2),\min (4,7)\}=\max \{2,4\}=4,C_{22}=\max \{\min (3,6),\min (4,0)\}=\max \{3,0\}=3.$$

故 $C=\left(\begin{array}{cc}2& 5\\ 4& 3\end{array}\right)$，其中 $C_{12}=5$ 的 witness 是 $k=1$（$5\le 6$）。

阈值 Boolean 化（Lemma 3 的实算）。取 $\lambda =4$：

$$A^{(4)}=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),B^{(4)}=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),$$

在 Boolean 半环里逐 entry 算乘积：

$$(A^{(4)}\cdot B^{(4)}{)}_{11}=(1\wedge 0)\vee (0\wedge 1)=0,(A^{(4)}\cdot B^{(4)}{)}_{12}=(1\wedge 1)\vee (0\wedge 0)=1,$$ $$(A^{(4)}\cdot B^{(4)}{)}_{21}=(0\wedge 0)\vee (1\wedge 1)=1,(A^{(4)}\cdot B^{(4)}{)}_{22}=(0\wedge 1)\vee (1\wedge 0)=0.$$

读出：$C_{12},C_{21}\ge 4$ 而 $C_{11},C_{22}<4$，与 $C$ 一致。取 $\lambda =6$：$A^{(6)}$ 全零，乘积全零，故所有 entry $<6$（$C$ 的最大值是 $5$）。取 $\lambda =5$：$A^{(5)}=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right)$，乘积只在 $(1,2)$ 处为 $1$，故 $C_{12}\ge 5$ 而 $C_{21},C_{22}<5$；结合 $\lambda =4$ 的结果即锁定 $C_{21}=4$，结合 $\lambda =6$ 的失败即锁定 $C_{12}=5$。再补两轮：$\lambda =3$ 给出”$C_{11}<3$、其余 $\ge 3$“（故 $C_{22}=3$），$\lambda =2$ 给出 $C_{11}\ge 2$，合并即 $C_{11}=2$。原文所说”阈值 6 时失败，逐块缩窄即可定位值 5”就是这段扫描。

截断支配恒等式（Lemma 4 的实算）。对 entry $(1,2)$：

$$(A\oslash B{)}_{12}=\max \{A_{1k}:A_{1k}\le B_{k2}\}=\max \{5(5\le 6),-(1\le 0\text{不成立})\}=5,$$ $$(B^{\mathsf{T}}\oslash A^{\mathsf{T}}{)}_{21}=\max \{B_{k2}:B_{k2}\le A_{1k}\}=\max \{-(6\le 5\text{不成立}),0(0\le 1)\}=0,$$ $$C_{12}=\max \{5,0\}=5✓.$$

两步算法的演示（§4.4）。把 $A$ 的第 1 行排序为 $\{1,5\}$，取 $g=1$ 得两块 $R_1=\{1\},R_2=\{5\}$。对 $(1,2)$：Step 1 问最大的 $r$ 使 $(A_r\ast B{)}_{12}=1$，即存在 $k$ 满足 $A_{1k}\in R_r$ 且 $A_{1k}\le B_{k2}$——$r=2$ 可行（$k=1$：$5\in R_2$ 且 $5\le 6$），故 $r_{12}=2$；Step 2 在 $R_2$ 内取被支配的最大值，仍是 $5$。两步各自只做了 $\sqrt{g}$ 与一次块定位的工作。

7.2 距离乘积的高位定位

取

$$A=\left(\begin{array}{cc}6& 4\\ 3& 2\end{array}\right),B=\left(\begin{array}{cc}2& 0\\ 5& 9\end{array}\right).$$

完整乘积。

$$C_{11}=\min \{6+2,4+5\}=\min \{8,9\}=8,C_{12}=\min \{6+0,4+9\}=\min \{6,13\}=6,$$ $$C_{21}=\min \{3+2,2+5\}=\min \{5,7\}=5,C_{22}=\min \{3+0,2+9\}=\min \{3,11\}=3.$$

设定。$\max A+\max B=6+9=15$，取 $W=16$；取 $L=2$，则 $\Delta =W/2^L=4$，$2^{L/2}=2$。平移矩阵：

$$A_x^{\prime }=A-8x:A_0^{\prime }=A,A_1^{\prime }=\left(\begin{array}{cc}-2& -4\\ -5& -6\end{array}\right);$$ $$B_y^{\prime }=-B+4y:B_0^{\prime }=\left(\begin{array}{cc}-2& 0\\ -5& -9\end{array}\right),B_1^{\prime }=\left(\begin{array}{cc}2& 4\\ -1& 5\end{array}\right).$$

entry $(1,1)$（$C_{11}=8$）。按 Lemma 7，$D_d[1,1]=1⟺\min \{8,9\}<4d$：

• $d=2$（$d_1=1,d_2=0$）：比较 $A_1^{\prime }[1,k]<B_0^{\prime }[k,1]$：$-2<-2$ 不成立（严格），$-4<-5$ 不成立，故 $D_2[1,1]=0$，即 $C_{11}\ge 8$；
• $d=3$（$d_1=1,d_2=1$）：$A_1^{\prime }[1,1]=-2<B_1^{\prime }[1,1]=2$ 成立，故 $D_3[1,1]=1$，即 $C_{11}<12$；
• $d=1$：$8<4$ 不成立（$A_0^{\prime }[1,k]<B_1^{\prime }[k,1]$ 两条都不成立），$D_1[1,1]=0$。

使 $D_d[1,1]=1$ 的最小 $d$ 是 $3$，故 $C_{11}\in [8,12)$，前两位为 $d-1=2=(10{)}_2$。验证：$8=2\times 4+0$ ✓。

entry $(2,2)$（$C_{22}=3$）。$d=1$：$A_0^{\prime }[2,1]+B_1^{\prime }[1,2]$ 对应 $3+0=3<4$ 成立，故 $D_1[2,2]=1$；$d=0$ 显然 $D_0=0$。最小 $d=1$，$C_{22}\in [0,4)$，前两位为 $0$。验证：$3=0\times 4+3$ ✓。

同样地 $C_{12}=6\in [4,8)$（最小 $d=2$），$C_{21}=5\in [4,8)$（最小 $d=2$）。四个 entry 的区间定位一次完成，只需 $2^{L/2}+2^{L/2}=4$ 个平移矩阵——而朴素逐桶路线要对 $2^L=4$ 个阈值各做一次完整的支配乘法。$L$ 增大时差距拉开：前者是 $2\cdot 2^{L/2}$ 个矩阵的族（一次广义支配乘积批量处理），后者是 $2^L$ 次独立乘法；这个拆分再叠加 §5.4 的块参数平衡，共同给出 $2^{0.64L}$ 中 $0.64<1$ 的指数节省。

8. 小结与习题

要点回顾：

• 半环没有加法逆元，Strassen 式技巧依赖的”取差与消去”无从执行；Boolean 是能嵌入整数环的例外（$\tilde{O}(n^{\omega })$），$(\max ,\min )$ 与距离乘积则长期接近立方。
• 逐 entry 的量子 min/max/OR 聚合给出通用 $\tilde{O}(n^{5/2})$ 基线（Proposition 2）；它是比较基准，不共享数据与判断，也不保证胜过所有经典半环专用算法。
• $(\max ,\min )$ 经阈值 Boolean 化与截断支配乘积归约，用”排序分块 + 矩形乘法批处理 + 量子边界搜索”与两步参数平衡（$\omega (2-\delta ,1+\gamma ,1)=\frac{5-\gamma }{2}$、$\gamma +\delta =1$）达到 $\tilde{O}(n^{2.473})$；指数是矩形乘法上界的快照，随经典进展更新。
• 距离乘积的和式阈值不可分解，但移项后成为单边支配比较；高 $L/2$ 位与低 $L/2$ 位的平移分给两侧，一次广义支配乘积完成全部区间定位，得 $\tilde{O}(2^{0.64L}{n}^{2.46})$；精度参数 $L$ 必须保留。
• Boolean 输出敏感：化为”近完全二部图上的图碰撞”，找全部碰撞 $\tilde{O}(\sqrt{n\lambda }+\sqrt{m})$，Cauchy–Schwarz 收拢为 $\tilde{O}(n\sqrt{\ell })$ 查询，与 $\ell$-Threshold 下界匹配（$\ell \le \epsilon n^2$ 时最优）。
• 查询优势不等于时间优势：dense 输出时写 $n^2$ 位即成下界，$\tilde{O}(n\sqrt{\ell })$ 的查询界实现为 $\tilde{O}(n\sqrt{\ell }+\ell \sqrt{n})$ 的时间；稀疏输入才是量子时间严格占优的区域（如 $m=n^{1.686}$ 时 $n^{2.277}$ 对 $\tilde{O}(n^{\omega })$）。

习题：

1. （阈值等价）补全 Lemma 3 的证明：对实数 $a,b$ 证明 $\min (a,b)\ge \lambda ⟺(a\ge \lambda )\wedge (b\ge \lambda )$；再据此说明为什么 $(\min ,+)$ 的条件 $A_{ik}+B_{kj}\le \lambda$ 不能写成两个独立条件的合取，并各举一个使”和小于 $\lambda$ 但两个单边条件都不成立”的数值例子。
2. （完整计算）对第 7.1 节的 $A,B$，分别取 $\lambda \in \{2,3,4,5,6\}$ 写出 $A^{(\lambda )},B^{(\lambda )}$ 与 Boolean 乘积，用扫描的方式确定 $C$ 的全部 entry；再对 entry $(2,1)$ 验证截断支配恒等式 $C_{21}=\max \{(A\oslash B{)}_{21},(B^{\mathsf{T}}\oslash A^{\mathsf{T}}{)}_{12}\}$。
3. （变长求和）证明 ${\sum }_{s=1}^t\frac{1}{\sqrt{s}}\le 2\sqrt{t}$（提示：$\sqrt{s}-\sqrt{s-1}=\frac{1}{\sqrt{s}+\sqrt{s-1}}$）。由此说明：在 $N$ 个条目中枚举全部 $t$ 个解的成本 $\tilde{O}(\sqrt{N(t+1)})$ 在 $t=N$ 时退化为 $\tilde{O}(N)$——与逐个经典检查同阶，量子在”几乎全部都是解”时占不到便宜。
4. （平衡练习）在第 4.4 节的三项成本中取 $g=n^{\delta },t=n^{\gamma }$，验证：(a) $\frac{5-\gamma }{2}=2+\frac{\delta }{2}⟺\gamma +\delta =1$；(b) 平衡后矩阵族项恰为 $n^{3/2}$；(c) 用 $\omega <2.373,\alpha >0.302$ 复算 $\gamma \approx 0.054$ 与指数 $\approx 2.473$。若把 $\omega$ 的上界改进到 $2.36$，指数大约降到多少？（只需数值实验，不必解闭式。）
5. （查询与时间）解释为什么 dense 输出（$\ell =\Theta (n^2)$）时 $\tilde{O}(n\sqrt{\ell })$ 的查询界不等于亚二次总时间：分别指出 (a) 输出规模、(b) $\ell \sqrt{n}$ 项、(c) $\tilde{C}$ 的经典维护这三笔账各占多少，并与 $\tilde{O}(n^{\omega })$ 比较。
6. （oracle 模型比较）比较三种输入访问方式在 Boolean 乘法中的差别：逐 entry 的翻转 oracle、非零 entry 的邻接表式 oracle、以及直接把矩阵写进电路的经典数组。对每种方式说明：(a) 一次”读 $A_{ik}$“的代价；(b) 第 6.6 节的稀疏输入优势依赖哪一种；(c) §4–5 的时间界依赖哪一种假设。

参考文献与 Zoo 覆盖

• Zoo 编号 206：François Le Gall 与 Harumichi Nishimura, Quantum Algorithms for Matrix Products over Semirings.
• Zoo 编号 19、155、157、161：矩阵验证、输出敏感 Boolean 乘法、路径/矩阵等价与 graph-collision 改进。
• 正文引用的其他文献：Buhrman 与 Špalek, Quantum verification of matrix products, SODA 2006；Le Gall, Improved output-sensitive quantum algorithms for Boolean matrix multiplication, SODA 2012；Vassilevska Williams 与 Williams, Sub-cubic equivalences between path, matrix and triangle problems, FOCS 2010；Duan 与 Pettie (SODA 2009) 的 $(\max ,\min )$ 乘法与全点瓶颈路径算法；Vassilevska Williams (STOC 2006) 与 Yuster (SODA 2009) 的距离乘积高位算法；Yuster 与 Zwick 的稀疏 Boolean 乘法分析；Dürr 与 Høyer, A quantum algorithm for finding the minimum, arXiv:quant-ph/9607014。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch11-query-complexity/semiring-matrix-multiplication
• 内容遵循 CC BY-NC-SA 4.0 许可协议