资料快照:2026-10-07 · 中文研究导读

274|常数深度量子电路不能算奇偶性:浅电路的能力边界

官方问题族 274;本版含 2 篇稿件。以下为稿件结论的解释,未完成独立证明认证。来源版本:adc7f1241b42,核对日期:2026-10-07。

A. 问题是什么

奇偶函数为 PARITY⁡(x)=x1⊕⋯⊕xn\operatorname{PARITY}(x)=x_1\oplus\cdots\oplus x_n。每一位都能影响结果,所以它是研究信息是否能在少量电路层内全局汇聚的典型问题。Moore 在 1999 年提出量子版常数深度电路类 QAC0\mathrm{QAC}^0 的奇偶性猜想。

该电路允许任意单比特门和任意多控制比特的 Toffoli 门,辅助比特数为输入规模的某个多项式,各层门的支撑不重叠。它已经比只有几何局域两比特门的固定深度电路强,因此不能只用普通空间光锥大小来完成证明。2024 年的部分进展得到近线性辅助空间区间的下界。

B. 稿件结论

本族两篇稿件分别给出投影局域化路线与轨道剪枝路线。声称对任意固定深度 dd、任意固定多项式次数 c≥1c\ge1 和任意固定优势 ε>0\varepsilon>0,当 nn 足够大时,使用至多 ncn^c 个总比特的此类电路不可能满足

Pr⁡[输出=PARITY⁡(x)]≥12+ε对所有 x∈{0,1}n.\Pr[\text{输出}=\operatorname{PARITY}(x)] \ge\frac12+\varepsilon \qquad\text{对所有 }x\in\{0,1\}^n.

辅助比特从 ∣0⟩|0\rangle 开始,最后只测量一个输出比特,其他寄存器可任意丢弃。允许保留垃圾使结论比只排除完全清理输出的算法更有意义。目录还指出通过既有归约可得到严格多数函数的对应障碍。

C. 历史资料核验的一处陷阱

搜索会遇到题为 Low-degree approximation of QAC⁰ circuits 的 2024 年预印本,其摘要仍写着已经解决问题。但 arXiv 当前记录明确标记撤稿,并说明 Lemma 2.1 不正确。不能只读搜索摘要就据此判断该问题早已解决。本报告没有把那份撤回的证明作为成立的历史结果。

D. 对物理研究的价值及边界

**潜在积极影响:**明确深度、辅助空间与全局信息处理之间的交换关系,帮助评估浅量子线路能否完成某类关联计算,也为状态制备和学习量子线路的下界方法提供工具。

它不是“量子计算机不能计算奇偶性”:更深的电路当然可以。也不能直接转化为任意硬件的最小运行时间;无界扇出门、中途测量、经典反馈、预先共享的纠缠辅助态等会改变模型,必须分别比较。本族两篇虽都出现在形式化目录中,本报告未运行 Comparator,也未独立检查形式命题是否逐项覆盖其物理电路语义。

原稿及配套材料

返回总览 · 来源与核验记录