零和博弈的近似 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 章）、振幅估计的基本结论（相位估计一章），以及"从概率分布采样"与"制备对应量子态"的区别。不需要博弈论背景，相关概念都会现场定义。

本课知识点

  1. 零和博弈与 Nash 均衡——能写出混合策略、期望 payoff 与均衡不等式的定义，并解释零和结构与 minimax 定理在其中的作用。

  2. Minimax 定理与 saddle gap——能把零和均衡表述为 convex--concave saddle point，并推导 saddle gap 与 \(\epsilon\)-近似均衡的等价性（Lemma 1）。

  3. MWU 更新规则与 regret 分析——能写出双方指数权重的更新公式，用势能函数与 telescoping 推导 regret 界 \(\eta+\frac{\log m}{\eta T}\)，并平衡参数得到 \(T=\widetilde O(1/\epsilon^2)\)。

  4. 从 regret 到近似均衡——能把双方 regret 界相加，推导经验分布 \((\bar p,\bar q)\) 的 saddle gap 为 \(O(\epsilon)\)，并解释输出经验分布而非分布平均的原因。

  5. 经典维数瓶颈与量子动态 Gibbs 采样——能解释经典实现每轮 \(O(m+n)\) 开销的来源，比较朴素 Gibbs 制备与动态复用 sampler，并说明维数依赖如何降到 \(\sqrt{m+n}\)。

  6. 总复杂度与输出形式——能解读 \(\widetilde O(\sqrt{m+n}\,\epsilon^{-5/2}+\epsilon^{-3})\) 中各因子的来源，推导经典与量子的 crossover 条件，并计算稀疏经典输出的描述长度。

  7. 验证、payoff oracle 与适用范围——能写出 payoff oracle 的定义与验证近似均衡所需估计的两个量，并说明结论为何不能推广到一般和博弈。

  8. Matching Pennies 实例——能在具体 \(2\times2\) 零和博弈上计算纯策略 payoff 向量、均衡、博弈的值与 gap 通式，并据此解释策略误差与 gap 的关系。

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}\)）。下面先把经典部分讲透，再看量子部分。

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 节会看到，量子验证正是围绕这两个量展开的。

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 界拼起来。

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

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\) 幂次的来源。

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）的关键区别。

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 均衡。这篇算法的结论不能推广过去。

10. 小例子：Matching Pennies

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

\[\begin{split} A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}. \end{split}\]

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

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

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

\[\begin{split} 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). \end{split}\]

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

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

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

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

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

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

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

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

  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 相等"确定。

参考文献