零和博弈的近似 Nash 均衡

给 $m \times n$ payoff matrix $A$ ，零和博弈的 equilibrium 是一个 convex—concave saddle point。经典 multiplicative weights 每轮维护两组 exponential weights；若显式归一化/采样，成本随 $m + n$ 线性。量子算法为缓慢变化的 Gibbs 分布设计动态采样数据结构，把维数依赖降到平方根，同时输出可直接使用的稀疏经典混合策略。

本词条要回答三个层层递进的问题：第一，什么是零和博弈的近似均衡，为什么它可以归结为 regret 最小化；第二，经典 multiplicative weights update（MWU）为什么需要 $O (1/ ϵ^{2})$ 轮、每轮 $O (m + n)$ ；第三，量子算法在哪里、以什么方式把 $m + n$ 的维数依赖开根号，以及为什么最终输出仍然是一份”经典”的策略。

读者需要的前置知识：Grover 搜索与振幅放大、振幅估计的基本结论（相位估计一章），以及”从概率分布采样”与”制备对应量子态”的区别。不需要博弈论背景，相关概念都会现场定义。

1. 问题背景：零和博弈与 Nash 均衡

两人零和博弈 (two-player zero-sum game) 是最简单的非合作博弈模型。Row player 有 $m$ 个纯策略（编号 $1, \dots, m$ ），column player 有 $n$ 个纯策略；当 row 出 $i$ 、column 出 $j$ 时，payoff matrix $A$ 的元素 $A_{ij}$ 表示 column 付给 row 的数量——row 的收益是 $A_{ij}$ ，column 的收益是 $- A_{ij}$ ，两者之和恒为零，故称”零和”。

允许随机化时，双方各选一个混合策略 (mixed strategy)，即单纯形上的概率分布

Δ_{m} := {p \in R^{m} : p_{i} \geq 0, \sum_{i} p_{i} = 1}, Δ_{n} := {q \in R^{n} : q_{j} \geq 0, \sum_{j} q_{j} = 1} .

此时期望 payoff 为双线性型 $p^{T} A q = \sum_{i, j} p_{i} A_{ij} q_{j}$ 。Row 想把它最大化，column 想把它最小化。

一对策略 $(p^{*}, q^{*})$ 称为 Nash 均衡 (Nash equilibrium)，如果任何一方单独偏离都不能获益：

(p^{*})^{T} A q^{*} \geq p^{T} A q^{*} (\forall p \in Δ_{m}), (p^{*})^{T} A q^{*} \leq (p^{*})^{T} A q (\forall q \in Δ_{n}) .

零和情形在博弈论中地位特殊：Von Neumann 于 1928 年证明的 minimax 定理保证均衡一定存在，且求均衡等价于解一对对偶线性规划。计算上，经典精确解法（单纯形法、内点法）的时间随 $m, n$ 多项式增长——对”小规模”博弈这已经够用。真正的瓶颈出现在 $m, n$ 巨大（例如指数个纯策略、或矩阵只能按元素查询）且只要求 $ϵ$ 精度时：能否让运行时间对维数的依赖远低于线性？这正是量子算法切入的位置。

本词条依据的两篇文献给出两个世代的结果：van Apeldoorn 与 Gilyén 首先给出维数依赖为 $m + n$ 的量子算法（精度依赖 $ϵ^{- 3}$ ）；Bouland、Getachew、Jin、Sidford 与 Tian 用改进的 dynamic Gibbs sampling 把精度依赖改进到 $ϵ^{- 5/2}$ （外加一项与维数无关的 $ϵ^{- 3}$ ）。下面先把经典部分讲透，再看量子部分。

2. Minimax 定理与 saddle gap

Row player 选 $p \in Δ_{m}$ 最大化 payoff；column player 选 $q \in Δ_{n}$ 最小化。Von Neumann minimax 定理断言：双方”先后手”不影响结果，

v = p \in Δ_{m} max q \in Δ_{n} min p^{T} A q = q \in Δ_{n} min p \in Δ_{m} max p^{T} A q .

这个共同的值 $v$ 称为博弈的值 (value of the game)。我们不证明这个定理（它是线性规划对偶的推论），但要把它用成一个等价说法： $(p^{*}, q^{*})$ 是 Nash 均衡，当且仅当它是函数 $L (p, q) = p^{T} A q$ 的 saddle point——对 $p$ 是极大、对 $q$ 是极小。注意 $L$ 对 $p$ 线性（故 concave）、对 $q$ 线性（故 convex），所以零和均衡是一个 convex—concave saddle point 问题，这是后文一切算法的几何框架。

近似均衡的误差用 saddle gap 度量：

Gap (p, q) = i max (A q)_{i} - j min (p^{T} A)_{j} .

这里 $(A q)_{i} = e_{i}^{T} A q$ 是 row 出纯策略 $i$ 对抗 $q$ 的期望 payoff， $(p^{T} A)_{j} = p^{T} A e_{j}$ 同理。两个量的含义是： $max_{i} (A q)_{i}$ 是 row 对 $q$ 的 best response 能拿到的 payoff； $min_{j} (p^{T} A)_{j}$ 是 column 对 $p$ 的 best response 能把 payoff 压到的水平。差值越大，说明双方偏离现状的动机越强。

Lemma 1. 对任意 $(p, q)$ ，有 $Gap (p, q) \geq 0$ ，并且 $Gap (p, q) \leq ϵ$ 当且仅当 $(p, q)$ 满足

p^{T} A q \geq i max (A q)_{i} - ϵ, p^{T} A q \leq j min (p^{T} A)_{j} + ϵ,

即任何单边 best response 最多改善 $ϵ$ 。这样的 $(p, q)$ 称为 $ϵ$ -approximate Nash equilibrium。

证明。先注意 $p^{T} A q$ 被夹在 gap 的两个端点之间：

p^{T} A q = i \sum p_{i} (A q)_{i} \leq i \sum p_{i} i^{'} max (A q)_{i^{'}} = i^{'} max (A q)_{i^{'}},

因为 ${p_{i}}$ 是概率权重，加权平均不超过最大值；同理

p^{T} A q = j \sum q_{j} (p^{T} A)_{j} \geq j^{'} min (p^{T} A)_{j^{'}} .

于是 $Gap (p, q) = max_{i} (A q)_{i} - min_{j} (p^{T} A)_{j} \geq p^{T} A q - p^{T} A q = 0$ 。进一步，把 gap 按定义拆成两项：

Gap (p, q) = row 偏离的获益 [i max (A q)_{i} - p^{T} A q] + column 偏离的获益 [p^{T} A q - j min (p^{T} A)_{j}],

由上面的夹逼，两个方括号各自非负。两个非负数之和不超过 $ϵ$ ，当且仅当每一项都不超过 $ϵ$ ——这正是题述两个不等式。Q.E.D.

这个引理把”近似均衡”转化成一个可以逐项估计的数值条件：要验证 $(p, q)$ 是近似均衡，只需分别估计 $max_{i} (A q)_{i}$ 与 $min_{j} (p^{T} A)_{j}$ 两个量。第 9 节会看到，量子验证正是围绕这两个量展开的。

3. Multiplicative weights：更新规则与直觉

怎么找到近似均衡？思路是让双方玩一个假想的重复博弈，各自用”根据历史表现调整权重”的规则出招，然后取平均策略。本节定义这个规则，下一节证明它有效。

设 $A_{ij} \in [- 1, 1]$ （一般的有界矩阵总可以归一化到这个范围，这只影响常数因子）。Row player 维护一组权重 $w_{t} (i)$ ，初始 $w_{1} (i) = 1$ （对所有纯策略一视同仁）。第 $t$ 轮，column 实际出了纯策略 $j_{t}$ 之后，row 按指数规则更新：表现好（payoff $A_{i, j_{t}}$ 大）的策略权重乘上更大的因子，

w_{t + 1} (i) = w_{t} (i) e^{η A_{i, j_{t}}},

其中 $η > 0$ 是学习率，稍后选取。归一化后即得第 $t$ 轮的混合策略

p_{t} (i) = \frac{exp ( η \sum _{τ < t} A _{i, j_{τ}} )}{\sum _{i^{'}} exp ( η \sum _{τ < t} A _{i^{'}, j_{τ}} )} .

Column player 的目标相反（最小化 payoff），所以指数取负号：

q_{t} (j) = \frac{exp ( - η \sum _{τ < t} A _{i_{τ}, j} )}{\sum _{j^{'}} exp ( - η \sum _{τ < t} A _{i_{τ}, j^{'}} )} .

每一轮双方从自己的分布中采样 $i_{t} \sim p_{t}$ 、 $j_{t} \sim q_{t}$ ，然后查询 loss/payoff 信息（row 需要一列 $A_{\cdot, j_{t}}$ ，column 需要一行 $A_{i_{τ}, \cdot}$ ）完成更新。

直觉上， $exp (η \cdot 累计收益)$ 是一头”软的最大值”：累计收益最高的策略会得到指数放大的权重，但 $η$ 有限时其余策略仍保留正概率，避免被单次坏运气永久淘汰。这类指数权重规则在在线学习中称为 Hedge / multiplicative weights update，其分析范式是”势能函数 + telescoping”，下一节完整给出。

4. Regret 界的完整推导

Regret 衡量”实际拿到的平均收益”与”事后诸葛亮的最优纯策略”之间的差距。记 row 在第 $t$ 轮的 payoff 向量为 $g_{t} := A e_{j_{t}}$ （即矩阵的第 $j_{t}$ 列），row 出 $p_{t}$ 的期望收益是 $p_{t}^{T} g_{t}$ 。下面证明 MWU 的 regret 上界。

Theorem 2. 设 $η \leq 1$ 、 $∣ g_{t} (i) ∣ \leq 1$ 。MWU 保证

\frac{1}{T} t = 1 \sum T p_{t}^{T} g_{t} \geq i max \frac{1}{T} t = 1 \sum T g_{t} (i) - η - \frac{lo g m}{η T} .

证明。用 partition function（归一化常数）作势能函数：

Z_{t} := i = 1 \sum m w_{t} (i), 于是 p_{t} (i) = w_{t} (i) / Z_{t} .

第一步，把 $Z_{t + 1}$ 用 $Z_{t}$ 控制。由更新规则与 $p_{t}$ 的定义，

Z_{t + 1} = i \sum w_{t} (i) e^{η g_{t} (i)} = Z_{t} i \sum p_{t} (i) e^{η g_{t} (i)} .

对指数项用初等不等式 $e^{x} \leq 1 + x + x^{2}$ （对 $x \leq 1$ 成立；我们的 $x = η g_{t} (i)$ 满足 $∣ x ∣ \leq η \leq 1$ ），

i \sum p_{t} (i) e^{η g_{t} (i)} \leq i \sum p_{t} (i) (1 + η g_{t} (i) + η^{2} g_{t} (i)^{2}) = 1 + η p_{t}^{T} g_{t} + η^{2} i \sum p_{t} (i) g_{t} (i)^{2} .

等号处只用了 $\sum_{i} p_{t} (i) = 1$ 与 $p_{t}^{T} g_{t} = \sum_{i} p_{t} (i) g_{t} (i)$ 的定义。再用 $∣ g_{t} (i) ∣ \leq 1$ 得 $\sum_{i} p_{t} (i) g_{t} (i)^{2} \leq \sum_{i} p_{t} (i) = 1$ ，于是

i \sum p_{t} (i) e^{η g_{t} (i)} \leq 1 + η p_{t}^{T} g_{t} + η^{2} \leq exp (η p_{t}^{T} g_{t} + η^{2}),

第二个不等号是另一条初等不等式 $1 + x \leq e^{x}$ （对一切实数 $x$ ）。代回得单步势能估计

Z_{t + 1} \leq Z_{t} exp (η p_{t}^{T} g_{t} + η^{2}) .

第二步，telescoping。把上式对 $t = 1, \dots, T$ 累乘，指数相加：

Z_{T + 1} \leq Z_{1} exp (η t = 1 \sum T p_{t}^{T} g_{t} + η^{2} T) = m exp (η t \sum p_{t}^{T} g_{t} + η^{2} T),

这里用了初始条件 $Z_{1} = \sum_{i} w_{1} (i) = m$ （所有权重初始为 1）。

第三步，从下方控制 $Z_{T + 1}$ 。设 $i^{*} = ar g max_{i} \sum_{t} g_{t} (i)$ 是事后最优纯策略。因为和式中每一项非负，只保留 $i^{*}$ 一项不会变大：

Z_{T + 1} = i \sum w_{T + 1} (i) \geq w_{T + 1} (i^{*}) = exp (η t = 1 \sum T g_{t} (i^{*})),

其中等号是把更新规则从 $w_{1} (i^{*}) = 1$ 起连乘 $T$ 次的结果。

第四步，合并上下界并取对数。由第二步与第三步，

η t \sum g_{t} (i^{*}) \leq lo g m + η t \sum p_{t}^{T} g_{t} + η^{2} T .

两边除以 $η T$ （ $η > 0$ ，不等号方向不变），整理即得

\frac{1}{T} t \sum p_{t}^{T} g_{t} \geq \frac{1}{T} t \sum g_{t} (i^{*}) - η - \frac{lo g m}{η T} = i max \frac{1}{T} t \sum g_{t} (i) - η - \frac{lo g m}{η T} .

Q.E.D.

有两点值得停下来看。其一，证明里唯一的”损失”来自两处放缩： $e^{x} \leq 1 + x + x^{2}$ 引入了 $η^{2} T$ 项（二阶项），只保留 $i^{*}$ 引入了 $lo g m$ 项（对 m 个策略的”无知税”）。Regret 界的形状 $η + \frac{l o g m}{η T}$ 完全是这两笔账的平衡。其二，上面的推导假设 row 每轮看到的是确定的 payoff 向量 $g_{t}$ ；在采样版本（只看到所查询的元素）中，每一步的更新是无偏估计，需要用 Hoeffding/Azuma 型集中不等式控制随机涨落——多出的因子只有对数级，被吸收进 $O$ 记号。因此采样版结论形式相同：

\frac{1}{T} t \sum e_{i_{t}}^{T} A q_{t} \geq i max e_{i}^{T} A \overset{q}{ˉ} - O (η + \frac{lo g m}{η T}),

其中 $\overset{q}{ˉ} = \frac{1}{T} \sum_{t} e_{j_{t}}$ 是 column 实际出招的经验分布（用 $\sum_{t} g_{t} (i) / T = (A \overset{q}{ˉ})_{i}$ 改写最大值项）。Column 一方对称：

\frac{1}{T} t \sum p_{t}^{T} A e_{j_{t}} \leq j min \overset{p}{ˉ}^{T} A e_{j} + O (η + \frac{lo g n}{η T}), \overset{p}{ˉ} = \frac{1}{T} t \sum e_{i_{t}} .

参数平衡。 现在的任务是选 $η, T$ 使误差项 $f (η) = η + \frac{l o g m}{η T}$ 不超过 $ϵ$ 。先对固定的 $T$ 优化 $η$ ：求导

f^{'} (η) = 1 - \frac{lo g m}{η ^{2} T} = 0 ⟹ η^{*} = \frac{lo g m}{T},

此时两项相等（ $η^{*} = \frac{l o g m}{η ^{*} T}$ ，这正是”参数平衡”的含义：让两个误差来源同阶），最小值

f (η^{*}) = 2 \frac{lo g m}{T} .

要求 $2 lo g m / T \leq ϵ$ ，解得

T \geq \frac{4 lo g m}{ϵ ^{2}} ⟹ η = Θ (ϵ), T = Θ (\frac{lo g m}{ϵ ^{2}}) = O (1/ ϵ^{2}) .

于是经验策略 $(\overset{p}{ˉ}, \overset{q}{ˉ})$ 满足什么？下一节把两个 regret 界拼起来。

5. 从 regret 到近似均衡

把 row 与 column 的 regret 界相加。记两边共有的”平均对局收益”为

V := \frac{1}{T} t = 1 \sum T p_{t}^{T} A q_{t}

（采样版中用集中不等式把 $e_{i_{t}}^{T} A q_{t}$ 、 $p_{t}^{T} A e_{j_{t}}$ 与 $p_{t}^{T} A q_{t}$ 的差控制在同一误差量级内）。Row 的界给出

i max (A \overset{q}{ˉ})_{i} \leq V + O (ϵ);

column 的界给出

j min (\overset{p}{ˉ}^{T} A)_{j} \geq V - O (ϵ) .

两式相减， $V$ 恰好抵消：

Gap (\overset{p}{ˉ}, \overset{q}{ˉ}) = i max (A \overset{q}{ˉ})_{i} - j min (\overset{p}{ˉ}^{T} A)_{j} \leq V + O (ϵ) - V + O (ϵ) = O (ϵ) .

由 Lemma 1， $(\overset{p}{ˉ}, \overset{q}{ˉ})$ 是 $O (ϵ)$ -approximate Nash equilibrium。这就是 MWU 解零和博弈的完整逻辑链：

MWU 低 regret ⟹ 经验分布的 saddle gap 小 ⟹ 近似均衡 .

注意一个微妙之处：输出的是 $\overset{p}{ˉ}, \overset{q}{ˉ}$ （各轮实际出招的经验分布），而不是 $\frac{1}{T} \sum_{t} p_{t}$ （各轮分布的平均）。前者是稀疏的——至多 $T$ 个不同纯策略出现过——这一点对量子算法的输出形式至关重要，见第 8 节。

6. 经典实现的维数瓶颈

MWU 每轮要做什么？看 row 一方。定义能量向量

u_{t} (i) = η τ < t \sum A_{i, j_{τ}}, 于是 p_{t} (i) = \frac{e ^{u_{t} (i)}}{Z _{t}}, Z_{t} = i \sum e^{u_{t} (i)} .

相邻两轮的 $u$ 只差一列的贡献： $u_{t + 1} (i) = u_{t} (i) + η A_{i, j_{t}}$ ，更新全部 $m$ 个分量要 $O (m)$ ；更本质的障碍是从 $p_{t}$ 采样需要 partition function $Z_{t}$ ，显式重算是 $O (m)$ 次指数运算与求和。Column 一方对称地需要 $O (n)$ 。于是每轮 $Ω (m + n)$ ，乘上轮数 $T = O (1/ ϵ^{2})$ ，经典总时间（在按元素查询 $A$ 的 oracle 模型下，配合适当的数据结构/随机化）为

O (\frac{m + n}{ϵ ^{2}}) .

瓶颈的结构值得看清楚：每轮真正”新”的信息只有一列（或一行）共 $O (1)$ 次查询的量级，但采样步骤强迫我们 touch 全部 $m$ 个权重。维数线性的开销不来自信息量，而来自显式表示与归一化整个分布。这正暗示了量子加速的切入点：量子态天然把整个分布编码在振幅里，“归一化”是免费的，“采样”是一次测量——只要能高效制备对应量子态。

7. 量子动态 Gibbs 采样

目标量子态是 Gibbs 分布的振幅编码（平方根振幅，使测量概率正比于 $e^{u_{t} (i)}$ ）：

∣ p_{t} ⟩ = Z_{t}^{- 1/2} i \sum e^{u_{t} (i) /2} ∣ i ⟩ .

制备它之后测量计算基，就得到一个服从 $p_{t}$ 的经典样本 $i_{t}$ ——正是 MWU 每轮需要的东西。

朴素制备为什么不够。 标准做法是：从均匀叠加出发，把 $u_{t} (i)$ 算进辅助寄存器，受控旋转把振幅压出因子 $e^{u_{t} (i) /2}$ ，再对辅助位 postselect。问题在成功率：受控旋转要求振幅不超过 1，必须统一除以最大权重 $e^{u_{m a x}}$ ，于是成功率正比于 $\frac{Z _{t} / m}{e ^{u_{m a x}}}$ ——即平均权重与最大权重之比。权重分散时这个比值可以小到 $Ω (1/ m)$ ，配合振幅放大也只是把每轮成本压到 $m$ 量级，而且每轮都要从零制备一遍。这正是要改进的对象。

动态思想：权重变化很慢。 关键观察是相邻两轮的 Gibbs 分布几乎相同：

u_{t + 1} (i) - u_{t} (i) = η A_{i, j_{t}} \in [- η, η], 权重比 e^{(u_{t + 1} (i) - u_{t} (i)) /2} \in [e^{- η /2}, e^{η /2}] .

由于 $η = Θ (ϵ)$ 是小量，每个权重每轮只改变约 $1 \pm η /2$ 。如果已经有 $∣ p_{t} ⟩$ （或其采样器），“修正”出 $∣ p_{t + 1} ⟩$ 应该比从头制备便宜得多——这与经典情形形成对照：经典的瓶颈恰恰是每轮无法复用上一轮的结果去采样。

Dynamic Gibbs sampling 数据结构把这一直觉落实为四个机制：

分层记录权重范围与重元素。 维护权重量级的分层估计，识别哪些 $i$ 的权重显著偏大（heavy hitters）。这样在修正时可以逐块控制权重比的上界，而不必对全部 $m$ 个分量做最坏情况假设。
复用上一轮的 sampler/reference state。 不销毁上一轮的制备结果，把它当作 rejection sampling 的提议分布（proposal）： $p_{t}$ 与 $p_{t + 1}$ 逐点只差 $e^{\pm η /2}$ 因子，是天然的好的 proposal。
Rejection sampling + 振幅放大修正权重比。 以与 $e^{(u_{t + 1} (i) - u_{t} (i)) /2}$ 成比例的概率接受样本；因为比值被限制在 $[e^{- η /2}, e^{η /2}]$ ，接受概率是 $Ω (e^{- η}) = 1 - O (η)$ 量级，几乎不浪费。振幅放大把”重复直到接受”的开销从 $O (1/ p)$ 降到 $O (1/ p)$ （这正是 Grover/振幅放大的标准二次加速），而这里的 $p$ 接近 1，开销近常数。
用低方差 mean/amplitude estimation 更新归一化。 新 partition function 满足

\frac{Z _{t + 1}}{Z _{t}} = i \sum p_{t} (i) e^{u_{t + 1} (i) - u_{t} (i)},

即一个关于 $p_{t}$ 的有界随机变量的期望。用振幅估计以相对精度 $δ$ 估计它，开销是 $O (1/ δ)$ （相位估计给出的标准精度反比），而非经典 Monte Carlo 的 $O (1/ δ^{2})$ ；并且是对旧分布采样，不用每轮从零重算 $O (m)$ 项的和。

综合起来，一次”从 $m$ 个权重中采样”的维数开销从朴素方案的线性（最坏情形）降到约 $m$ ——粗略地说，所有”以成功概率 $p$ 从 $m$ 个元素中取样/求和”的子任务都被振幅放大开了根号，而动态复用保证了 $p$ 不退化（这是”dynamic”相对朴素 Gibbs 制备的本质改进；完整的数据结构不变量分析见原文）。另一方对称地得到 $n$ 。与此同时必须控制两笔误差账： $T$ 轮误差的累计，以及反复复用导致的 state disturbance（量子态被测量/修正操作逐渐污染）。处理方式是给每轮分配 $δ = O (ϵ / T)$ 的误差预算，使 $\sum_{t} δ = O (ϵ)$ ；每轮精度要求因此提高，这是下一节复杂度中额外 $ϵ$ 幂次的来源。

8. 总复杂度与输出形式

改进算法（Bouland 等）的运行时间为

O (m + n ϵ^{- 5/2} + ϵ^{- 3}) .

逐项解读每个因子的来源（以下是量级层面的账，精确幂次依赖数据结构细节）：

$m + n$ ：第 7 节的维数开销——每轮 row 侧 $m$ 、column 侧 $n$ 的动态 Gibbs 采样，合并写成 $m + n$ 。这是相对经典 $O ((m + n) / ϵ^{2})$ 的核心收益：维数依赖被开根号。
$ϵ^{- 5/2}$ ：轮数与单轮精度的乘积。 $T = O (ϵ^{- 2})$ 轮（第 4 节）；每轮误差预算 $δ = O (ϵ / T) = O (ϵ^{3})$ 使累计误差可控，而精度要求的提高给维数相关部分再添 $ϵ^{- 1/2}$ 量级开销，合计 $ϵ^{- 2} \cdot ϵ^{- 1/2} = ϵ^{- 5/2}$ 。
$ϵ^{- 3}$ ：与维数无关的高精度归一化/期望估计。partition function 比值需要估到相对精度 $δ = Θ (ϵ / T) = Θ (ϵ^{3})$ ，振幅估计的 $O (1/ δ)$ 直接给出 $ϵ^{- 3}$ 。这一项不含 $m, n$ ，在矩阵很大而精度适中的区域不重要，但精度极高时会成为主项。

与早期量子算法（van Apeldoorn–Gilyén）的 $O (m + n ϵ^{- 3})$ 比较：维数依赖相同，改进在精度依赖从 $ϵ^{- 3}$ 降到 $ϵ^{- 5/2}$ ，代价是引入与维数无关的 $ϵ^{- 3}$ 项。

与经典方法的 crossover。 量子何时确实更快？比较主项：

m + n ϵ^{- 5/2} \leq \frac{m + n}{ϵ ^{2}} ⟺ ϵ^{- 1/2} \leq m + n ⟺ ϵ \geq (m + n)^{- 1} .

（第一步两边同除 $m + n ϵ^{- 2}$ ；第二步两边平方再整理。）再核对 $ϵ^{- 3}$ 项：它不超过经典复杂度的条件同样是 $ϵ^{- 3} \leq (m + n) ϵ^{- 2} ⟺ ϵ \geq (m + n)^{- 1}$ 。所以在

ϵ = Ω ((m + n)^{- 1})

这一广泛区域（包括所有”精度不随矩阵规模缩小”的固定 $ϵ$ ），量子算法相对经典有 polynomial speedup；反之当精度要求极高（ $ϵ$ 比维数倒数还小）时，额外的 $ϵ$ 幂次可能主导，加速消失。这个区域划分与两条复杂度曲线的相对位置完全一致，没有任何保留条款被藏起来。

输出形式：稀疏经典策略。 算法的输出不是振幅编码的量子态 $∣ p^{*} ⟩$ ，而是采样历史 ${(i_{t}, j_{t})}_{t = 1}^{T}$ 给出的经验分布

\overset{p}{ˉ} = \frac{1}{T} t \sum e_{i_{t}}, \overset{q}{ˉ} = \frac{1}{T} t \sum e_{j_{t}} .

$\overset{p}{ˉ}$ 的非零分量至多 $T$ 个（只有实际被采样到过的纯策略出现），每个非零分量是 $k / T$ 形的有理数（出现次数除以总轮数）。存储这份分布只需记录 $\leq T$ 个”指标 + 频数”对，长度为

O (T lo g (m + n)) bits

（每个指标用 $lo g m$ 或 $lo g n$ 位命名）。这份输出可以直接使用：从 $\overset{p}{ˉ}$ 采样等价于从记录的多重集合里均匀取一个；计算 $p^{T} A q$ 形 payoff 也只需在稀疏支持上求和。相反，若输出是 $m$ 维量子态，把它读出来需要对 $m + n$ 维系统做 quantum state tomography，开销会重新引入维数的线性（甚至更差）依赖，把前面的加速全部抵消。输出模型与算法内部表示同样重要，这是本词条与许多”量子态即答案”的算法（如 HHL）的关键区别。

9. 验证与 payoff oracle

算法需要一个访问 payoff matrix 的量子 oracle：

O_{A} ∣ i, j, z ⟩ = ∣ i, j, z \oplus A_{ij} ⟩,

即按指标查询矩阵元并写入加法寄存器。 $A_{ij} \in [- 1, 1]$ 是实数， $z \oplus A_{ij}$ 实际指 fixed-point 编码下的模加；寄存器必须给足定点精度，使舍入误差不污染 $ϵ$ 量级的结论（精度位数只带来对数级开销，被 $O$ 吸收）。

得到候选 $(\overset{p}{ˉ}, \overset{q}{ˉ})$ 后，如何验证 saddle gap？由 Lemma 1，只需估计

i max (A \overset{q}{ˉ})_{i}, j min (\overset{p}{ˉ}^{T} A)_{j} .

两个量结构对称，看第一个。由于 $\overset{q}{ˉ}$ 至多 $T$ 稀疏，每个 $(A \overset{q}{ˉ})_{i} = \frac{1}{T} \sum_{t} A_{i, j_{t}}$ 是至多 $T$ 项的和，可在稀疏支持上计算；再对 $m$ 个指标做 quantum maximum finding（Dürr–Høyer 型，Grover 的变体），以 $O (m)$ 次查询/估计找到最大值，而非经典线性扫描 $m$ 。验证侧的失败概率同样要控制：全算法共 $T$ 轮、每轮若干次估计，每次子程序需放大成功概率到 $1 - O (δ / T)$ （重复 $O (lo g (T / δ))$ 次取中位数/多数表决），使 union bound 下总失败率仍为 $O (δ)$ 。这笔账也只贡献对数因子。

适用范围必须说清楚。 以上全部结果只针对 two-player zero-sum（更一般地，bilinear saddle point）问题。对一般和博弈，Nash 均衡是 PPAD 型的 fixed point 问题，既无 minimax 结构，也不能由 regret 最小化直接逼近——两方各自跑 MWU 的经验平均一般不收敛到 Nash 均衡。这篇算法的结论不能推广过去。

10. 小例子：Matching Pennies

用最小的非平凡博弈把第 2 节的量全部算一遍。Matching Pennies 的 payoff matrix 为

A = (1 - 1 - 1 1) .

（Row 猜”是否同色”：同色 row 赢 1，异色输 1。）设混合策略

p = (x, 1 - x), q = (y, 1 - y), x, y \in [0, 1] .

先算双方的纯策略 payoff 向量：

A q = (y - (1 - y) - y + (1 - y)) = (2 y - 1 1 - 2 y), p^{T} A = (x - (1 - x), - x + (1 - x)) = (2 x - 1, 1 - 2 x) .

期望 payoff 为

p^{T} A q = x (2 y - 1) + (1 - x) (1 - 2 y) = (2 x - 1) (2 y - 1) .

均衡。 若 $x = 1/2$ ，则 $p^{T} A = (0, 0)$ ：无论 column 怎么出，payoff 恒为 0，column 无从改善；对称地 $y = 1/2$ 使 row 无从改善。所以

p^{*} = q^{*} = (1/2, 1/2), v = (2 \cdot \frac{1}{2} - 1)^{2} = 0.

Gap 的通式。 由第 2 节定义，

i max (A q)_{i} = max (2 y - 1, 1 - 2 y) = ∣2 y - 1∣, j min (p^{T} A)_{j} = min (2 x - 1, 1 - 2 x) = - ∣2 x - 1∣,

因此

Gap (p, q) = ∣2 x - 1∣ + ∣2 y - 1∣.

检验： $x = y = 1/2$ 时 gap $= 0$ ，与均衡一致；任何 $x \neq = 1/2$ 或 $y \neq = 1/2$ 都严格为正，与”均衡唯一”一致。

与原文断言核对。 取 $q = (1/2 + δ, 1/2 - δ)$ （即 $2 y - 1 = 2 δ$ ）、 $p$ 均匀（ $x = 1/2$ ）：row 的 best response 拿到 $max_{i} (A q)_{i} = ∣2 δ ∣ = 2∣ δ ∣$ ，而 $p^{T} A = (0, 0)$ 给出 $min_{j} (p^{T} A)_{j} = 0$ ，故

Gap = 2∣ δ ∣.

这直接给出策略估计误差与 $ϵ$ 的关系：对手策略偏离均衡 $δ$ （以分量计）本身就贡献 $2∣ δ ∣$ 的 gap。反过来，要求 gap $\leq ϵ$ 等价于要求双方策略都落在均衡的 $O (ϵ)$ 邻域内——对小博弈”输出近似均衡”与”逼近均衡点”是一回事，对大博弈前者才是算法实际保证的东西。

11. 小结与习题

零和 equilibrium 等价于 convex—concave minimax saddle point；saddle gap 把”近似均衡”变成两个可估计量的差（Lemma 1）。
MWU 的势能分析给出 regret 界 $η + \frac{l o g m}{η T}$ ；平衡两项得 $η = Θ (ϵ)$ 、 $T = O (1/ ϵ^{2})$ 轮后，经验出招分布的 gap 为 $O (ϵ)$ 。
经典瓶颈不在信息量而在每轮 $O (m + n)$ 的显式归一化/采样；quantum dynamic Gibbs sampling 利用相邻权重只变 $1 \pm O (η)$ 的事实，复用上一轮 sampler 并以 rejection sampling + amplitude amplification 修正，把维数依赖降到 $m + n$ 。
总时间 $O (m + n ϵ^{- 5/2} + ϵ^{- 3})$ ；在 $ϵ = Ω ((m + n)^{- 1})$ 区域相对经典多项式加速。
输出是支持至多 $T$ 、长度 $O (T lo g (m + n))$ 的稀疏经典分布，避免 tomography；结果不推广到一般和 Nash（PPAD 型问题）。

习题。

（定义核查）补全 Lemma 1 的证明中”加权平均不超过最大值”这一步的细节，并举例说明对一般的 $(p, q)$ ，gap 可以严格大于双方实际偏离获益中的任何一项（提示：让另一方策略离最优也很远）。
（推导）从单步估计 $Z_{t + 1} \leq Z_{t} exp (η p_{t}^{T} g_{t} + η^{2})$ 出发，不翻回第 4 节，独立重推 Theorem 2；并验证 $η^{*} = lo g m / T$ 确实是 $f (η) = η + \frac{l o g m}{η T}$ 的极小点（检查二阶导数）。
（计算）对 Matching Pennies 验证：当双方都用 $x = y = 1/2 + δ$ 时 $Gap = 4∣ δ ∣$ ；再构造一个 $2 \times 2$ 零和博弈使其均衡不是均匀分布，并计算它的 gap 通式。
（复杂度分析）设 $m + n = 1 0^{6}$ 。分别画出经典 $O ((m + n) / ϵ^{2})$ 、早期量子 $O (m + n ϵ^{- 3})$ 与改进量子 $O (m + n ϵ^{- 5/2} + ϵ^{- 3})$ 在 $ϵ \in [1 0^{- 8}, 1]$ 上的相对大小（忽略对数因子），找出改进算法占优的区间，并与 $ϵ = (m + n)^{- 1}$ 的解析阈值对照。
（输出模型）解释为什么经验分布 $\overset{p}{ˉ}$ 的支持大小至多 $T$ 、描述长度 $O (T lo g (m + n))$ ；如果算法改为输出 $\frac{1}{T} \sum_{t} p_{t}$ （分布的平均），这两个结论还成立吗？为什么算法偏偏选择输出经验分布？
（概念延伸）两人一般和博弈中，双方各自运行 no-regret 动态。用囚徒困境或性别之争（battle of the sexes）说明：minimax 值不再有意义，且经验平均策略不必接近任何 Nash 均衡。由此说明第 9 节”不能推广”的保留条款是本质的而非技术性的。

参考文献

Zoo 编号 485：Bouland、Getachew、Jin、Sidford 与 Tian, Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling.
Zoo 编号 486：van Apeldoorn 与 Gilyén, Quantum Algorithms for Zero-Sum Games.

参考资料

本词条整理自《量子计算算法教程》原文：ch14-optimization-numerics/nash-equilibria
内容遵循 CC BY-NC-SA 4.0 许可协议

description	给 m\times n payoff matrix A，零和博弈的 equilibrium 是一个 convex--concave saddle point。经典 multiplicative weights 每轮维护两组 exponent…
tags	优化与数值
aliases	Nash

量子计算百科