结果族 274：Parity is not in QAC0 · 学科：Mathematical physics · 验证状态：主结果已 Lean 形式化
判断一排开关里”按下的个数是奇是偶”（奇偶性），你必须看清每一个开关，任何偷懒的速算都会露馅。这篇论文证明：即使借助量子魔法——常数深度、多项式个量子比特、能一次摸遍所有输入的巨型门——也没有固定优势能算对奇偶性。Moore 1999 年的猜想被正面解决。
关键词卡片
看个具体例子
画出一个这样的电路：所有输入汇入一个巨型 Toffoli 门，最后只测一个输出比特。
数字版定理：对任何深度 ≤ d、总比特 ≤ nᶜ 的此类电路，必存在输入 x，使其答对 parity(x) 的概率 @@M@@<\tfrac12+\varepsilon@@。取 ε=1/6：成功率连常见的 2/3 门槛都够不着。此前最好的结果都要限制辅助比特数量或固定纠缠深度，本文一举覆盖任意固定多项式资源下的全部固定深度。
为什么值得关心
奇偶性是浅电路的试金石：它一倒，严格多数判决、Dicke 态制备等一串对称任务连带倒下，量子浅电路的真实能力边界由此划定。
已 Lean 形式化
第一级台阶
导读里”数一排开关必须看清每一个”的类比先换算：对象是一串输入比特和一台按层搭建的量子电路，每层里的门各自管一小撮或一大片比特、互不重叠；操作是让初始全零的工作比特陪跑，电路跑完后只读一个输出比特。任务是判断输入中”1 的个数”的奇偶。”必须看清每一个”翻译过来就是：任何固定深度的这种电路，都做不到对每个输入都有稳定超出一半的答对率。
第二级台阶
| 用本科术语精确化：奇偶函数定义为按位异或 x₁⊕…⊕xₙ。电路类 QAC⁰ 由任意单比特酉门与无界元 Toffoli 门（任意多个控制位的受控翻转）组成，深度为常数 d、总比特数不超过 n 的固定幂；辅助比特初始为 | 0⟩，允许纠缠、允许留下任意垃圾。所谓”以优势 ε 算出”，指对每个输入 x 答对概率至少 1/2+ε。证明的核心工具是算子范数——衡量一个线性变换最大拉伸倍数的量。 |
第三级台阶
定理在”测量输出”这一最宽松模型下陈述：固定 d、比特数指数 c 与优势 ε，n 充分大时不存在上述电路以 1/2+ε 优势算出奇偶。”深度常数、比特数多项式”挡住了靠规模暴力取胜；”无中间测量、无后选择、无原生扇出门”排除了已知会翻盘的额外原语。结构核心是局部化定理：从乘积投影条件出发、经电路共轭后跳到大量失配状态的转移范数不超过 e^{−N^s}，且对一切电路、投影一致成立——输出零概率的奇偶傅里叶系数被压到零，与固定优势所需的上界矛盾。
本文证明 QAC⁰——常数深度、多项式总比特、由任意单比特门与无界元数 Toffoli 门组成的量子电路——无法以任何固定正优势算出奇偶性，正面解决 Moore 1999 年的奇偶性猜想（测量输出模型），并连带排除严格多数判决等对称任务。
奇偶函数 @@M@@\parity(x)=x_1\oplus\cdots\oplus x_n@@ 是检验浅电路能否整合全局信息的试金石：答对它就必须让每个输入都影响到输出。经典电路复杂度理论的起点正是 @@M@@\mathrm{AC}^0@@ 上的奇偶下界（Furst–Saxe–Sipser 与 Ajtai，1983–1984；Håstad 1986 的切换引理给出近最优指数界）。1999 年 Moore 提出量子类比 @@M@@\QAC@@：允许任意单比特酉门和任意元数的 Toffoli 门，但每层门的支撑两两不交，并猜想它无法实现相干奇偶／无界扇出 (fanout)。困难有二：一个 Toffoli 门可一次触碰全部输入，逆向光锥论证完全失效；量子辅助 (ancilla) 比特可以纠缠、可以留下任意垃圾。此前最好的结果（Anshu–Dong–Ou–Yao 2025、Dong–Ou–Yao 2025）仍把辅助比特数限制在 @@M@@\widetilde O(n^{1+2^{-d}})@@，Joshi–Tal–Vasconcelos–Wright 等则固定纠缠深度，均未覆盖任意固定多项式资源下的全部固定深度。
奇偶下界定理：固定深度 @@M@@d\ge0@@、指数 @@M@@c\ge1@@ 与优势 @@M@@0<\varepsilon\le1/2@@。当 @@M@@n@@ 充分大时，任何深度 @@M@@\le d@@、输入 @@M@@n@@ 比特、总比特数 @@M@@\le n^c@@、由任意单比特酉与无界元 Toffoli 门构成的电路，必存在输入 @@M@@x@@ 使其答对 @@M@@\parity(x)@@ 的概率低于 @@M@@1/2+\varepsilon@@。辅助比特初始为 @@M@@\ket0@@、只测量一个输出比特、其余寄存器任意丢弃——这是最宽松的测量输出 (measured-output) 模型。取 @@M@@\varepsilon=1/6@@ 即常见的成功阈 @@M@@2/3@@，故 @@M@@\mathrm{PARITY}\notin\QAC@@。核心结构定理是乘积投影的局部化 (localization)：对失配计数 (mismatch count) @@M@@M=\sum_{i\in S}(I-\proj{v_i})_i@@ 与任意 @@M@@U\in\cU_d(N)@@，有 @@M@@\|[M\ge N^t]\,U[D=0]U^\dagger[M=0]\|\le e^{-N^s}@@（任意固定 @@M@@0\le s<t@@），且对所有电路与计数一致成立。推论包括：严格多数 @@M@@\operatorname{MAJ}_n@@ 无 @@M@@1/(\log n)^\gamma@@ 的最坏情形优势（结合 Xu–Li 归约）；固定汉明重量均匀叠加态 @@M@@|D_k^n\rangle@@（Dicke 态）与字符串及其按位取反不可被高精度制备；输出期望符号的傅里叶系数在大小 @@M@@\ge n^\delta@@ 的输入子集上总平方权重超快速衰减——一个量子版 LMN 定理。
整个证明绕开光锥，转而控制”从一个乘积条件出发、跳到大量失配状态”的转移范数，且保留投影造成的振幅损失、绝不重新归一化。先把每个 Toffoli 门改写为关于乘积投影 (product projection) @@M@@A@@ 的反射 @@M@@I-2A@@（控制位全为 1、目标位取 @@M@@\ket-@@），电路呈 @@M@@U=(L_dR_d)\cdots(L_1R_1)L_0@@ 的规范形，且取逆后深度不变。第一步证深度 0：共轭一个乘积投影仍是乘积投影，失配数变成独立伯努利变量之和，用关于 @@M@@2^K@@ 的 Markov 不等式得 @@M@@2^{-r}@@ 型尾界。第二步剥层归纳：设投影只固定 @@M@@k@@ 个比特，一层内至多 @@M@@k@@ 个反射与它相遇，在投影两侧展开每个反射，得系数和 @@M@@\le 9^k@@ 的”三投影乘积”项，再用深度 @@M@@d-1@@ 的归纳假设，在三个因子之间插入两档中间失配截断，把每段跳变逐一压住。第三步克服展开代价随支撑指数增长的困难：把任意乘积投影写成第二个计数 @@M@@D@@ 的 @@M@@[D=0]@@，用 Chebyshev 型多项式 @@M@@p@@（@@M@@p(0)=1@@、在正整数谱点上误差 @@M@@\le e^{-N^a}@@、度与加权系数和 @@M@@\le e^{N^u}@@）把 @@M@@D@@ 的幂展开成至多 @@M@@N^k@@ 个小支撑单项式。最巧妙的是算子次序：平方目标范数得 @@M@@\|HQP\|^2=\|HQPQH\|@@，只把最左的 @@M@@Q@@ 替换为 @@M@@p(C)@@，残余误差落在 @@M@@PQ@@ 上，经逆电路共轭后恰好变成”两个计数互换、阈值更高”的同一命题——于是先在更大阈值证 @@M@@\cB_d(t,b)@@，再倒推 @@M@@\cB_d(s,t)@@。尺度链 @@M@@t_{i+1}=2t_i-s_i-3\eta@@ 经 @@M@@O(1/(t-s))@@ 步把阈值推过 1（此时尾投影消失、命题平凡），自后向前逐级归约完成归纳。收官时令 @@M@@B=W^\dagger OW@@，输出零概率 @@M@@p_0(x)@@ 的奇偶傅里叶系数恰是互补 Hadamard 乘积态 @@M@@\ket{\xi_h},\ket{\xi_{\bar h}}@@ 间矩阵元的平均；这两态在全部 @@M@@n@@ 个输入比特上失配，局部化迫使每个矩阵元 @@M@@\le e^{-N^s}@@（取 @@M@@0<s<t<1/c@@ 使 @@M@@N^t<n@@），平均趋于零；而逐点正确率 @@M@@\ge1/2+\varepsilon@@ 强迫该平均 @@M@@\ge\varepsilon@@，矛盾。
主定理已通过 Lean 形式化验证（结果族 274）。姊妹篇《Regular trajectories, pruning and quantum parity》给出第二条独立证明：其走”正则轨迹＋剪枝”的状态依赖路线，本文则证一致的算子范数定理、不以任何轨迹假设为前提；两文各自完成多项式估计与奇偶转化，互不引用对方结构定理，构成交叉核验。多数函数、态制备等推论依赖 Xu–Li 与 Gretta–Gupta–Joshi 的归约。仍需留意 OpenAI 官方声明：未经形式化的结果可能存在问题，形式化覆盖之外的具体表述请以社区核验为准。
问 1：证明里最承重的一步是什么？
答：bootstrap 一节的有限阈值链归纳。关键招式是算子次序：平方目标范数得 ‖HQP‖²=‖HQPQH‖，只把最左的 Q 换成 Chebyshev 型多项式 p(C)，残余误差经逆电路共轭后变成”两个计数互换、阈值更高”的同一类命题；尺度链经有限步把阈值推过最大计数 N，命题变平凡，再倒推回来。这个”自引用”结构若有一处指数记账（如系数和 ≤ e^{N^u} 与阈值步长 2t−s−3η 的配合）错位，整个一致性就会塌。
问 2：哪个假设最不能去掉？
答：无原生扇出门、无中间测量与后选择。Høyer–Špalek 2005 已证明常深度扇出门威力巨大；Moore 1999 也指出相干奇偶与扇出经 Hadamard 共轭互换。本文证的是”没有扇出原语时奇偶不可算”，这正是猜想的原意。此外每层门支撑两两不交是量子电路的固有约束，经典 AC⁰ 的任意重用导线不可比。
问 3：与 2025–2026 年的前沿下界相比，真正的新意在哪里？
答：Anshu–Dong–Ou–Yao 与 Dong–Ou–Yao 把辅助比特限制在 Õ(n^{1+2^{-d}})，Joshi–Tal–Vasconcelos–Wright 固定纠缠深度，均未覆盖任意固定多项式资源下的全部固定深度。本文对每个固定深度 d、每个固定多项式 n^c、每个固定正优势给出下界，且允许垃圾任意丢弃的测量输出模型——覆盖面上是干净的收官。
问 4：局部化定理为什么能绕开光锥论证？
答：无界元 Toffoli 可一次触碰全部输入，逆向光锥没有任何限制可用。本文改控”从乘积条件出发跳到大量失配态”的转移范数：展开层内反射为三投影乘积（系数和 9^k），用 Chebyshev 多项式把任意乘积投影写成小支撑单项式之和，保留投影的振幅损失、绝不重新归一化——这两点是经典谱范数近似路线（ADOY）没有做到的。
问 5：AI 生成证明最可能出错的模式？这里如何对冲？
答：此类证明的典型风险在多层归纳的常数与指数簿记。本文有两重对冲：主定理已通过 Lean 形式化验证（结果族 274 标注）；姊妹篇《Regular trajectories, pruning and quantum parity》给出第二条独立证明（状态依赖的轨迹路线），两文互不引用对方结构定理，构成交叉核验。但推论依赖的 Xu–Li 与 Gretta–Gupta–Joshi 归约是否在形式化覆盖内，论文未逐条说明。
问 6：局部化的一致性声明有多强？
答：引言强调估计对电路 U、乘积投影 A、失配计数 M 一致成立，且”未计数寄存器可携带任意内部纠缠态”——这是算子范数表述（而非状态依赖表述）的力量所在；它不依赖任何轨迹假设，正是与姊妹篇的分野。
问 7：下游谁受益？
| 答：量子电路复杂度社区：严格多数判决无 1/(log n)^γ 优势（结合 Xu–Li 归约）、Dicke 态 | D_k^n⟩ 不可高精度制备、量子版 LMN 傅里叶衰减定理（推论：大小 ≥ n^δ 子集上的总平方权重超快速衰减）——浅量子电路的真实能力边界由此划定，并与带阈值门的模型分离。 |
总评
这是 Moore 1999 猜想在最宽松输出模型下的完整解决，乘积投影局部化是可复用的新结构定理，且有 Lean 形式化与独立姊妹篇双保险；剩余风险集中在依赖外部归约的推论部分。