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

最大匹配与最大流都由“反复寻找增广结构”驱动。量子算法不会改变 Berge 定理或 max-flow min-cut，而是在 residual graph 中用 Grover/minimum finding 加速邻接扫描、最短增广路和 blocking-flow 子程序。复杂度取决于顶点数 \(n\)、边数 \(m\) 与整数容量上界 \(U\)，不同参数区域由不同算法占优。

1. 匹配与增广路

匹配 \(M\subseteq E\) 中每个顶点至多关联一条边。\(M\)-augmenting path 的边在

\[ E\setminus M, M, E\setminus M,\ldots \]

间交替，两个端点未匹配。沿路径翻转边状态

\[ M\leftarrow M\triangle P \]

使匹配大小增加 1。Berge 定理：\(M\) 为最大基数匹配当且仅当不存在增广路。

这里“maximum”不是“maximal”：maximal 只表示再加单边会冲突，可能远小于最优。Zoo/早期摘要偶有措辞混用，算法目标是最大匹配。

2. 二分图分层增广

Hopcroft--Karp 思路每阶段：

  1. 在 alternating residual graph 中 BFS 找最短增广路长度；

  2. 构造只含正确层间边的 layered graph；

  3. 找一个 maximal set 的顶点不交最短增广路并同时翻转；

  4. 最短增广路长度严格增加，所以阶段数受控。

量子版本对“当前顶点是否还有 admissible 邻边”做 Grover 搜索。已检查失败的邻接区间要缓存/删去，否则同一空列表会重复付费。分层、路径删除和匹配更新用可逆或经典控制数据结构实现。

Ambainis--Špalek 的结果为

\[ O\!\left(n\sqrt{m+n}\log n\right) \]

时间。\(m\gg n\) 时主项约 \(n\sqrt m\)；\(m=O(n)\) 时约 \(n^{3/2}\)。该界是早期量子增广框架的结果，并非声称在所有现代参数区间胜过最佳经典匹配算法。

3. 非二分图与 blossom

一般图的奇环会使简单 alternating BFS 失效；Edmonds blossom 把某些奇环收缩为超级顶点，在收缩图中寻找增广路，再展开。量子算法必须让邻接搜索适应动态 blossom 与多层标签，成本上升为

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

前项来自在大量 blossom/森林状态中搜索边，后项处理数据结构与分阶段放大。量子查询减少不能删除 blossom 正确性证明；收缩、base 顶点和路径提升仍按经典算法维护。

4. 从 matching 到 residual network

网络有源点 \(s\)、汇点 \(t\) 与整数容量

\[ 0\le c_e\le U. \]

当前流 \(f\) 的 residual capacity 为正向 \(c_e-f_e\) 和反向 \(f_e\)。只要 residual graph 有 \(s\)--\(t\) 路，沿其瓶颈

\[ \Delta=\min_{e\in P}c_f(e) \]

增广。没有路径时，可达集给出与当前流同值的 cut，证明最大。

单位容量二分网络把左--右边容量置 1，并连接超级源汇，maximum flow 值就是 maximum matching 大小。因此匹配子程序也是流算法的特殊尺度。

5. 量子 residual 搜索的两种平衡

整数容量允许 capacity scaling：只看 residual capacity 至少某阈值的边，逐级减半阈值。每级需要：

  • 量子搜索 admissible residual edge；

  • 找增广路/阻塞流；

  • 更新受影响的边并删除饱和边；

  • 用 cut/剩余 deficit 控制阶段数。

一条算法偏向批量 blocking-flow：用分层结构限制顶点重访，并在每层量子扫描边。另一条偏向逐次较大增广：容量整数性保证总增广次数由 \(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). \]

取较小者。原论文重点陈述 \(U\le n^{1/4}\) 等容量区域；若 \(U\) 很大，二进制编码长度虽只有 \(\log U\)，上述多项式 \(U\) 依赖可能失去优势，应采用其他 scaling/经典算法比较。

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

量子子程序可能有 bounded error，但输出流可经典验证：

\[ 0\le f_e\le c_e,\qquad \sum_{e\in\delta^-(v)}f_e =\sum_{e\in\delta^+(v)}f_e \]

对 \(v\ne s,t\)。若同时输出 residual 不可达形成的 cut \(S\)，并验证

\[ |f|=c(S,\bar S), \]

则由 max-flow min-cut 得到零错误最优性证书。算法可在每个量子搜索子程序上放大失败率，使整体错误逆多项式，再以证书兜底。

7. 小例子

网络

\[ s\to a:3,quad s\to b:2,quad a\to t:2,quad b\to t:3,quad a\to b:1 \]

先沿 \(s-a-t\) 增广 2，再沿 \(s-b-t\) 增广 2，总流 4；随后可沿 \(s-a-b-t\) 增广 1，总流 5。源点出边总容量也是 5，cut \(\{s\}\) 证明最优。

量子算法只加速在大 residual graph 中寻找这些 admissible 边/路径；增广量与 cut 证明完全相同。

8. 小结与习题

  • 最大匹配由不存在 augmenting path 刻画；二分图分层批量找最短增广路。

  • 一般图还需 blossom 收缩，量子搜索不能绕开组合结构。

  • 最大流在 residual network 上增广，整数容量与 scaling 控制阶段数。

  • 两种量子平衡给出依 \(n,m,U\) 不同的上界，应按参数取最小并与经典算法比较。

  1. 证明沿 augmenting path 翻转使匹配大小增加 1。

  2. 把二分 matching 写成单位容量 flow 网络。

  3. 验证小例子的流守恒与最小 cut。

  4. 分别在 \(m=n,n^2\)、\(U=1,n^{1/4}\) 时比较 \(T_1,T_2\) 指数。

参考文献