# 量子网络流与匹配：增广路框架中的 Grover 加速

最大匹配（matching）与最大流（maximum flow）是组合优化中历史最悠久、应用最广泛的两个问题。它们的经典解法有一个共同的内核：**反复寻找增广结构**——匹配算法寻找增广路（augmenting path），流算法在残余网络（residual network）中寻找可以再多推一些流的路径，直到找不到为止。每一次"寻找"本质上都是一次图搜索，而图搜索恰恰是 Grover 类量子搜索能够二次加速的对象。

本篇教程的核心思想可以一句话概括：**量子算法不会改变 Berge 定理或 max-flow min-cut 定理这些组合学骨架，而是在残余图中用 Grover 搜索与量子最小值查找（minimum finding）来加速邻接扫描、最短增广路和 blocking-flow 子程序。** 组合结构的正确性证明、增广量的计算、最优性证书，全部保持经典。因此读懂本文的关键不是量子力学（所需的前置知识只有本站 [Grover 算法与振幅放大](../ch03-algo-basics/grover.md) 一章），而是先把经典的增广路框架彻底搞清楚——我们也将用大部分篇幅做这件事。

复杂度取决于三个参数：顶点数 $n$、边数 $m$ 与整数容量上界 $U$。没有单一的"量子最优"结论：不同参数区域由不同算法占优，而且本文介绍的是 2005 年 Ambainis–Špalek 的早期量子增广框架（Zoo 编号 168），在某些参数区间它已被后来的经典或量子工作改进。我们会明确指出每个上界的适用区域与保留条款。

:::{admonition} 本课知识点
:class: tip

1. **[问题背景与量子加速模式](#background-quantum-entry)**——能写出匹配与最大流的问题定义，说明经典算法"轮数 × 每轮扫描代价"的共同瓶颈，并解释量子加速"组合框架不动、搜索步骤换 Grover"的固定模式与适用边界。
2. **[增广路与 Berge 定理](#augmenting-path-berge)**——能写出交错路、增广路与对称差的定义，证明增广路翻转引理与 Berge 定理，并区分 maximum 与 maximal 匹配。
3. **[Hopcroft–Karp 分层增广](#hopcroft-karp-phases)**——能列出单个阶段的四个步骤，推导阶段引理与 $O(\sqrt{n})$ 阶段数上界，得出 $O(m\sqrt{n})$ 的经典复杂度。
4. **[量子搜索的插入点与匹配复杂度](#quantum-search-insertion)**——能指出 Grover 搜索替换经典邻接扫描的具体位置，解释失败邻接区间必须删除的摊还原因，并解读 $O(n\sqrt{m+n}\log n)$ 三个因子的来源与稠密、稀疏两个区域的比较结论。
5. **[blossom 收缩与一般图匹配](#blossom-contraction)**——能解释奇环为何破坏交错 BFS、Edmonds 收缩—展开—提升机制如何修复它，并说明量子版本上界为何比二分图情形多出一个 $n$ 因子。
6. **[残余网络与 max-flow min-cut](#residual-network-min-cut)**——能写出残余容量、割与瓶颈增广的定义，证明弱对偶与 max-flow min-cut 定理，并构造二分匹配到单位容量流的归约。
7. **[capacity scaling 与两条上界](#capacity-scaling-bounds)**——能解释容量缩放机制与两条算法路线，在给定参数区域计算并比较 $T_1$、$T_2$ 的指数，说明 $U^{1/3}$ 型指数的平衡来源与大 $U$ 的伪多项式保留条款。
8. **[经典证书与四顶点算例](#classical-certificate-example)**——能在四顶点网络上完整执行 Ford–Fulkerson 增广、流守恒验证与割证书核算，并解释 bounded-error 量子子程序为何仍产生零错误的输出。

:::

(background-quantum-entry)=
## 1. 问题背景：从哪里来，为什么重要

### 匹配与流的来历

**匹配问题**来自指派与配对：把任务分派给机器、把学生分派到宿舍、把器官捐献者与受捐者配对。抽象地说，给定图 $G=(V,E)$，我们要选出尽可能多的互不相邻的边——每条边代表一对"配对成功"的对象。

**最大流问题**来自运输与通信网络：边有容量上限（公路的车流量、管道的吞吐量），问从源点 $s$ 到汇点 $t$ 单位时间最多能输送多少。它的现代形式由 Ford 与 Fulkerson 在 1950 年代系统建立，他们同时证明了著名的 max-flow min-cut 定理（1956）：最大流的值等于最小割的容量。这一定理既是算法终止的判据，也是最优性的证书，后文会反复用到。

两个问题紧密相连：二分图匹配可以写成单位容量的最大流（见第 5 节），而流算法的分层思想（Dinic 的 blocking flow）与匹配算法（Hopcroft–Karp）共享同一套"分层图 + 批量增广"的技术。

### 经典算法能做什么，瓶颈在哪

经典算法经过半个世纪的发展已经非常成熟：

- **二分图匹配**：Hopcroft–Karp 算法（1973）达到 $O(m\sqrt{n})$，其"按最短增广路长度分阶段、每阶段批量增广"的思想至今仍是基础；
- **一般图匹配**：Edmonds 的 blossom 算法（1965）第一个给出多项式时间解法，通过收缩奇环处理非二分结构；
- **最大流**：从 Ford–Fulkerson 的增广路方法出发，经 Edmonds–Karp、Dinic 等改进达到强多项式时间；对整数容量还有 capacity scaling 技术。

共同的瓶颈在于：**每一轮增广都包含一次或多次对图的扫描**（BFS/DFS 或沿邻接表找下一条可用边），单次扫描的代价是 $\Omega(m)$ 级别的，而轮数可以多达 $\Theta(\sqrt{n})$（匹配）或 $\Theta(nU)$（逐单位增广的流）。总代价 = 轮数 × 每轮扫描代价，量子加速的机会正藏在这个乘积的第二项里。

### 量子算法的切入点与边界

量子算法对这类问题的加速遵循一个固定模式：

1. 经典框架不动——增广路、分层、blossom、残余网络、割证书全部保留；
2. 框架内部的"搜索步骤"换成量子搜索——例如"当前顶点是否还有未检查的可用邻边""哪条增广路最短"，用 Grover 搜索或量子最小值查找获得平方根级加速；
3. 因为子程序有 bounded error，需要在每个量子调用上做错误放大，最后再用经典的证书验证兜底（见第 7 节）。

边界的声明同样重要：**量子查询的减少不能删除组合结构的正确性证明。** blossom 的收缩与展开、路径的提升、匹配的更新，仍然按经典算法维护（用可逆的或经典控制的数据结构实现）。下面各节会先建立经典理论，再说明量子加速具体插在哪里、代价如何核算。

(augmenting-path-berge)=
## 2. 匹配与增广路

本节建立匹配理论的两个基石：增广路翻转引理与 Berge 定理。整节都是经典的，但它是理解量子算法"到底在加速什么"的前提。

**定义（匹配）**。设 $G=(V,E)$ 为无向图，$n=|V|$，$m=|E|$。边集 $M\subseteq E$ 称为**匹配**，如果 $M$ 中任意两条边没有公共端点。与 $M$ 中某条边关联的顶点称为**已匹配（饱和）顶点**，其余顶点称为**自由（未匹配）顶点**。匹配的大小就是边数 $|M|$。

**定义（交错路与增广路）**。一条简单路径 $P$ 称为关于 $M$ 的**交错路（alternating path）**，如果它的边依次在

$$
E\setminus M,\ M,\ E\setminus M,\ \ldots
$$

之间交替。若交错路的**两个端点都是自由顶点**，则称之为 $M$ 的**增广路（augmenting path）**。

注意增广路的边数必为奇数：两个端点都是自由的，所以首边与尾边都属于 $E\setminus M$，而交替结构要求奇数条边才能让首尾同类。设增广路有 $2k+1$ 条边，则其中 $k$ 条属于 $M$、$k+1$ 条属于 $E\setminus M$。

**定义（对称差）**。两个集合的对称差 $A\triangle B$ 是"恰属其一"的元素全体：$A\triangle B=(A\setminus B)\cup(B\setminus A)$。对边集而言，$M\triangle P$ 就是"把路径 $P$ 上边的匹配状态全部翻转"：原来在 $M$ 里的移出，原来不在的移入。

**Lemma 1（增广路翻转）**。设 $P$ 是 $M$ 的一条增广路，则

$$
M' = M\triangle P
$$

仍是匹配，且 $|M'|=|M|+1$。

**证明**。分两步：先验证 $M'$ 是匹配，再数大小。

第一步，$M'$ 是匹配，即每个顶点在 $M'$ 中至多关联一条边。按顶点位置分类讨论：

- 不在 $P$ 上的顶点：关联的 $M$ 边没有被动过，至多与原来一样，仍至多一条；
- $P$ 的内部顶点 $v$：$v$ 在 $P$ 上恰好关联两条路径边，由交错性这两条边一条属于 $M$、一条属于 $E\setminus M$。翻转之后，属于 $M$ 的那条被移出、不属于的那条被移入，$v$ 在 $M'$ 中仍然恰好关联一条边；
- $P$ 的端点 $u$：$u$ 是自由顶点，原来在 $M$ 中关联零条边；$P$ 在 $u$ 处只有一条路径边（首边或尾边），且它属于 $E\setminus M$，翻转后被移入。所以 $u$ 在 $M'$ 中恰好关联一条边。

三类顶点都不违反匹配约束，故 $M'$ 是匹配。

第二步，计数。$P$ 有 $2k+1$ 条边：$k$ 条在 $M$ 中、$k+1$ 条不在。对称差把前者移出、后者移入，因此

$$
|M'| = |M| - k + (k+1) = |M|+1.
$$

Q.E.D.

**Theorem 2（Berge 定理，1957）**。$M$ 是**最大基数匹配**当且仅当 $G$ 中不存在关于 $M$ 的增广路。

**证明**。两个方向。

（$\Rightarrow$）若存在增广路 $P$，由 Lemma 1，$M\triangle P$ 是严格更大的匹配，与 $M$ 最大矛盾。

（$\Leftarrow$）逆否命题：若 $M$ 不是最大的，要证存在增广路。取一个严格更大的匹配 $M'$（$|M'|>|M|$），考察对称差 $H=M\triangle M'$。每个顶点在 $M$ 中至多关联一条边、在 $M'$ 中也至多关联一条，所以每个顶点在 $H$ 中的度数至多为 $2$。度数不超过 $2$ 的图，其连通分量只有三种：孤立点、简单路径、简单环。逐类分析：

- $H$ 中的环必然是交错的（环上的边轮流来自 $M$ 与 $M'$，因为同一匹配的两条边不能相邻），故环长为偶数，$M$ 边与 $M'$ 边各占一半；
- $H$ 中的路径也是交错的。若路径边数为偶数，则两类边各占一半；若为奇数，则必有一类边多一条——具体地，首边和尾边同属一类，该类多一条。

现在计数：$|M'|>|M|$ 意味着 $H$ 中 $M'$ 边的总数多于 $M$ 边。环和偶长路径贡献相等，所以必存在一条奇长路径，其 $M'$ 边比 $M$ 边多一条。这条路径的首边、尾边都属于 $M'$，于是它的两个端点都不被 $M$ 饱和（否则端点还会关联一条 $M$ 边，矛盾——那条边也该在 $H$ 里，路径就延长下去了）。按定义，这正是关于 $M$ 的一条增广路。Q.E.D.

Berge 定理把整个匹配理论压缩成一句话：**找最大匹配 = 反复找增广路并翻转，直到找不到为止。** 算法的全部技术内容都在"如何高效地找"。量子算法加速的正是这一步，而定理本身不变。

**Maximum 与 maximal 的区分**。这里"最大（maximum）"不是"极大（maximal）"：maximal 只表示"再单独加入任何一条边都会冲突"，这样的匹配可能远小于最优。一个具体例子：取四个顶点排成一条路 $a-b-c-d$（三条边），$M=\{\,b\text{-}c\,\}$ 是 maximal 的（$a\text{-}b$ 与 $c\text{-}d$ 都与它冲突），但最大匹配是 $\{\,a\text{-}b,\ c\text{-}d\,\}$，大小为 $2$。检查 Berge 定理的判据：$a-b-c-d$ 本身就是关于 $\{\,b\text{-}c\,\}$ 的增广路（首边 $a\text{-}b\notin M$，端点 $a,d$ 自由），所以 $\{\,b\text{-}c\,\}$ 确实不是最大。Zoo 条目与早期摘要偶有措辞混用，需要留心：所有算法的目标都是 maximum matching。

## 3. 二分图分层增广与量子加速

本节设 $G=(L\cup R,E)$ 为二分图。先把经典的 Hopcroft–Karp 思想讲透，再指出量子搜索插在哪个位置，最后核算复杂度。

(hopcroft-karp-phases)=
### 为什么按"最短"分阶段

朴素策略是每找到一条增广路就翻转一次。Hopcroft–Karp 的观察是：**如果每一轮都沿着当前最短的增广路批量增广，那么最短增广路的长度会单调增长**，而长度增长本身就能控制总轮数。具体地，算法按**阶段（phase）**组织，每阶段做四件事：

1. 在交错残余图（alternating residual graph，即把 $M$ 边定向为 $R\to L$、把 $E\setminus M$ 边定向为 $L\to R$ 后得到的有向图）中，从所有自由左顶点同时做 BFS，求出到每个顶点的最短交错距离，从而得到当前最短增广路的长度 $\ell$；
2. 构造**分层图（layered graph）**：只保留从第 $i$ 层走向第 $i+1$ 层的边（即 BFS 意义下的 admissible 边），其余边本阶段弃用；
3. 在分层图中用 DFS 找一个 **maximal 的、顶点互不相交的最短增广路集合**（这里确实只需要 maximal 而非 maximum，见下），把它们**同时翻转**——顶点不相交保证了翻转互不干扰，可以一次性全部执行；
4. 进入下一阶段。

**Lemma 3（阶段引理）**。每执行一个阶段，最短增广路的长度严格增加（至少增加 $2$）。

**证明（思路）**。设本阶段最短增广路长为 $\ell$。阶段结束时，所有长度不超过 $\ell$ 的增广路都已消失：顶点不相交的那批路被翻转后不再交错；其余长 $\ell$ 的路必与某条被翻转的路共享顶点，而共享顶点处的边状态已被改变，破坏了交错性。于是下一阶段的增广路 $P'$ 必然用到某条"被翻转过的边"。在分层图里，原先的 admissible 边从第 $i$ 层指向第 $i+1$ 层；翻转后它的方向反过来，从第 $i+1$ 层指回第 $i$ 层。$P'$ 每走一条这样的"回退边"，就要额外花至少两步才能补回损失的层数，因此 $|P'|\ge \ell+2$（增广路长度必为奇数，所以严格增长至少是 $2$）。Q.E.D.

**Corollary 4（阶段数上界）**。Hopcroft–Karp 的阶段数为 $O(\sqrt{n})$。

**证明**。设 $M^*$ 是最大匹配，考察 $M\triangle M^*$。由 Berge 定理证明中的分析，它的分量是顶点互不相交的交错路径与偶环，其中"关于 $M$ 的增广路"恰好有 $|M^*|-|M|$ 条，而且这些路**顶点互不相交**（每个顶点至多属于一个分量）。若当前最短增广路长度超过 $2\sqrt{n}$，则每条这样的路至少包含 $\sqrt{n}$ 个顶点；路之间顶点不相交，所以路数至多为 $n/\sqrt{n}=\sqrt{n}$，即至多再增广 $\sqrt{n}$ 次就到 $M^*$。由 Lemma 3，每个阶段最短长度至少加 $2$，故至多 $O(\sqrt{n})$ 个阶段后最短长度超过 $2\sqrt{n}$；此后至多再 $O(\sqrt{n})$ 个阶段收尾。总阶段数 $O(\sqrt{n})$。Q.E.D.

每个阶段经典地用 $O(m)$ 时间完成（一次 BFS 加若干次 DFS），于是经典总代价为

$$
O(m\sqrt{n}).
$$

这就是"轮数 × 每轮扫描代价"结构的来源：$O(\sqrt{n})$ 轮，每轮 $\Omega(m)$ 的邻接扫描。

(quantum-search-insertion)=
### 量子搜索插在哪里

量子版本保持上述分层增广框架不变，把框架内部的**邻接扫描**换成量子搜索。每阶段反复需要回答的原始问题是：

> 当前顶点 $v$ 是否还有一条未检查的 admissible 邻边？若有，找出一条（或找出最短方向上的那一条）。

这是一个标准的无结构搜索/最小值查找问题：在 $v$ 的邻接表中搜索满足谓词"admissible 且未被删除"的边。对度数规模为 $d$ 的列表，经典扫描最坏 $\Theta(d)$，Grover 搜索为 $O(\sqrt{d})$，量子最小值查找（Dürr–Høyer 型）同样给出平方根加速。把它嵌回 Hopcroft–Karp 的 BFS/DFS 骨架，每次"找下一条可用边"都获得二次加速。

有一个实现细节直接影响复杂度，值得单独强调：**已检查失败的邻接区间要缓存或删除**。原因很朴素：Grover 搜索一个空列表也要花 $\Theta(\sqrt{d})$ 次查询（搜索算法必须扫过整个叠加才能确认"无解"）。如果同一个顶点的邻接表在失败后被原样保留，下一阶段还会再付一次"确认为空"的费用，而这一步没有任何进展。把失败区间从数据结构中物理删去（或打标记），每条边一生只被"付费"常数次，摊还分析才成立。分层结构、路径删除和匹配更新则用可逆的或经典控制的数据结构实现——它们不参与量子干涉，只负责给搜索预言机提供干净的查询接口。

### 复杂度核算

Ambainis–Špalek 的结果为

$$
O\!\left(n\sqrt{m+n}\,\log n\right)
$$

时间。对三个因子做定性解读（精确的摊还分析见原论文）：

- $n$：匹配大小至多为 $n/2$，增广的总轮数（按顶点计的轮次）由 $n$ 控制；
- $\sqrt{m+n}$：对"尚未删除的邻接边全集"做量子搜索的平方根因子——经典框架中为扫描邻接表付出的线性代价 $O(m+n)$，在量子搜索下开平方；
- $\log n$：把每个量子搜索子程序的错误率压到逆多项式所需的振幅放大/重复开销（见第 7 节）。

按参数区域化简：当 $m\gg n$（稠密图）时 $\sqrt{m+n}\approx\sqrt{m}$，主项约为

$$
O\!\left(n\sqrt{m}\,\log n\right);
$$

当 $m=O(n)$（稀疏图）时 $\sqrt{m+n}=O(\sqrt{n})$，界约为

$$
O\!\left(n^{3/2}\log n\right).
$$

与经典的 $O(m\sqrt{n})$ 对比：稠密区（如 $m=\Theta(n^2)$）经典为 $O(n^{5/2})$、量子约为 $O(n^2\log n)$，量子占优；稀疏区两者同为约 $n^{3/2}$ 量级，量子还多一个对数因子。**保留条款**：该界是早期量子增广框架的结果，并非声称在所有现代参数区间胜过最佳经典匹配算法；评估任何"量子优势"时都必须先指明 $n,m$ 的区域，再与同区域的最佳经典算法比较。

(blossom-contraction)=
## 4. 非二分图与 blossom

二分图之外的障碍是**奇环**。本节解释奇环为什么让简单的交错 BFS 失效、Edmonds 如何用 blossom 收缩修复它，以及量子搜索如何与这套动态组合结构共存。

### 奇环为什么破坏交错 BFS

在二分图中，BFS 层数的奇偶性与左右两部天然对齐：从自由左顶点出发，偶数层是左顶点、奇数层是右顶点，一条边不可能连接同层顶点，所以"我第一次到达 $v$ 时的交错方式"是唯一的。一般图中这不再成立。考虑一个三角形 $a-b-c-a$，设 $a\text{-}b$ 是匹配边、$b\text{-}c$ 与 $c\text{-}a$ 不是。从某个自由顶点经非匹配边到达 $a$ 后，交错 BFS 可以走 $a\to b$（匹配边）再走 $b\to c$（非匹配边）到达 $c$；但也可以直接走 $a\to c$（非匹配边）到达 $c$。同一个顶点 $c$ 以**两种不同的交错奇偶性**被到达——朴素 BFS 只允许每个顶点入队一次，无论保留哪种到达方式，都可能漏掉真正的增广路，或者把绕奇环一圈的"假路"当成增广路（路径要求顶点不重复，绕环回到已访问顶点的走法不是合法路径）。

### Edmonds 的 blossom 收缩

Edmonds（1965）的解决方案：当 BFS 发现一个奇环，其上的边按交错方式排列、且环可以通过两条不同奇偶性的方式从同一"花蒂"顶点到达时（这样的结构称为一朵**花（flower）**：一段茎（stem）加一个奇环花托（blossom）），把整个奇环**收缩（shrink）成一个超级顶点**，在收缩后的图中继续寻找增广路；找到后再把超级顶点**展开（expand）**，把收缩图中的路径**提升（lift）**回原图——奇环上两种方向的交错路径总有一种能接上茎的奇偶性，所以提升总是可行的。blossom 收缩的正确性（收缩图有增广路当且仅当原图有）是匹配理论中最精巧的组合论证之一，它保证这个过程可以递归进行，最终给出多项式时间算法。

### 量子版本的成本

量子算法必须让邻接搜索适应**动态的 blossom 结构与多层标签**：超级顶点在搜索过程中不断被创建和展开，每次"这条边是否 admissible"的谓词求值都要先查询当前的收缩状态。结果是搜索的每次调用更贵，且数据结构更新更频繁。Ambainis–Špalek 给出的一般图匹配上界为

$$
O\!\left(n^2\left(\sqrt{m/n}+\log n\right)\log n\right).
$$

逐项解读：外层 $n^2$ 来自增广轮数与每轮 blossom/森林状态的维护代价；$\sqrt{m/n}$ 项来自在大量 blossom/森林状态中对边做量子搜索（摊还到每个顶点的邻接规模约为 $m/n$，量子搜索开平方）；后一个 $\log n$ 项处理数据结构与分阶段放大的开销。按区域看：稠密图 $m=\Theta(n^2)$ 时 $\sqrt{m/n}=\sqrt{n}$，主项约 $n^{5/2}\log n$；稀疏图 $m=O(n)$ 时首项约 $n^2\log^2 n$。

**保留条款**（与二分图情形同样重要）：量子查询的减少不能删除 blossom 的正确性证明。收缩、base 顶点（花蒂）的维护和路径的提升仍然完全按经典算法执行；量子加速只作用于"找边"这一步，组合结构的每一步演化都要付出相应的数据结构代价，这正是外层 $n^2$ 因子降不下来的原因。

(residual-network-min-cut)=
## 5. 从匹配到残余网络

现在转向最大流。本节给出残余网络、增广与割证书的完整理论，并把二分匹配归约为单位容量流。

### 定义

**定义（网络与流）**。一个**网络**是有向图 $(V,E)$，带源点 $s\in V$、汇点 $t\in V$ 和整数容量

$$
0\le c_e\le U,\qquad e\in E.
$$

**流（flow）**是边上的整数值 $f_e$，满足容量约束 $0\le f_e\le c_e$ 与流守恒：对每个 $v\ne s,t$，

$$
\sum_{e\in\delta^-(v)}f_e=\sum_{e\in\delta^+(v)}f_e,
$$

其中 $\delta^-(v)$、$\delta^+(v)$ 分别表示进入、离开 $v$ 的边集。流的**值**定义为源点的净流出

$$
|f|=\sum_{e\in\delta^+(s)}f_e-\sum_{e\in\delta^-(s)}f_e.
$$

**定义（残余容量与残余图）**。当前流 $f$ 下，边 $e=(u,v)$ 有两个方向的**残余容量（residual capacity）**：

- 正向 $c_f(e)=c_e-f_e$：这条边还能再多推多少；
- 反向 $c_f(\bar e)=f_e$：已经推过去的流还能撤回多少（撤回等价于沿反方向推流）。

**残余图（residual graph）**$G_f$ 由所有残余容量严格为正的正向边与反向边组成。注意反向边是残余网络的灵魂：它允许后来的增广"撤销"先前错误的决定，这正是 Ford–Fulkerson 方法能找到最优解的原因。

### 增广引理

只要残余图中存在 $s$–$t$ 路径 $P$，就可以沿它增广。增广量取路径的**瓶颈（bottleneck）**

$$
\Delta=\min_{e\in P}c_f(e),
$$

即沿途最紧的那条边的残余容量；沿正向边加 $\Delta$、沿反向边减 $\Delta$（等价于在反向边上正向加 $\Delta$）。

**Lemma 5（增广保持合法性）**。增广之后得到的 $f'$ 仍是合法流，且 $|f'|=|f|+\Delta$。

**证明**。逐条验证约束。容量约束：正向边 $f_e'=f_e+\Delta\le f_e+c_f(e)=c_e$；反向边 $f_e'=f_e-\Delta\ge f_e-c_f(\bar e)=0$。流守恒：$P$ 的内部顶点 $v$ 被路径一进一出各经过一次，流入侧与流出侧同时加 $\Delta$（若路径经反向边进出，则对应边减 $\Delta$，效果相同），两边的增量抵消，守恒式不变。流值：路径离开 $s$ 的第一条边使 $s$ 的净流出增加 $\Delta$，故 $|f'|=|f|+\Delta$。Q.E.D.

### 割与最优性证书

**定义（割）**。一个 $s$–$t$ **割（cut）**是把顶点集分成 $S\sqcup\bar S$ 且 $s\in S$、$t\in\bar S$ 的划分，其容量为跨过割的正向边容量之和

$$
c(S,\bar S)=\sum_{\substack{e=(u,v)\\u\in S,\ v\in\bar S}}c_e.
$$

**Lemma 6（弱对偶）**。对任意流 $f$ 与任意割 $(S,\bar S)$，$|f|\le c(S,\bar S)$。

**证明**。把流守恒式对所有 $v\in S\setminus\{s\}$ 求和并加进 $|f|$ 的定义式：

$$
|f|=\sum_{v\in S}\left(\sum_{e\in\delta^+(v)}f_e-\sum_{e\in\delta^-(v)}f_e\right),
$$

因为 $v\ne s$ 的项由流守恒都为零，加进来不改变值。现在按边分类看这个双重求和：两个端点都在 $S$ 内的边 $e=(u,w)$，在 $v=u$ 处作为出边贡献 $+f_e$、在 $v=w$ 处作为入边贡献 $-f_e$，恰好抵消；从 $S$ 指向 $\bar S$ 的边只贡献 $+f_e$；从 $\bar S$ 指向 $S$ 的边只贡献 $-f_e$。于是

$$
|f|=\sum_{e:\,S\to\bar S}f_e-\sum_{e:\,\bar S\to S}f_e\le\sum_{e:\,S\to\bar S}c_e=c(S,\bar S),
$$

最后一步用了 $0\le f_e\le c_e$。Q.E.D.

**Theorem 7（max-flow min-cut，Ford–Fulkerson 1956）**。最大流的值等于最小割的容量。并且当残余图中不存在 $s$–$t$ 路径时，可达集立即给出达到等号的割。

**证明（可达集构造）**。设 $G_f$ 中不存在 $s$–$t$ 路径，令 $S$ 为 $s$ 在 $G_f$ 中的可达顶点集（$t\notin S$）。考察任意一条从 $S$ 指向 $\bar S$ 的原图边 $e$：若 $f_e<c_e$，则正向残余边存在，其终点应该可达，矛盾，故 $f_e=c_e$（饱和）。同理，任意从 $\bar S$ 指向 $S$ 的边必有 $f_e=0$（否则反向残余边存在）。代回 Lemma 6 证明中的等式：

$$
|f|=\sum_{e:\,S\to\bar S}c_e-\sum_{e:\,\bar S\to S}0=c(S,\bar S).
$$

由弱对偶，任何流的值都不超过 $c(S,\bar S)$，而 $f$ 达到了它，所以 $f$ 最大、这个割最小。Q.E.D.

这个证明的方式很重要：**最优性不是被"声明"的，而是由一个可检查的割证书确认的。** 第 7 节会看到，这正是量子算法可以容忍内部随机性的原因。

### 二分匹配归约为单位容量流

给定二分图 $G=(L\cup R,E)$，构造网络：加入超级源点 $s$ 与超级汇点 $t$；对每个 $u\in L$ 加边 $s\to u$；把 $E$ 中每条边定向为 $L\to R$；对每个 $w\in R$ 加边 $w\to t$；**所有边容量置为 $1$**。

**命题**。该网络中最大（整数）流的值等于 $G$ 的最大匹配大小。

**证明（对应关系）**。一方面，大小为 $k$ 的匹配 $M$ 给出值为 $k$ 的流：对每条匹配边 $u\to w$（$u\in L,w\in R$），沿 $s\to u\to w\to t$ 推 $1$ 单位流。匹配边互不相邻，所以每条 $s\to u$ 与 $w\to t$ 至多被用一次，容量约束成立；中间顶点一进一出，流守恒成立。另一方面，值为 $k$ 的**整数**流给出大小为 $k$ 的匹配：所有容量为 $1$，所以每条边的流值是 $0$ 或 $1$；取所有流值为 $1$ 的 $L\to R$ 边，由 $s\to u$ 的容量约束，每个 $u\in L$ 至多出流 $1$，由 $w\to t$ 的容量约束，每个 $w\in R$ 至多入流 $1$，故这些边两两不相邻，构成大小为 $k$ 的匹配。两个方向的构造互为逆，故最优值相等。Q.E.D.

整数性不是额外的假设：整数容量下沿瓶颈增广保持流值为整数（Lemma 5 中 $\Delta$ 是整数），从零流出发得到的最大流自动是整数流。因此**匹配子程序也是流算法的特殊尺度**（$U=1$ 的特殊情形），流算法在 $U=1$ 区域的行为直接反映匹配算法的行为。

(capacity-scaling-bounds)=
## 6. 量子残余搜索的两种平衡

本节进入最大流的量子算法。核心机制是 capacity scaling，核心结论是依参数区域取两条上界 $T_1,T_2$ 的较小者。

### Capacity scaling

整数容量允许**容量缩放（capacity scaling）**：选一个阈值 $\Delta$（初始取不超过 $U$ 的最大 $2$ 的幂），当前阶段只看残余容量至少为 $\Delta$ 的边构成的子图，在其中增广到没有 $s$–$t$ 路径为止，然后把阈值减半 $\Delta\leftarrow\Delta/2$，重复直到 $\Delta<1$。直觉是"先走粗管道，再走细管道"：大阈值时可选的边少、但每次增广推的流多；阈值逐级减半，保证不会遗漏细小但关键的边（如第 8 节小例子中的边 $a\to b$）。每级需要：

- 量子搜索 admissible 的残余边（残余容量 $\ge\Delta$ 的边）；
- 在该子图中找增广路或 blocking flow；
- 更新受影响的边（残余容量变化）并删除饱和边；
- 用割或剩余 deficit（当前流值与上界的差距）控制每级的增广次数与阶段数。

### 两条算法路线

原论文在这个框架下发展了两条路线，偏向不同的内部权衡：

- **路线一（批量 blocking flow）**：类似 Dinic 的思想，用分层结构限制顶点的重访次数，在每一层内用量子扫描寻找 admissible 边，一批一批地推流。批量减少了"找路"的次数，但每批要维护分层结构，批大小成为需要优化的内部参数；
- **路线二（逐次较大增广）**：每次找一条尽可能大的增广路。容量整数性保证每次增广至少推 $1$ 单位流，而最大流值本身有上界

$$
|f^*|\le c(\{s\},V\setminus\{s\})\le (n-1)\,U\le nU
$$

（源点至多有 $n-1$ 条出边，每条容量至多为 $U$），所以**总增广次数由 $nU$ 控制**；量子搜索负责在每条路径的构造中寻找候选边。

### 两条上界与参数平衡

对内部容量阈值/批大小做优化后，得到两项上界：

$$
T_1=O\!\left(n^{7/6}\sqrt{m}\,U^{1/3}\log n\right),
$$

$$
T_2=O\!\left(\sqrt{nU}\,m\log n\right).
$$

最终复杂度取两者较小值。逐项解读因子来源：

- $T_1$ 中 $\sqrt{m}$ 是对残余边全集做量子搜索的平方根因子；$n^{7/6}$ 与 $U^{1/3}$ 来自路线一中对批大小/阈值的平衡；
- $T_2$ 中 $\sqrt{nU}$ 是路线二"增广次数上界 $nU$"经 Grover 加速后的平方根；$m$ 是每轮在残余网络中扫描与更新边的线性代价；两条路线的 $\log n$ 都来自错误放大。

**为什么会有 $1/3$ 这样的分数指数？** 这类指数的典型来源是一个两参数平衡。设某内部参数 $r$（批大小）使代价的两项分别为 $A\,r$（随 $r$ 增大而增，例如批内维护代价）与 $B/r^2$（随 $r$ 增大而减，例如批次数量），则总代价 $C(r)=Ar+B/r^2$ 的最小值在对 $r$ 求导处取得：

$$
\frac{dC}{dr}=A-\frac{2B}{r^3}=0\quad\Longrightarrow\quad r^*=\left(\frac{2B}{A}\right)^{1/3},
$$

代回得 $C(r^*)\propto A^{2/3}B^{1/3}$。当被平衡的项 $B$ 携带容量因子 $U$ 时，最优代价就呈现 $U^{1/3}$ 型的立方根依赖。这里的具体 $A,B$ 属于原论文的摊还分析，但$1/3$、$7/6$ 这类指数的出现机制就是上述平衡。

**参数区域比较**（正文示范两个，其余留作习题）。固定 $U=1$，比较

$$
T_1\le T_2\iff n^{7/6}\sqrt{m}\le \sqrt{n}\,m\iff n^{2/3}\le m,
$$

其中第二步两边同除 $\sqrt{n}\,\sqrt{m}$。所以 $U=1$ 时：$m\ge n^{2/3}$ 取 $T_1$，更稀疏时取 $T_2$。再如 $m=\Theta(n^2)$、$U=1$：$T_1=n^{7/6}\cdot n=n^{13/6}$，$T_2=n^{1/2}\cdot n^2=n^{5/2}$，而 $\frac{13}{6}<\frac{5}{2}$（即 $\frac{26}{12}<\frac{30}{12}$），故取 $T_1$，约为 $O(n^{13/6}\log n)$。

**大 $U$ 的保留条款**。原论文重点陈述 $U\le n^{1/4}$ 等容量区域。若 $U$ 很大，需要注意：容量的二进制编码长度只有 $\log U$ 比特，因此任何关于 $U$ 的**多项式**依赖（如 $T_1$ 中的 $U^{1/3}$、$T_2$ 中的 $\sqrt{U}$）在严格的输入长度意义下都是伪多项式的，可能失去相对于强多项式经典算法或其他 scaling 方案的优势。实际使用时应按所在参数区域与其他 scaling/经典算法比较后再选择，而不是直接套用两条上界。

(classical-certificate-example)=
## 7. 正确性证书仍是经典的

量子搜索子程序是 bounded error 的：单次调用可能以小概率失败或返回错误的边。为什么整个算法的输出仍然可信？答案是**输出本身可以被经典地、确定性地验证**，验证不依赖对量子随机性的任何信任。

流的合法性可以在 $O(m)$ 时间内逐边、逐顶点检查：

$$
0\le f_e\le c_e\quad(\forall e),\qquad
\sum_{e\in\delta^-(v)}f_e=\sum_{e\in\delta^+(v)}f_e\quad(\forall v\ne s,t).
$$

最优性则由割证书确认：算法在结束时同时输出残余不可达形成的割 $S$（即 $s$ 在最终残余图中的可达集），验证者重新计算

$$
|f|=c(S,\bar S)
$$

是否成立。若成立，由 max-flow min-cut（Theorem 7）立即得到 $f$ 是最大流——这是一个**零错误的最优性证书**：无论量子子程序内部出了什么错，只要最终通过验证，答案就一定对。

剩下的问题只是效率：要让"通过验证"这件事以高概率发生。标准的做法是在每个量子搜索子程序上做错误放大——把失败率从常数压到逆多项式 $1/\mathrm{poly}(n)$，代价是每个调用多一个 $O(\log n)$ 因子（这就是两条上界中 $\log n$ 的来源之一）；全部调用至多多项式次，由 union bound，整体失败概率仍是逆多项式的小量。即使某次运行真的失败，末端的经典验证也能发现（证书对不上），此时重跑或修补即可——**错误永远不会伪装成正确答案输出**。匹配情形同理：输出匹配后可经典检查它确为匹配，并（在二分情形通过交错残余图中的不可达割、一般情形通过 blossom 算法的对偶证书）确认最大性。

## 8. 小例子：一个四顶点网络的完整计算

考虑网络（边上标注的是容量）

$$
s\to a:3,\qquad s\to b:2,\qquad a\to t:2,\qquad b\to t:3,\qquad a\to b:1.
$$

从零流出发，用 Ford–Fulkerson 增广，并把每一步的残余容量与瓶颈完整算出来。

**第一次增广**：取路径 $P_1=s\to a\to t$。瓶颈

$$
\Delta_1=\min\{c_f(s,a),\ c_f(a,t)\}=\min\{3,2\}=2.
$$

沿路径加 $2$：$f_{sa}=2$，$f_{at}=2$。此时 $|f|=2$。关键残余容量：$s\to a$ 正向余 $3-2=1$；$a\to t$ 正向余 $2-2=0$（**饱和**，同时产生反向残余边 $t\to a:2$）。

**第二次增广**：取路径 $P_2=s\to b\to t$。瓶颈

$$
\Delta_2=\min\{c_f(s,b),\ c_f(b,t)\}=\min\{2,3\}=2.
$$

沿路径加 $2$：$f_{sb}=2$，$f_{bt}=2$。此时 $|f|=4$。关键残余容量：$s\to b$ 正向余 $2-2=0$（饱和，反向 $b\to s:2$）；$b\to t$ 正向余 $3-2=1$。

**第三次增广**：此时从 $s$ 出发只有 $s\to a$ 还有正向残余（余 $1$）；从 $a$ 出发，$a\to t$ 已饱和，但 $a\to b:1$ 尚未使用；从 $b$ 出发，$b\to t$ 余 $1$。于是存在路径 $P_3=s\to a\to b\to t$，瓶颈

$$
\Delta_3=\min\{1,\ 1,\ 1\}=1.
$$

沿路径加 $1$：$f_{sa}=3$，$f_{ab}=1$，$f_{bt}=3$。总流

$$
|f|=f_{sa}+f_{sb}=3+2=5.
$$

**终止与证书**：现在 $s\to a$ 与 $s\to b$ 都饱和，残余图中从 $s$ 出发没有任何出边，可达集为 $S=\{s\}$，自然不存在 $s$–$t$ 路径，算法终止。检查割 $(\{s\},\{a,b,t\})$：

$$
c(S,\bar S)=c_{sa}+c_{sb}=3+2=5=|f|,
$$

由 Theorem 7，流值 $5$ 就是最大流。顺手验证流守恒：顶点 $a$ 流入 $f_{sa}=3$，流出 $f_{at}+f_{ab}=2+1=3$；顶点 $b$ 流入 $f_{sb}+f_{ab}=2+1=3$，流出 $f_{bt}=3$。全部吻合。

**用 capacity scaling 重看同一例子**。取初始阈值 $\Delta=2$：残余容量 $\ge 2$ 的 admissible 边为 $s\to a:3$、$s\to b:2$、$a\to t:2$、$b\to t:3$，注意 $a\to b:1$ 在这一级**不可达**。在这一级恰好发生前两次增广（各推 $2$）；此后该级无 $s$–$t$ 路径，阈值减半到 $\Delta=1$，边 $a\to b$ 变为 admissible，发生第三次增广。"先粗后细"的机制与上文的逐条计算完全一致。

量子算法在这个例子里加速的是什么？只是**在大的残余图中寻找这些 admissible 边/路径**的那一步搜索——本例图太小，搜索加速无从体现；增广量 $\Delta$ 的计算、残余容量的更新、割证书 $c(\{s\},\bar S)=5$ 的证明，与经典算法完全相同。

## 9. 小结

- 最大匹配由"不存在增广路"刻画（Berge 定理）；二分图按最短增广路长度分阶段、批量翻转，阶段数 $O(\sqrt{n})$。
- 一般图还需 Edmonds 的 blossom 收缩处理奇环；量子搜索不能绕开这套组合结构，因此一般图的上界多出一个 $n$ 因子。
- 最大流在残余网络上增广；残余图无 $s$–$t$ 路径时，可达集给出等号成立的割（max-flow min-cut）。整数容量与 capacity scaling 控制阶段数。
- 量子算法加速的是框架内部的邻接扫描与路径搜索：匹配 $O(n\sqrt{m+n}\log n)$、一般图匹配 $O(n^2(\sqrt{m/n}+\log n)\log n)$、流的两条路线 $T_1=O(n^{7/6}\sqrt{m}\,U^{1/3}\log n)$ 与 $T_2=O(\sqrt{nU}\,m\log n)$。应按 $n,m,U$ 的区域取最小，并与同区域最佳经典算法比较；$U$ 很大时多项式 $U$ 依赖是伪多项式的，可能失去优势。
- 量子子程序是 bounded error 的，但流合法性、匹配合法性与割/对偶证书都可经典验证，最优性结论零错误。

## 练习题

**练习 1【问题背景与量子加速模式】**（→ [第 1 节](#background-quantum-entry)）

1. 基础：分别用一句话写出匹配问题与最大流问题的目标，并各举一个文中提到的应用场景。
2. 进阶：把经典增广框架的总代价分解为"轮数 × 每轮扫描代价"，解释量子搜索为什么只能作用于乘积的第二项，并举出正文中一个必须保持经典执行的组合组件（如 blossom 收缩、增广量计算、割证书）。

> 提示：Grover 加速的是子程序内部的邻接扫描与路径搜索，增广轮数由组合结构决定。

**练习 2【增广路与 Berge 定理】**（→ [第 2 节](#augmenting-path-berge)）

1. 基础：写出交错路与增广路的定义，并解释为什么增广路的边数必为奇数。
2. 进阶：不引用 Lemma 1 的计数结论，直接从顶点度数的分类讨论出发，证明沿增广路翻转使匹配大小恰好增加 $1$；并说明为什么"交错但端点已匹配"的路径不能这样翻转。
3. 进阶：构造一个 $6$ 个顶点的图与一个 maximal 匹配 $M$，使得 $|M|$ 严格小于最大匹配大小；写出 $M\triangle M^*$ 的各连通分量，并指出其中的增广路。

> 提示：一条 $4$ 顶点的路加一条独立边即可；再用 maximality 逐条排除可加入的边。

**练习 3【Hopcroft–Karp 分层增广】**（→ [为什么按"最短"分阶段](#hopcroft-karp-phases)）

1. 基础：列出 Hopcroft–Karp 单个阶段的四个步骤，并解释为什么被同时翻转的增广路集合只需 maximal、但必须顶点互不相交。
2. 进阶：证明 Corollary 4 的关键一步：若当前最短增广路长度超过 $2\sqrt{n}$，则 $|M^*|-|M|\le\sqrt{n}$；再结合 Lemma 3 推出总阶段数为 $O(\sqrt{n})$。

> 提示：考察 $M\triangle M^*$ 的分量——这些增广路顶点互不相交，每条至少含 $\sqrt{n}$ 个顶点。

**练习 4【量子搜索的插入点与匹配复杂度】**（→ [量子搜索插在哪里](#quantum-search-insertion)）

1. 基础：写出量子版本每个阶段反复要回答的原始搜索问题，并比较度数为 $d$ 的邻接表上经典扫描与 Grover 搜索的最坏情况代价。
2. 进阶：解释已检查失败的邻接区间为什么必须缓存或删除（包括"Grover 确认一个空列表也要付费"这一点），并在 $m=\Theta(n^2)$ 与 $m=O(n)$ 两个区域分别比较 $O(n\sqrt{m+n}\log n)$ 与经典 $O(m\sqrt{n})$。

> 提示：稠密区代入 $\sqrt{m+n}\approx\sqrt{m}$；稀疏区两者同为 $n^{3/2}$ 量级，量子还多一个 $\log n$ 因子。

**练习 5【blossom 收缩与一般图匹配】**（→ [第 4 节](#blossom-contraction)）

1. 基础：在三角形 $a\text{-}b\text{-}c$（$a\text{-}b$ 为匹配边）上，写出从自由顶点经非匹配边到达 $a$ 之后、以两种不同交错奇偶性到达 $c$ 的走法，并说明这为什么让朴素交错 BFS 出错。
2. 进阶：解释收缩、展开、提升三个步骤各自的作用，并说明量子版本上界 $O(n^2(\sqrt{m/n}+\log n)\log n)$ 中外层 $n^2$ 因子的来源——为什么它降不下来。

> 提示：$n^2$ 来自增广轮数与每轮 blossom/森林状态的数据结构维护代价，这些更新不参与量子干涉。

**练习 6【残余网络与 max-flow min-cut】**（→ [第 5 节](#residual-network-min-cut)）

1. 基础：写出边 $e=(u,v)$ 在流 $f$ 下的正向与反向残余容量，并解释反向边为什么让算法能"撤销"先前错误的决定。
2. 进阶：证明弱对偶 $|f|\le c(S,\bar S)$：把流守恒式对 $S\setminus\{s\}$ 中的顶点求和，说明两个端点都在 $S$ 内的边为何贡献恰好抵消。
3. 进阶：把第 8 节出现过的二分结构具体化：设 $L=\{u_1,u_2\}$、$R=\{w_1,w_2\}$、边集 $E=\{u_1w_1,\,u_1w_2,\,u_2w_1\}$，画出对应的单位容量流网络，求最大流，并说明它与最大匹配的边一一对应。

> 提示：归约的证明分两个方向——匹配给流、整数流给匹配。

**练习 7【capacity scaling 与两条上界】**（→ [第 6 节](#capacity-scaling-bounds)）

1. 基础：写出 capacity scaling 的流程：阈值的初始取法、admissible 边的条件、阈值何时减半，以及"先粗后细"为什么不会遗漏细小但关键的边。
2. 进阶：对第 8 节原始网络，把初始阈值取为 $\Delta=4$ 再逐级减半，写出每一级的 admissible 边集、发生的增广以及阈值下降的时刻，与正文取 $\Delta=2$ 的过程对照。
3. 进阶：在 $m=n$ 与 $m=n^2$、$U=1$ 与 $U=n^{1/4}$ 的四种组合下，分别比较 $T_1$ 与 $T_2$ 的指数，指出每种组合应取哪一条上界（正文已示范 $U=1$ 的两个情形，完成 $U=n^{1/4}$ 的两个）。

> 提示：把 $U=n^{1/4}$ 代入两条上界后，两边同除公共的 $m$ 与 $n$ 的幂，只比较 $n$ 的指数。

**练习 8【经典证书与四顶点算例】**（→ [第 7–8 节](#classical-certificate-example)）

1. 基础：在正文的四顶点网络上复算第三次增广 $P_3=s\to a\to b\to t$ 的瓶颈与增广后的流值，并验证终止时割 $(\{s\},\{a,b,t\})$ 的容量恰等于流值。
2. 进阶：解释"错误永远不会伪装成正确答案输出"为何成立：单次量子调用的失败率如何被压到逆多项式、整体失败概率如何由 union bound 控制、最终由哪个经典检查兜底。
3. 进阶：把小例子的容量改为 $s\to a:4$、$s\to b:1$、$a\to t:2$、$b\to t:3$、$a\to b:2$，重算最大流，验证流守恒，并给出割证书证明最优。

> 提示：先沿 $s\to a\to t$ 与 $s\to b\to t$ 增广，再找经过 $a\to b$ 的路径，最后用源点处的饱和割收尾。

## 参考文献

- Zoo 编号 168：Andris Ambainis 与 Robert Špalek, [Quantum Algorithms for Matching and Network Flows](https://arxiv.org/abs/quant-ph/0508205).