# 量子网络流与匹配：增广路框架中的 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$ 指数。

## 参考文献

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