量子网络流与匹配

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

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

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

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 的收缩与展开、路径的提升、匹配的更新，仍然按经典算法维护（用可逆的或经典控制的数据结构实现）。下面各节会先建立经典理论，再说明量子加速具体插在哪里、代价如何核算。

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,\dots$$

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

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

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

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

$$M^{\prime }=M△P$$

仍是匹配，且 $|M^{\prime }|=|M|+1$。

证明。分两步：先验证 $M^{\prime }$ 是匹配，再数大小。

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

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

三类顶点都不违反匹配约束，故 $M^{\prime }$ 是匹配。

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

$$|M^{\prime }|=|M|-k+(k+1)=|M|+1.$$

Q.E.D.

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

证明。两个方向。

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

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

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

现在计数：$|M^{\prime }|>|M|$ 意味着 $H$ 中 $M^{\prime }$ 边的总数多于 $M$ 边。环和偶长路径贡献相等，所以必存在一条奇长路径，其 $M^{\prime }$ 边比 $M$ 边多一条。这条路径的首边、尾边都属于 $M^{\prime }$，于是它的两个端点都不被 $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 的观察是：如果每一轮都沿着当前最短的增广路批量增广，那么最短增广路的长度会单调增长，而长度增长本身就能控制总轮数。具体地，算法按**阶段（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^{\prime }$ 必然用到某条”被翻转过的边”。在分层图里，原先的 admissible 边从第 $i$ 层指向第 $i+1$ 层；翻转后它的方向反过来，从第 $i+1$ 层指回第 $i$ 层。$P^{\prime }$ 每走一条这样的”回退边”，就要额外花至少两步才能补回损失的层数，因此 $|P^{\prime }|\ge \ell +2$（增广路长度必为奇数，所以严格增长至少是 $2$）。Q.E.D.

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

证明。设 $M^{\ast }$ 是最大匹配，考察 $M△M^{\ast }$。由 Berge 定理证明中的分析，它的分量是顶点互不相交的交错路径与偶环，其中”关于 $M$ 的增广路”恰好有 $|M^{\ast }|-|M|$ 条，而且这些路顶点互不相交（每个顶点至多属于一个分量）。若当前最短增广路长度超过 $2\sqrt{n}$，则每条这样的路至少包含 $\sqrt{n}$ 个顶点；路之间顶点不相交，所以路数至多为 $n/\sqrt{n}=\sqrt{n}$，即至多再增广 $\sqrt{n}$ 次就到 $M^{\ast }$。由 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)$ 的邻接扫描。

量子搜索插在哪里

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

当前顶点 $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$ 的区域，再与同区域的最佳经典算法比较。

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$ 因子降不下来的原因。

5. 从匹配到残余网络

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

定义

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

$$0\le c_e\le U,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 =\underset{e\in P}{\min }{c}_f(e),$$

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

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

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

割与最优性证书

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

$$c(S,\bar{S})=\sum _{\begin{array}{c}e=(u,v)\\ u\in S,v\in \bar{S}\end{array}}{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$ 区域的行为直接反映匹配算法的行为。

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^{\ast }|\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$（批大小）使代价的两项分别为 $Ar$（随 $r$ 增大而增，例如批内维护代价）与 $B/r^2$（随 $r$ 增大而减，例如批次数量），则总代价 $C(r)=Ar+B/r^2$ 的最小值在对 $r$ 求导处取得：

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

代回得 $C(r^{\ast })\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⟺n^{7/6}\sqrt{m}\le \sqrt{n}m⟺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/经典算法比较后再选择，而不是直接套用两条上界。

7. 正确性证书仍是经典的

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

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

$$0\le f_e\le c_e(\forall e),\sum _{e\in {\delta }^{-}(v)}{f}_e=\sum _{e\in {\delta }^{+}(v)}{f}_e(\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,s\to b:2,a\to t:2,b\to t:3,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. （增广路翻转）不引用 Lemma 1 的计数结论，直接从顶点度数的分类讨论出发，证明沿增广路翻转使匹配大小恰好增加 $1$；并说明为什么”交错但端点已匹配”的路径不能这样翻转。
2. （maximum 与 maximal）构造一个 $6$ 个顶点的图与一个 maximal 匹配 $M$，使得 $|M|$ 严格小于最大匹配大小的一半；写出 $M△M^{\ast }$ 的各连通分量，并指出其中的增广路。
3. （归约）把第 8 节出现过的二分结构具体化：设 $L=\{u_1,u_2\}$、$R=\{w_1,w_2\}$、边集 $E=\{u_1{w}_1,u_1{w}_2,u_2{w}_1\}$，画出对应的单位容量流网络，求最大流，并说明它与最大匹配的边一一对应。
4. （流计算）把小例子的容量改为 $s\to a:4$、$s\to b:1$、$a\to t:2$、$b\to t:3$、$a\to b:2$，重算最大流，验证流守恒，并给出割证书证明最优。
5. （capacity scaling）对第 8 节原始网络，把初始阈值取为 $\Delta =4$ 再逐级减半，写出每一级的 admissible 边集、发生的增广以及阈值下降的时刻，与正文取 $\Delta =2$ 的过程对照。
6. （参数区域）在 $m=n$ 与 $m=n^2$、$U=1$ 与 $U=n^{1/4}$ 的四种组合下，分别比较 $T_1$ 与 $T_2$ 的指数，指出每种组合应取哪一条上界（正文已示范 $U=1$ 的两个情形，完成 $U=n^{1/4}$ 的两个）。

参考文献

• Zoo 编号 168：Andris Ambainis 与 Robert Špalek, Quantum Algorithms for Matching and Network Flows.

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch12-quantum-graphs/network-flows-matchings
• 内容遵循 CC BY-NC-SA 4.0 许可协议