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

最大匹配（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. 问题背景与量子加速模式——能写出匹配与最大流的问题定义，说明经典算法"轮数 × 每轮扫描代价"的共同瓶颈，并解释量子加速"组合框架不动、搜索步骤换 Grover"的固定模式与适用边界。

  2. 增广路与 Berge 定理——能写出交错路、增广路与对称差的定义，证明增广路翻转引理与 Berge 定理，并区分 maximum 与 maximal 匹配。

  3. Hopcroft–Karp 分层增广——能列出单个阶段的四个步骤，推导阶段引理与 \(O(\sqrt{n})\) 阶段数上界，得出 \(O(m\sqrt{n})\) 的经典复杂度。

  4. 量子搜索的插入点与匹配复杂度——能指出 Grover 搜索替换经典邻接扫描的具体位置，解释失败邻接区间必须删除的摊还原因，并解读 \(O(n\sqrt{m+n}\log n)\) 三个因子的来源与稠密、稀疏两个区域的比较结论。

  5. blossom 收缩与一般图匹配——能解释奇环为何破坏交错 BFS、Edmonds 收缩—展开—提升机制如何修复它，并说明量子版本上界为何比二分图情形多出一个 \(n\) 因子。

  6. 残余网络与 max-flow min-cut——能写出残余容量、割与瓶颈增广的定义，证明弱对偶与 max-flow min-cut 定理，并构造二分匹配到单位容量流的归约。

  7. capacity scaling 与两条上界——能解释容量缩放机制与两条算法路线，在给定参数区域计算并比较 \(T_1\)、\(T_2\) 的指数，说明 \(U^{1/3}\) 型指数的平衡来源与大 \(U\) 的伪多项式保留条款。

  8. 经典证书与四顶点算例——能在四顶点网络上完整执行 Ford–Fulkerson 增广、流守恒验证与割证书核算，并解释 bounded-error 量子子程序为何仍产生零错误的输出。

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,\ \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 的观察是：如果每一轮都沿着当前最短的增广路批量增广，那么最短增广路的长度会单调增长，而长度增长本身就能控制总轮数。具体地，算法按**阶段（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)\) 的邻接扫描。

量子搜索插在哪里

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

当前顶点 \(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,\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\) 的划分，其容量为跨过割的正向边容量之和

\[\begin{split} c(S,\bar S)=\sum_{\substack{e=(u,v)\\u\in S,\ v\in\bar S}}c_e. \end{split}\]

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^*|\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/经典算法比较后再选择，而不是直接套用两条上界。

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 节）

  1. 基础：分别用一句话写出匹配问题与最大流问题的目标，并各举一个文中提到的应用场景。

  2. 进阶：把经典增广框架的总代价分解为"轮数 × 每轮扫描代价"，解释量子搜索为什么只能作用于乘积的第二项，并举出正文中一个必须保持经典执行的组合组件（如 blossom 收缩、增广量计算、割证书）。

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

练习 2【增广路与 Berge 定理】（→ 第 2 节）

  1. 基础：写出交错路与增广路的定义，并解释为什么增广路的边数必为奇数。

  2. 进阶：不引用 Lemma 1 的计数结论，直接从顶点度数的分类讨论出发，证明沿增广路翻转使匹配大小恰好增加 \(1\)；并说明为什么"交错但端点已匹配"的路径不能这样翻转。

  3. 进阶：构造一个 \(6\) 个顶点的图与一个 maximal 匹配 \(M\)，使得 \(|M|\) 严格小于最大匹配大小；写出 \(M\triangle M^*\) 的各连通分量，并指出其中的增广路。

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

练习 3【Hopcroft–Karp 分层增广】（→ 为什么按"最短"分阶段）

  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【量子搜索的插入点与匹配复杂度】（→ 量子搜索插在哪里）

  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 节）

  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 节）

  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 节）

  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 节）

  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\) 的路径，最后用源点处的饱和割收尾。

参考文献