结果族 277：Threshold repetition for entangled games · 学科：Mathematical physics · 验证状态：主结果已 Lean 形式化
监考老师把同一份难题连考 k 遍，学生平均只能蒙对 v 的比例；想靠运气大幅超额发挥？概率随 k 指数级崩塌——这就是”阈值并行重复”。本文把它推广到最难缠的考场：两个可以共享量子纠缠、协同作答且测量方式任意的考生。结论依旧：作弊撑不住指数衰减。
关键词卡片
看个具体例子
数字版定理：
@@M@@D\Pr\bigl[W_k\ge(v+\delta)k\bigr]\ \le\ \exp\Big(-\frac{\kappa_0\,\delta^5}{1+\log d}\ k\Bigr),@@
对一切有限维联合策略一致成立（d 是双方答案表大小之积），对策略取上确界后依然成立，速率不依赖问题分布、问题表大小与策略维度。代入 v=0.9、δ=0.1、d=4：指数率正比于 @@M@@10^{-5}/2.4@@，每多考一局都在为衰减”充值”；v=0 时该概率干脆恒为零。固定问题分布时，δ 的次数还能从五次升到三次。
为什么值得关心
错误放大是密码学与复杂性理论的发动机。此前的指数衰减结果要么限于特殊博弈类型，要么需要修改问题分布的”锚定”操作；一般纠缠博弈的阈值版本补齐后，量子验证器的可靠性放大有了通用工具。
已 Lean 形式化
第一级台阶
导读里”监考老师连考 k 遍”的场景先换算成对象与操作：对象是一场问答博弈——裁判按选定分布向两位不能通信的考生各发一问，两人凭赛前共享的量子关联分别作答，裁判按判定规则验收；操作是把同一博弈独立地连玩 k 次，考生可以对收到的整串问题做任意的联合量子测量、协同组织 k 份答案。要问的是：单局最高胜率不到满分时，k 局里获胜占比超过”单局值加固定增量”的概率能有多大。
第二级台阶
用本科术语精确化：博弈由问题集、答案集、问题分布与接受谓词给出；纠缠策略是共享态加两组测量（POVM，即分解单位算子的正算子族），纠缠值 ω*(G) 是一切有限维策略胜率的上确界。k 次重复中记各局胜利指示变量之和为 W_k；阈值事件即 W_k 超过 (v+δ)k。指数集中不等式断言此类偏离事件的概率随 k 指数衰减。
第三级台阶
定理在此语境陈述：存在普适常数，对一切纠缠值 v<1 的有限二人一轮博弈、一切 0<δ<1−v 与 k≥1、一切有限维联合策略，阈值事件概率不超过 exp(−κ₀δ⁵k/(1+log d))，其中 d 为双方答案表大小之积。”问题分布可任意相关、可含零概率项”是最一般的设定；”对策略一致、速率不涉问题表大小与策略维度”挡住了靠增大维度或改造分布作弊的路。固定问题分布时还有显式的 δ 三次方速率可择优取用；两侧推论则把完备性与可靠性同时放大——错误放大发动机就此装上一般纠缠博弈。
证明了任意有限二人一轮博弈的阈值并行重复 (threshold repetition) 定理：只要纠缠值 (entangled value) @@M@@v<1@@，在 @@M@@k@@ 次独立重复中获胜占比超过 @@M@@v+\delta@@ 的概率便对一切有限维联合策略一致地按 @@M@@\exp(-\Omega(\delta^5 k/(1+\log d)))@@ 指数衰减，且允许任意相关问题分布——一般纠缠博弈的阈值错误放大由此实现。
并行重复 (parallel repetition) 问的是：把一个验证者博弈 (game) 重复 @@M@@k@@ 次，作弊者的成功概率能否随 @@M@@k@@ 指数下降？Raz（1998）对经典博弈证明了”全胜”情形的指数衰减，Rao（2011）进一步证明了更强的”阈值”版本：胜利占比超过单局值任意固定增量的概率指数小，这是复杂性理论与密码学中错误放大的标准手段。纠缠博弈允许两个不通信的玩家共享量子态，重复时还可使用任意联合 POVM 测量，各局胜利高度相关，经典信息论论证随之失效。此前已知结果都带结构性限制：XOR 博弈（Cleve–Slofstra–Unger–Upadhyay 2008，完美重复）、唯一博弈 (unique games，Kempe–Regev–Toner 2010)、投影博弈 (projection games，Dinur–Steurer–Vidick 2015)、自由博弈 (free games) 等；对完全一般的博弈，Yuen（2016）只得到多项式衰减，Bavarian–Vidick–Yuen 的指数定理则需”锚定” (anchoring)——向博弈添加问题、从而改变问题分布。近著《Ten Advances》第 6 章与 Song（2026）相继对任意博弈的”全胜”事件给出指数与三次方衰减，但一般博弈的阈值版本始终缺位，本文补上这一环。
主定理（定理 1.1）：存在普适常数 @@M@@\kappa_0>0@@，对任意有限二人一轮博弈 @@M@@G@@（布尔接受谓词），设其纠缠值 @@M@@v=\omega^*(G)<1@@，@@M@@d=|\mathcal A||\mathcal B|@@ 为双方答案集大小之积。则对一切 @@M@@0<\delta<1-v@@、@@M@@k\ge 1@@ 及任意有限维联合策略（问题分布 @@M@@\mu@@ 可相关、允许零概率项与不连通支撑），
@@M@@D\Pr\bigl[W_k\ge\lceil(v+\delta)k\rceil\bigr]\le\exp\!\left(-\frac{\kappa_0\delta^5}{1+\log d}\,k\right),@@
其中 @@M@@W_k@@ 是 @@M@@k@@ 局中的获胜局数。不等式对策略取上确界仍成立；速率不依赖问题分布、问题表大小与策略维度。
固定分布的三次方界（第 5 节推论）：以 @@M@@\mu@@ 的正概率问题对为顶点、共享一个问题的顶点相邻构成图，记其连通分量为 @@M@@H_j@@，令 @@M@@\kappa_\mu=8\max_j(|H_j|-1)/\mu_{j,\min}@@，则同一事件的概率不超过 @@M@@\exp\bigl(-\delta^3 k/(16384(1+\kappa_\mu)(1+\log d))\bigr)@@：对固定 @@M@@\mu@@，@@M@@\delta@@ 的次数由五次升为三次，两个界可择优取用。当 @@M@@v=0@@ 时文中还证得该概率恒为零。
两侧错误放大（第 6 节推论）：设 @@M@@\omega^*(G)\ge c@@ 与 @@M@@\omega^*(G)\le s@@（@@M@@0\le s<c\le1@@，@@M@@\Delta=c-s@@），以阈值 @@M@@t=(c+s)/2@@ 判定的重复博弈 @@M@@H_k@@ 同时放大两侧：完备性至少 @@M@@1-e^{-\Delta^2k/8}@@，可靠性至多 @@M@@e^{-\kappa_0(\Delta/2)^5k/(1+\log d)}@@，且不增加玩家数、轮数或通信。
全文脊柱是一条”条件化 ⇒ 阈值”的转移命题：若某条件化估计在预算 @@M@@T\le\delta/4@@ 内有效——即当测试集 @@M@@C@@ 的条件化成本 @@M@@\tau=(\log(1/p_C)+|C|\log d)/(k-|C|)\le T@@ 时，条件于”@@M@@C@@ 内全胜”后其余坐标的平均胜率不超过 @@M@@v+\delta/4@@——则阈值事件概率不超过 @@M@@\exp(-\delta Tk/(16(1+\log d)))@@。它把”用哪种条件化技术”与”如何导出集中不等式”彻底解耦。
转移命题用纯经典反证法。先假设上尾概率不低于 @@M@@e^{-ck}@@；再对 @@M@@[k]@@ 均匀有放回地抽取约 @@M@@ck@@ 个下标作为测试集。一个一阶矩论证（只涉及二元胜利指示变量的联合分布，不需要任何独立性）保证存在一个固定测试集 @@M@@C@@：其全胜概率 @@M@@p_C@@ 不太小，且条件于此事件后总胜数仍大概率超过 @@M@@(v+\delta/2)k@@，折算得其余坐标的条件平均胜率至少 @@M@@v+7\delta/16@@；另一方面 @@M@@C@@ 足够短、@@M@@p_C@@ 足够大，使成本 @@M@@\tau(C)<T@@，条件化估计却给出至多 @@M@@v+\delta/4@@，矛盾。此论证只覆盖足够大的 @@M@@k@@；对短博弈，取 @@M@@N@@ 份独立张量拷贝拼成长博弈，”每块都超阈值”蕴含全局超阈值，由 @@M@@p_H^N\le e^{-cNk}@@ 解出 @@M@@p_H\le e^{-ck}@@，从而同一速率无遗漏地覆盖一切长度。
主定理只需把 Song（2026）的条件化估计（误差 @@M@@B_4\tau^{1/4}@@，常数普适）代入转移命题，取 @@M@@T=(\delta/4B_4)^4@@。三次方界则完全不借助 Song 的采样器：先用预解式纯化 (resolvent purification) 把条件化产生的一族正算子实现为公共有限维空间中的向量族（@@M@@\mathcal F_T^*\mathcal F_T=T@@），配套的算子 Jensen 不等式把向量间平均平方距离控制在算子熵差之内，传输后的 POVM 还精确保持答案概率；再按固定顺序逐坐标暴露问题——第 @@M@@i@@ 个坐标之前暴露 Alice 的问题、之后暴露 Bob 的——移动分界点张出两条熵望远镜 (entropy telescope)，总代价至多 @@M@@2p\tau@@，于是依赖双方问题的条件向量被两个”单问题可描述”的向量近似；最后在每个支撑连通分量内选定根 (root) 问题，把该分量全部条件向量统一替换为根处的向量，沿支撑图路径用 Cauchy–Schwarz 累积误差（至多 @@M@@\kappa_\mu p\tau@@），并以共享旗标的直和态构造出分量博弈的合法策略，配合相对熵与 Pinsker 不等式控制条件化后分量权重的漂移。合并得条件化误差 @@M@@O_\mu(\sqrt\tau+\tau)@@，取 @@M@@T\asymp\delta^2@@ 即得三次方速率。
本文主结果已由 Lean 形式化证明（见结果族 277 文档 lean/docs/277.md），在这批 OpenAI 手稿中属验证等级最高的一类。它与姊妹篇构成递进链条：《Ten Advances》第 6 章提供预解式纯化与条件化机器，Song（2026）提供平滑采样器与条件化估计，本文新增的转移命题把前两者升级为阈值结论，各篇互为印证。依 OpenAI 官方声明，未经形式化的结果可能有问题，引用未进入 Lean 部分的具体常数时应以论文原文与社区核验为准。
问 1：证明里最承重的一步是什么？
答：第 2 节的”条件化 ⇒ 阈值”转移命题。它假设条件化估计在预算 τ≤T 内把其余坐标平均胜率压在 v+δ/4，就输出阈值概率 ≤ exp(−δTk/(16(1+log d)))。反证法只对二元胜利指示的联合律做一阶矩抽样（有放回抽约 ck 个下标），不需要任何独立性——这把”用哪种条件化技术”与”如何集中”彻底解耦。短博弈靠独立张量拷贝补齐，速率无缝覆盖一切 k。
问 2：阈值版本比”全胜”版本到底多买了什么？
答：全胜事件只是阈值事件的子集；错误放大的真实场景是诚实策略偶尔输几局——只放大全胜无法容忍任何单局失败。Rao 2011 年对经典博弈证明阈值版是标准手段；本文把它带进任意纠缠博弈，且第 6 节推论直接给出完备性、可靠性两侧同时放大（阈值取 (c+s)/2）。
问 3：与 Yuen 2016、Bavarian–Vidick–Yuen 2022 相比真正的新意是什么？
答：Yuen 对一般博弈只得多项式衰减；BVY 的指数定理须”锚定”——往博弈里加问题、从而改掉给定的问题分布。本文保持原分布不变，对任意相关问题分布（含零概率项与不连通支撑）拿到指数阈值界；相对《Ten Advances》第 6 章与 Song 2026 的”全胜”结果，补的正是阈值这一环。
问 4：δ 的五次方从哪来？三次方界又为什么依赖分布？
| 答：五次方直接由 Song 条件化估计的 τ^{1/4} 误差经转移命题转化而来（取 T=(δ/4B₄)^4）。三次方界不借 Song 的采样器，改用自建的预解式纯化＋双熵望远镜＋按支撑连通分量取根，误差 O_μ(√τ+τ)，取 T∝δ² 得三次方——但常数经 κ_μ=8max_j( | H_j | −1)/μ_{j,min} 依赖固定分布。两界对同一策略都成立，可择大者用。 |
问 5：速率为何能不依赖问题分布与策略维度？
| 答：τ 的分子只计入条件事件稀有度 log(1/p) 与测试答案串数 | C | log d，答案表大小 d 是唯一进入速率的组合量；对策略取上确界仍成立，故无穷维极限也无隙可乘。v=0 时文中证得该概率恒为零（均值界引理），比指数界更彻底。 |
问 6：AI 生成证明最可能出错的模式？这里如何对冲？
答：典型风险是多层”暴露— telescope—取根”构造中常数累积。对冲：主结果已 Lean 形式化（本批验证等级最高的一类，见 lean/docs/277.md）。但注意 Song 的条件化估计是外部输入，若其引理不在形式化范围内，五次方速率的常数 κ₀ 仍是纸面值；论文也未给出 κ₀ 的具体数值。
问 7：下游谁受益？
答：量子密码与验证理论： 一般博弈的阈值错误放大让量子验证器的可靠性放大有了通用工具，不再须改造问题分布或限制谓词结构；复杂性理论中把博弈硬度转化为重复硬度（Rao 式论证）的量子版由此齐备；两侧放大推论可直接嵌入协议的完备—可靠分析。
总评
把经典世界标准配备的阈值并行重复完整搬进最一般的纠缠博弈，转移命题是漂亮且可复用的解耦装置，加 Lean 形式化背书；最大风险在外部引用的 Song 估计与未显式化的普适常数。