# 零和博弈的近似 Nash 均衡：Multiplicative Weights 与 Dynamic Gibbs Sampling

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

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

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

:::{admonition} 本课知识点
:class: tip

1. **[零和博弈与 Nash 均衡](#zero-sum-nash)**——能写出混合策略、期望 payoff 与均衡不等式的定义，并解释零和结构与 minimax 定理在其中的作用。
2. **[Minimax 定理与 saddle gap](#minimax-saddle-gap)**——能把零和均衡表述为 convex--concave saddle point，并推导 saddle gap 与 $\epsilon$-近似均衡的等价性（Lemma 1）。
3. **[MWU 更新规则与 regret 分析](#mwu-regret-analysis)**——能写出双方指数权重的更新公式，用势能函数与 telescoping 推导 regret 界 $\eta+\frac{\log m}{\eta T}$，并平衡参数得到 $T=\widetilde O(1/\epsilon^2)$。
4. **[从 regret 到近似均衡](#regret-to-equilibrium)**——能把双方 regret 界相加，推导经验分布 $(\bar p,\bar q)$ 的 saddle gap 为 $O(\epsilon)$，并解释输出经验分布而非分布平均的原因。
5. **[经典维数瓶颈与量子动态 Gibbs 采样](#classical-bottleneck-quantum-gibbs)**——能解释经典实现每轮 $O(m+n)$ 开销的来源，比较朴素 Gibbs 制备与动态复用 sampler，并说明维数依赖如何降到 $\sqrt{m+n}$。
6. **[总复杂度与输出形式](#complexity-output)**——能解读 $\widetilde O(\sqrt{m+n}\,\epsilon^{-5/2}+\epsilon^{-3})$ 中各因子的来源，推导经典与量子的 crossover 条件，并计算稀疏经典输出的描述长度。
7. **[验证、payoff oracle 与适用范围](#verification-oracle-scope)**——能写出 payoff oracle 的定义与验证近似均衡所需估计的两个量，并说明结论为何不能推广到一般和博弈。
8. **[Matching Pennies 实例](#matching-pennies)**——能在具体 $2\times2$ 零和博弈上计算纯策略 payoff 向量、均衡、博弈的值与 gap 通式，并据此解释策略误差与 gap 的关系。

:::

(zero-sum-nash)=
## 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)**，即单纯形上的概率分布

$$
\Delta_m:=\Big\{p\in\mathbb R^m:\ p_i\ge0,\ \textstyle\sum_i p_i=1\Big\},
\qquad
\Delta_n:=\Big\{q\in\mathbb R^n:\ q_j\ge0,\ \textstyle\sum_j q_j=1\Big\}.
$$

此时期望 payoff 为双线性型 $p^TAq=\sum_{i,j}p_iA_{ij}q_j$。Row 想把它最大化，column 想把它最小化。

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

$$
(p^*)^TAq^*\ge p^TAq^*\quad(\forall p\in\Delta_m),
\qquad
(p^*)^TAq^*\le (p^*)^TAq\quad(\forall q\in\Delta_n).
$$

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

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

(minimax-saddle-gap)=
## 2. Minimax 定理与 saddle gap

Row player 选 $p\in\Delta_m$ 最大化 payoff；column player 选 $q\in\Delta_n$ 最小化。Von Neumann minimax 定理断言：双方"先后手"不影响结果，

$$
v=\max_{p\in\Delta_m}\min_{q\in\Delta_n}p^TAq
=\min_{q\in\Delta_n}\max_{p\in\Delta_m}p^TAq.
$$

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

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

$$
\operatorname{Gap}(p,q)
=\max_i(Aq)_i-\min_j(p^TA)_j.
$$

这里 $(Aq)_i=e_i^TAq$ 是 row 出纯策略 $i$ 对抗 $q$ 的期望 payoff，$(p^TA)_j=p^TAe_j$ 同理。两个量的含义是：$\max_i(Aq)_i$ 是 row 对 $q$ 的 best response 能拿到的 payoff；$\min_j(p^TA)_j$ 是 column 对 $p$ 的 best response 能把 payoff 压到的水平。差值越大，说明双方偏离现状的动机越强。

**Lemma 1**. 对任意 $(p,q)$，有 $\operatorname{Gap}(p,q)\ge0$，并且 $\operatorname{Gap}(p,q)\le\epsilon$ 当且仅当 $(p,q)$ 满足

$$
p^TAq\ge\max_i(Aq)_i-\epsilon,
\qquad
p^TAq\le\min_j(p^TA)_j+\epsilon,
$$

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

**证明**。先注意 $p^TAq$ 被夹在 gap 的两个端点之间：

$$
p^TAq=\sum_i p_i\,(Aq)_i\le\sum_i p_i\max_{i'}(Aq)_{i'}=\max_{i'}(Aq)_{i'},
$$

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

$$
p^TAq=\sum_j q_j\,(p^TA)_j\ge\min_{j'}(p^TA)_{j'}.
$$

于是 $\operatorname{Gap}(p,q)=\max_i(Aq)_i-\min_j(p^TA)_j\ge p^TAq-p^TAq=0$。进一步，把 gap 按定义拆成两项：

$$
\operatorname{Gap}(p,q)
=\underbrace{\big[\max_i(Aq)_i-p^TAq\big]}_{\text{row 偏离的获益}}\;
+\underbrace{\big[p^TAq-\min_j(p^TA)_j\big]}_{\text{column 偏离的获益}},
$$

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

这个引理把"近似均衡"转化成一个可以逐项估计的数值条件：要验证 $(p,q)$ 是近似均衡，只需分别估计 $\max_i(Aq)_i$ 与 $\min_j(p^TA)_j$ 两个量。第 9 节会看到，量子验证正是围绕这两个量展开的。

(mwu-regret-analysis)=
## 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^{\eta A_{i,j_t}},
$$

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

$$
p_t(i)=
\frac{\exp\!\big(\eta\sum_{\tau<t}A_{i,j_\tau}\big)}
{\sum_{i'}\exp\!\big(\eta\sum_{\tau<t}A_{i',j_\tau}\big)}.
$$

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

$$
q_t(j)=
\frac{\exp\!\big(-\eta\sum_{\tau<t}A_{i_\tau,j}\big)}
{\sum_{j'}\exp\!\big(-\eta\sum_{\tau<t}A_{i_\tau,j'}\big)}.
$$

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

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

## 4. Regret 界的完整推导

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

**Theorem 2**. 设 $\eta\le1$、$|g_t(i)|\le1$。MWU 保证

$$
\frac1T\sum_{t=1}^T p_t^Tg_t
\;\ge\;
\max_i\frac1T\sum_{t=1}^T g_t(i)
\;-\;\eta-\frac{\log m}{\eta T}.
$$

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

$$
Z_t:=\sum_{i=1}^m w_t(i),
\qquad\text{于是 } p_t(i)=w_t(i)/Z_t.
$$

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

$$
Z_{t+1}
=\sum_i w_t(i)e^{\eta g_t(i)}
=Z_t\sum_i p_t(i)e^{\eta g_t(i)}.
$$

对指数项用初等不等式 $e^x\le1+x+x^2$（对 $x\le1$ 成立；我们的 $x=\eta g_t(i)$ 满足 $|x|\le\eta\le1$），

$$
\sum_i p_t(i)e^{\eta g_t(i)}
\le\sum_i p_t(i)\big(1+\eta g_t(i)+\eta^2g_t(i)^2\big)
=1+\eta\,p_t^Tg_t+\eta^2\sum_i p_t(i)g_t(i)^2.
$$

等号处只用了 $\sum_i p_t(i)=1$ 与 $p_t^Tg_t=\sum_i p_t(i)g_t(i)$ 的定义。再用 $|g_t(i)|\le1$ 得 $\sum_i p_t(i)g_t(i)^2\le\sum_i p_t(i)=1$，于是

$$
\sum_i p_t(i)e^{\eta g_t(i)}\le1+\eta\,p_t^Tg_t+\eta^2
\le\exp\!\big(\eta\,p_t^Tg_t+\eta^2\big),
$$

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

$$
Z_{t+1}\le Z_t\exp\!\big(\eta\,p_t^Tg_t+\eta^2\big).
$$

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

$$
Z_{T+1}
\le Z_1\exp\!\Big(\eta\sum_{t=1}^T p_t^Tg_t+\eta^2T\Big)
=m\exp\!\Big(\eta\sum_t p_t^Tg_t+\eta^2T\Big),
$$

这里用了初始条件 $Z_1=\sum_i w_1(i)=m$（所有权重初始为 1）。

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

$$
Z_{T+1}=\sum_i w_{T+1}(i)\ge w_{T+1}(i^*)=\exp\!\Big(\eta\sum_{t=1}^T g_t(i^*)\Big),
$$

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

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

$$
\eta\sum_t g_t(i^*)
\le\log m+\eta\sum_t p_t^Tg_t+\eta^2T.
$$

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

$$
\frac1T\sum_t p_t^Tg_t
\ge\frac1T\sum_t g_t(i^*)-\eta-\frac{\log m}{\eta T}
=\max_i\frac1T\sum_t g_t(i)-\eta-\frac{\log m}{\eta T}.
$$

Q.E.D.

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

$$
\frac1T\sum_t e_{i_t}^TAq_t
\;\ge\;
\max_i e_i^TA\bar q-O\!\left(\eta+\frac{\log m}{\eta T}\right),
$$

其中 $\bar q=\frac1T\sum_t e_{j_t}$ 是 column 实际出招的经验分布（用 $\sum_t g_t(i)/T=(A\bar q)_i$ 改写最大值项）。Column 一方对称：

$$
\frac1T\sum_t p_t^TAe_{j_t}
\;\le\;
\min_j \bar p^TAe_j+O\!\left(\eta+\frac{\log n}{\eta T}\right),
\qquad \bar p=\frac1T\sum_t e_{i_t}.
$$

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

$$
f'(\eta)=1-\frac{\log m}{\eta^2T}=0
\quad\Longrightarrow\quad
\eta^*=\sqrt{\frac{\log m}{T}},
$$

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

$$
f(\eta^*)=2\sqrt{\frac{\log m}{T}}.
$$

要求 $2\sqrt{\log m/T}\le\epsilon$，解得

$$
T\ge\frac{4\log m}{\epsilon^2}
\quad\Longrightarrow\quad
\eta=\Theta(\epsilon),\qquad
T=\Theta\!\left(\frac{\log m}{\epsilon^2}\right)=\widetilde O(1/\epsilon^2).
$$

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

(regret-to-equilibrium)=
## 5. 从 regret 到近似均衡

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

$$
V:=\frac1T\sum_{t=1}^T p_t^TAq_t
$$

（采样版中用集中不等式把 $e_{i_t}^TAq_t$、$p_t^TAe_{j_t}$ 与 $p_t^TAq_t$ 的差控制在同一误差量级内）。Row 的界给出

$$
\max_i(A\bar q)_i\le V+O(\epsilon);
$$

column 的界给出

$$
\min_j(\bar p^TA)_j\ge V-O(\epsilon).
$$

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

$$
\operatorname{Gap}(\bar p,\bar q)
=\max_i(A\bar q)_i-\min_j(\bar p^TA)_j
\le V+O(\epsilon)-V+O(\epsilon)=O(\epsilon).
$$

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

$$
\text{MWU 低 regret}\ \Longrightarrow\ \text{经验分布的 saddle gap 小}\ \Longrightarrow\ \text{近似均衡}.
$$

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

(classical-bottleneck-quantum-gibbs)=
## 6. 经典实现的维数瓶颈

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

$$
u_t(i)=\eta\sum_{\tau<t}A_{i,j_\tau},
\qquad\text{于是 } p_t(i)=\frac{e^{u_t(i)}}{Z_t},\quad Z_t=\sum_i e^{u_t(i)}.
$$

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

$$
\widetilde O\!\left(\frac{m+n}{\epsilon^2}\right).
$$

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

## 7. 量子动态 Gibbs 采样

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

$$
|p_t\rangle
=Z_t^{-1/2}\sum_i e^{u_t(i)/2}|i\rangle.
$$

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

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

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

$$
u_{t+1}(i)-u_t(i)=\eta A_{i,j_t}\in[-\eta,\eta],
\qquad\text{权重比 } e^{(u_{t+1}(i)-u_t(i))/2}\in[e^{-\eta/2},e^{\eta/2}].
$$

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

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

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

$$
\frac{Z_{t+1}}{Z_t}=\sum_i p_t(i)\,e^{u_{t+1}(i)-u_t(i)},
$$

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

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

(complexity-output)=
## 8. 总复杂度与输出形式

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

$$
\widetilde O\!\left(
\sqrt{m+n}\,\epsilon^{-5/2}
+\epsilon^{-3}
\right).
$$

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

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

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

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

$$
\sqrt{m+n}\,\epsilon^{-5/2}\;\le\;\frac{m+n}{\epsilon^2}
\iff
\epsilon^{-1/2}\le\sqrt{m+n}
\iff
\epsilon\ge(m+n)^{-1}.
$$

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

$$
\epsilon=\Omega\!\left((m+n)^{-1}\right)
$$

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

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

$$
\bar p=\frac1T\sum_t e_{i_t},\qquad \bar q=\frac1T\sum_t e_{j_t}.
$$

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

$$
O\!\left(T\log(m+n)\right)\text{ bits}
$$

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

(verification-oracle-scope)=
## 9. 验证与 payoff oracle

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

$$
O_A|i,j,z\rangle
=|i,j,\,z\oplus A_{ij}\rangle,
$$

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

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

$$
\max_i(A\bar q)_i,\qquad \min_j(\bar p^TA)_j.
$$

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

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

(matching-pennies)=
## 10. 小例子：Matching Pennies

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

$$
A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}.
$$

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

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

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

$$
Aq=
\begin{pmatrix}y-(1-y)\\-y+(1-y)\end{pmatrix}
=\begin{pmatrix}2y-1\\1-2y\end{pmatrix},
\qquad
p^TA=
\big(x-(1-x),\ -x+(1-x)\big)
=\big(2x-1,\ 1-2x\big).
$$

期望 payoff 为

$$
p^TAq=x(2y-1)+(1-x)(1-2y)=(2x-1)(2y-1).
$$

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

$$
p^*=q^*=(1/2,1/2),\qquad v=(2\cdot\tfrac12-1)^2=0.
$$

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

$$
\max_i(Aq)_i=\max(2y-1,\,1-2y)=|2y-1|,
\qquad
\min_j(p^TA)_j=\min(2x-1,\,1-2x)=-|2x-1|,
$$

因此

$$
\operatorname{Gap}(p,q)=|2x-1|+|2y-1|.
$$

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

**与原文断言核对。** 取 $q=(1/2+\delta,\,1/2-\delta)$（即 $2y-1=2\delta$）、$p$ 均匀（$x=1/2$）：row 的 best response 拿到 $\max_i(Aq)_i=|2\delta|=2|\delta|$，而 $p^TA=(0,0)$ 给出 $\min_j(p^TA)_j=0$，故

$$
\operatorname{Gap}=2|\delta|.
$$

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

## 11. 小结

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

## 练习题

**练习 1【零和博弈与 Nash 均衡】**（→ [第 1 节](#zero-sum-nash)）

1. 写出双方混合策略单纯形 $\Delta_m,\Delta_n$ 的定义与期望 payoff $p^TAq$ 的表达式，并指出 row 与 column 各自的优化方向。
2. 证明：row 对固定 $q$ 的最优回应总可以取纯策略，即 $\max_{p\in\Delta_m}p^TAq=\max_i(Aq)_i$。

> 提示：把 $p^TAq=\sum_i p_i(Aq)_i$ 看成诸 $(Aq)_i$ 的加权平均。

**练习 2【Minimax 定理与 saddle gap】**（→ [第 2 节](#minimax-saddle-gap)）

1. 写出 $\operatorname{Gap}(p,q)$ 的定义，并分别说明 $\max_i(Aq)_i$ 与 $\min_j(p^TA)_j$ 对应哪一方的 best response payoff。
2. （定义核查）补全 Lemma 1 的证明中"加权平均不超过最大值"这一步的细节，并举例说明对一般的 $(p,q)$，gap 可以严格大于双方实际偏离获益中的任何一项。

> 提示：让另一方的策略离最优也很远。

**练习 3【MWU 更新规则与 regret 分析】**（→ [第 3 节](#mwu-regret-analysis)）

1. 设 $m=2$、$\eta=\frac12$、初始权重 $w_1=(1,1)$，第一轮 payoff 向量 $g_1=Ae_{j_1}=(1,-1)$。计算 $w_2$、$Z_2$ 与第 2 轮的混合策略 $p_2$（给出表达式与近似数值）。
2. （推导）从单步估计 $Z_{t+1}\le Z_t\exp(\eta p_t^Tg_t+\eta^2)$ 出发，不翻回第 4 节，独立重推 Theorem 2；并验证 $\eta^*=\sqrt{\log m/T}$ 确实是 $f(\eta)=\eta+\frac{\log m}{\eta T}$ 的极小点（检查二阶导数）。

> 提示：对 $f(\eta)=\eta+(\log m/T)\,\eta^{-1}$ 逐项求导。

**练习 4【从 regret 到近似均衡】**（→ [第 5 节](#regret-to-equilibrium)）

1. 记 $V=\frac1T\sum_t p_t^TAq_t$。由 $\max_i(A\bar q)_i\le V+\epsilon_1$ 与 $\min_j(\bar p^TA)_j\ge V-\epsilon_2$，推导 $\operatorname{Gap}(\bar p,\bar q)\le\epsilon_1+\epsilon_2$，并指出 $V$ 是如何被抵消的。
2. （输出模型）解释为什么经验分布 $\bar p$ 的支持大小至多 $T$、描述长度 $O(T\log(m+n))$；如果算法改为输出 $\frac1T\sum_t p_t$（分布的平均），这两个结论还成立吗？为什么算法偏偏选择输出经验分布？

> 提示：$\bar p$ 的每个非零分量都是 $k/T$ 形的有理数。

**练习 5【经典维数瓶颈与量子动态 Gibbs 采样】**（→ [第 6 节](#classical-bottleneck-quantum-gibbs)）

1. 写出 Gibbs 分布的振幅编码态 $|p_t\rangle$，并说明为什么对它测量计算基就得到一个服从 $p_t$ 的经典样本。
2. 验证相邻两轮每个权重只变动 $e^{\pm\eta/2}$ 因子，并由此说明 rejection sampling 的接受概率是 $1-O(\eta)$ 量级。
3. 解释朴素制备为何在权重集中于少数分量时成功率降到 $1/m$ 量级（即使配振幅放大也只降到 $\sqrt m$ 量级），而动态复用上一轮 sampler 如何避开这一最坏情况。

> 提示：受控旋转要求振幅不超过 1，朴素方案统一除以最大权重 $e^{u_{\max}}$。

**练习 6【总复杂度与输出形式】**（→ [第 8 节](#complexity-output)）

1. 解读 $\widetilde O(\sqrt{m+n}\,\epsilon^{-5/2}+\epsilon^{-3})$ 中各项因子的来源：$\sqrt{m+n}$、$\epsilon^{-5/2}$ 与 $\epsilon^{-3}$ 分别对应什么开销？
2. 若把算法输出从稀疏经典分布改成 $m$ 维量子态并要求完整读出，复杂度会发生什么变化？结合 quantum state tomography 说明。
3. （复杂度分析）设 $m+n=10^6$。分别画出经典 $\widetilde O((m+n)/\epsilon^2)$、早期量子 $\widetilde O(\sqrt{m+n}\epsilon^{-3})$ 与改进量子 $\widetilde O(\sqrt{m+n}\epsilon^{-5/2}+\epsilon^{-3})$ 在 $\epsilon\in[10^{-8},1]$ 上的相对大小（忽略对数因子），找出改进算法占优的区间，并与 $\epsilon=(m+n)^{-1}$ 的解析阈值对照。

> 提示：比较改进量子与经典时，先在两边同除 $\sqrt{m+n}\,\epsilon^{-2}$。

**练习 7【验证、payoff oracle 与适用范围】**（→ [第 9 节](#verification-oracle-scope)）

1. 写出 payoff oracle $O_A$ 的作用，并指出验证 $(\bar p,\bar q)$ 是 $\epsilon$-近似均衡需要估计哪两个量、各用什么量子子程序。
2. （概念延伸）两人一般和博弈中，双方各自运行 no-regret 动态。用囚徒困境或性别之争（battle of the sexes）说明：minimax 值不再有意义，且经验平均策略不必接近任何 Nash 均衡。由此说明第 9 节"不能推广"的保留条款是本质的而非技术性的。

> 提示：no-regret 保证的是逼近（粗）相关均衡，一般和博弈中它未必是 Nash 均衡。

**练习 8【Matching Pennies 实例】**（→ [第 10 节](#matching-pennies)）

1. 对 $A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}$ 与 $p=(x,1-x)$、$q=(y,1-y)$，计算 $Aq$、$p^TA$ 与期望 payoff $p^TAq$。
2. （计算）对 Matching Pennies 验证：当双方都用 $x=y=1/2+\delta$ 时 $\operatorname{Gap}=4|\delta|$；再构造一个 $2\times2$ 零和博弈使其均衡不是均匀分布，并计算它的 gap 通式。

> 提示：混合均衡由"对手的两个纯策略 payoff 相等"确定。

## 参考文献

- Zoo 编号 485：Bouland、Getachew、Jin、Sidford 与 Tian, [Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling](https://arxiv.org/abs/2301.03763).
- Zoo 编号 486：van Apeldoorn 与 Gilyén, [Quantum Algorithms for Zero-Sum Games](https://arxiv.org/abs/1904.03180).