结果族 274：Parity is not in QAC0 · 学科：Mathematical physics · 验证状态：主结果已 Lean 形式化
同一座迷宫，换一条全新的走法再次确认”此路不通”。这是同一猜想（QAC⁰ 电路算不对奇偶性）的第二篇独立证明：常数深度的量子电路无论配备多少辅助比特，都整合不了全局信息。新招叫”正则轨迹＋剪枝”——先删掉几乎不起作用的门，再追踪量子态逐层演化时”失配数”的指数尾巴。
关键词卡片
看个具体例子
数字版定理：对任何深度 d、总比特数 ≤ C(n+1)^k 的电路，存在输入 x 使
@@M@@D\Pr[\text{答对}\ \mathrm{Parity}_n(x)]\ <\ \tfrac{1}{2}+\varepsilon .@@
| 配套的具体下界：在适用区间 n^δ ≤ k ≤ n/2 内，制备 Dicke 态 | D_k^n⟩ 必有迹距离误差 @@M@@>1/(80k)@@；比如 k=√n 时误差必大于 @@M@@1/(80\sqrt n)@@。剪枝的账目也很干净：保留投影概率 ≥ m⁻⁶ 的门，删除的总扰动不超过 2tm⁻²——垃圾清理后照样翻车。定理在最宽松的测量输出模型下成立：输入可被破坏、非输出寄存器可留任意垃圾、只测一个输出比特。 |
为什么值得关心
两条完全独立的证明路线殊途同归，互为交叉核验，加之主定理已通过机器验证，这个量子复杂度的地标异常牢固。
已 Lean 形式化
第一级台阶
导读里”同一座迷宫换一条走法再确认此路不通”的类比先落地：迷宫还是那座——常数深度、多项式规模、带巨型门的量子电路，任务还是判断输入的奇偶。新走法换成盯住”量子态本身”：让态逐层穿过电路，随手数一数有多少量子比特偏离了指定基准；再随手把几乎不起作用的门删掉，删完发现态的”偏离数”始终拖着一条指数级细的尾巴——正是这条尾巴掐死了奇偶。
第二级台阶
精确化：把广义 Toffoli 门改写为关于乘积投影 P 的反射 I−2P。对每个乘积测试定义激发计数 H：它统计有多少位点偏离指定单比特态，是可观测的自伴算符。正则轨迹指逐层演化序列满足——任取一层中少量反射，其测试位点的合计失配在进入该层的状态上有指数衰减的尾界。剪枝规则则保留投影概率不低于 m^{-6} 的反射（m 为总比特数），被删门对状态的扰动每层不超过 2m^{-2}。
第三级台阶
定理在测量输出模型下陈述：固定正整数 d、k、C 与优势 ε，n 充分大时，任何深度至多 d、总比特数至多 C(n+1)^k 的电路必有输入 x，在其上答对奇偶的概率严格小于 1/2+ε。”每层支撑两两不交、无中间测量与后选择、门可依赖 n 但不可依赖 x”框住了电路的真实权限。收官论证是：把输入拷贝进参考寄存器的门必在剪枝中幸存，把符号算符穿过拷贝层后得到恰有 n 个激发的向量，而 n 远大于多项式规模的任何幂次门槛 m^h——尾部界把带符号期望压到指数小，与固定优势所需的界矛盾。
本文用”正则轨迹＋剪枝”的新框架独立证明：常数深度、多项式总比特的 QAC⁰ 电路无法以任何固定优势计算奇偶性，从而排除 Moore 猜想中的无界扇出，并连带给出态制备与对称函数的一批下界。
@@M@@\QAC@@ 允许任意单比特酉门和任意元数的广义 Toffoli 门，但每层门的支撑两两不交——于是”一条导线能否同时驱动任意多个门”，即无界扇出 (fanout)，成为实质问题。Moore 1999 年猜想该模型实现不了扇出；由于 Hadamard 共轭交换 CNOT 的控制与目标，扇出 @@M@@F_n@@ 与相干奇偶变换 @@M@@\ket{y,b}\mapsto\ket{y,b\oplus\Parity_n(y)}@@ 互相等价，猜想亦称奇偶性猜想。此前的下界或限制辅助比特数（Anshu–Dong–Ou–Yao 2025 等的 @@M@@\widetilde O(n^{1+3^{-d}})@@ 量级），或固定纠缠深度（Joshi–Tal–Vasconcelos–Wright、Kintali），没有一个能同时覆盖所有固定深度与所有固定多项式资源。本文在最宽松的测量输出 (measured-output) 模型——输入可被破坏、非输出寄存器可留任意垃圾、只测一个输出比特——下补齐这一缺口。
定理：固定正整数 @@M@@d,k,C@@ 与 @@M@@0<\varepsilon\le1/2@@，存在 @@M@@n_0=n_0(d,k,C,\varepsilon)@@，使得 @@M@@n\ge n_0@@ 时，任何深度 @@M@@\le d@@、总比特数 @@M@@\le C(n+1)^k@@ 的电路必有某个输入 @@M@@x@@，在其上答对 @@M@@\Parity_n(x)@@ 的概率严格小于 @@M@@1/2+\varepsilon@@。由此，常数深度多项式资源无法实现扇出 @@M@@F_n@@：给它配两层单比特门和一个零目标比特即得奇偶计算，与定理矛盾；这同时否定 Moore 原始的”辅助比特须归零”表述。态制备方面，定义保留态的 felinity @@M@@2\sum_y p_y p_{\bar y}@@（@@M@@\bar y@@ 为按位取反，@@M@@p_y@@ 为对角概率），则每个固定深度与多项式比特界下最终 felinity @@M@@<n^{-A}@@；且对 @@M@@n^\delta\le k\le n/2@@，Dicke 态 @@M@@|D_k^n\rangle=\binom nk^{-1/2}\sum_{|y|=k}|y\rangle@@ 的制备必有迹距离误差 @@M@@>1/(80k)@@。结合 Xu–Li 的归约，严格多数及更广的对称函数同样没有 @@M@@1/(\log n)^\gamma@@ 的最坏情形优势。
方法整体是状态依赖的轨迹分析。先把广义 Toffoli 视为关于乘积投影的反射 @@M@@R_g=I-2P_g@@；对每个”乘积测试”定义激发计数 (excitation count) @@M@@H_A@@，它统计有多少位点偏离指定单比特态。核心概念是正则轨迹 (regular trajectory)：逐层演化时，任取一层中至多 @@M@@m^b@@ 个反射，它们测试位点的合计失配在进入该层的状态上有指数衰减的尾部 @@M@@\|\one_{H_S\ge m^h}\xi_{j-1}\|\le e^{-m^p}@@。先构造两类 Chebyshev 滤波多项式：零滤波 @@M@@Q@@ 在整数谱点上逼近零投影（@@M@@Q(0)=1@@、精度 @@M@@e^{-m^q}@@、度与全局范数 @@M@@\le e^{m^r}@@）；尾探测器 @@M@@T@@ 处处非负、在 @@M@@[m^h,m^u]@@ 上 @@M@@\ge1/4@@ 而在低段 @@M@@\le e^{-m^s}@@——非负性保证二次型中不会出现外部抵消。在此基础上证三个结构命题：其一，低度算子沿正则轨迹传播，度数指数只损失任意小的固定量，依据是”度数 @@M@@\ell@@ 的算子至多改变激发数 @@M@@\ell@@“这一局部性原理；其二，尾部传输引理比较两条正则轨迹，把两个多项式分别放在内积的两侧，使其巨大的全局范数各自被对方的尾界吸收；其三，投影插入命题说明在输出端插入任意乘积投影再反向演化仍保持正则，由此得到关键推论：从乘积初态出发，@@M@@\|\one_{H_0\ge m^h}W^\dagger P_BW\psi_0\|\le e^{-m^p}@@。但一般电路未必正则，于是引入剪枝 (pruning)：逐层用”剪后前缀”的真实状态作判断，保留投影概率 @@M@@\|P_g\psi\|^2\ge m^{-6}@@ 的反射；被保留的层自动正则，被删的门对状态的扰动每层 @@M@@\le 2m^{-2}@@，故剪后电路 @@M@@W@@ 与原电路在初态上只差 @@M@@2tm^{-2}@@。最后是奇偶收官：附加 @@M@@n@@ 比特参考寄存器，用一排 CNOT 把输入拷贝进去（其投影概率为 @@M@@1/4@@，必被保留），初态取均匀相干叠加 @@M@@\psi_0=\ket{+}^{\otimes n}\ket0^{\otimes a}\ket0_R^{\otimes n}@@。逐点正确性把带符号期望 @@M@@\ip{\Phi}{Z_RP_B\Phi}=2^{-n}\sum_x(-1)^{|x|}p_x@@ 压到 @@M@@\le-\varepsilon@@，剪枝几乎不改变它。再把 @@M@@Z_R@@ 穿过被保留的拷贝层得 @@M@@Z_IZ_R@@，其作用于 @@M@@\psi_0@@ 恰把每个输入因子 @@M@@\ket+@@ 翻成 @@M@@\ket-@@，新向量相对 @@M@@\psi_0@@ 的失配数恰为 @@M@@n@@。由于总比特数 @@M@@m@@ 多项式依赖于 @@M@@n@@，可选 @@M@@m^h=o(n)@@，使该向量落入高失配谱段，前述尾推论把配对 @@M@@|\ip{\Omega}{Z_RP_B\Omega}|\le e^{-m^p}@@ 逼到零，与 @@M@@\le-\varepsilon@@ 矛盾。
主定理已完成 Lean 形式化（结果族 274），滤波、传输、剪枝等结构引理均自含于本文，不依赖姊妹篇。姊妹篇《Product-projection localization and the QAC0 parity lower bound》以一致的算子范数局部化定理给出另一条独立证明，两条路线各自完成全部环节、互不引用，显著降低单一路线出错的风险。多数与态制备推论引用 Xu–Li、Gretta–Gupta–Joshi 及 Grier–Morris–Wu 的归约。按 OpenAI 官方声明，未经形式化的结果可能有问题，形式化范围之外的细节请以社区核验为准。
问 1：这条证明路线里最承重的一步是什么？
答：尾部传输引理（tail-transport lemma，第 5 节）。它比较两条正则轨迹：一个多项式在起点端探测尾巴，另一个在终点端逼近乘积投影，二者放在内积的两侧，使各自巨大的全局范数被对方的尾界吸收。低度传播与投影插入（命题一、二）都靠它支撑；若两侧的指数参数没有对齐，”度数只损任意小固定量”就会失效。剪枝账目（保留阈值 m^{−6}、每层扰动 2m^{−2}）是第二承重点。
问 2：为什么走状态依赖路线，而不像姊妹篇那样证一致的算子范数定理？各付出什么代价？
答：状态依赖的好处是滤波多项式只需在实际到达的态上表现良好，无须控制远离计数范围的坏范数；代价是必须先解决”一般电路不正则”——剪枝规则用剪后前缀的真实状态作判断，强制幸存层正则。姊妹篇的一致范数定理更强但更贵；两条路线各自完成全部环节、互不引用，这是罕见的双保险设计。
问 3：哪个假设最不能去掉？
答：无原生扇出、无中间测量与后选择（第 2 节明列）。Høyer–Špalek 已示扇出之威力；且由 Hadamard 共轭，扇出与相干奇偶互换——定理因此同时否定 Moore 原始”辅助比特须归零”表述。门单位成本不随元数增长是模型定义，不算可去假设。
问 4：与前人下界相比覆盖面强在哪？
答：Anshu–Dong–Ou–Yao、Dong–Ou–Yao 限制辅助比特在近线性；Joshi–Tal–Vasconcelos–Wright 与 Kintali 固定纠缠深度（且无规模界）。本文对每个固定深度、每个固定多项式总比特界、每个固定正优势同时成立，并允许输入被破坏、垃圾任意丢弃——覆盖上是完整缺口补齐。
问 5：奇偶收官里为什么拷贝门必在剪枝中幸存？
| 答：一排 CNOT 把均匀相干叠加的输入拷入参考寄存器，投影概率恰为 1/4，远超保留阈值 m^{−6}；于是把参考寄存器的符号算符 Z 穿过拷贝层后，每个输入因子 | +⟩ 翻成 | −⟩，相对初态恰有 n 个激发。总比特 m 只是 n 的多项式，可选 h 使 m^h=o(n)，该向量落入高激发谱段，推论（乘积尾巴）把带符号期望逼到 e^{−m^p}，与逐点正确性所需的 ε 矛盾。 |
问 6：AI 生成证明最可能出错的模式？本文如何对冲？
答：典型风险是多层结构的常数簿记（m^{−6}、2m^{−2}、1/(80k) 这类具体数字）。对冲有三：主定理已 Lean 形式化（结果族 274）；全部结构引理自含，不依赖姊妹篇；姊妹篇给出独立第二证明。值得注意的是本文脚注披露所引 JTVW 与 Kintali 两文亦有 LLM 参与——引用链的可靠性本身成了新变量，论文未进一步讨论。
问 7：下游谁受益？
| 答：量子电路复杂度与态制备理论：felinity 小于 n^{−A}、Dicke 态 | D_k^n⟩ 制备误差大于 1/(80k)（n^δ≤k≤n/2）、经 Xu–Li 归约严格多数无 1/(log n)^γ 优势——浅量子电路的全局信息整合能力被系统性封顶。 |
总评
与姊妹篇构成 Moore 猜想的双独立证明，正则轨迹加剪枝的状态依赖框架自有方法论价值，且有 Lean 形式化背书；剩余风险在形式化覆盖之外的具体常数与依赖外部归约的推论。