结果族 279：Exact quantum factoring over a fixed finite gate set · 学科：Mathematical physics · 验证状态：暂无形式化证明，请以社区核验为准
量子计算机能快速分解大整数（Shor 算法），但它像掷骰子：每次以很高的概率成功，不中就重来。这篇论文把骰子彻底拿掉：只用一套固定的几种”量子积木”，搭出对每个整数都必然、百分之百输出完整素分解的线路——把”高概率对”升级成”必然对”。
关键词卡片
@@M@@91=7\times13@@@@M@@a^r\equiv1\pmod m@@ 的最小正整数 @@M@@r@@，Shor 算法的核心步骤看个具体例子
先拿 @@M@@N=15@@ 走一遍 Shor 式试验：取 @@M@@a=7@@，它的阶是 @@M@@r=4@@（@@M@@7^4\equiv1\pmod{15}@@），于是 @@M@@a^{r/2}=49\equiv4@@，@@M@@\gcd(4-1,15)=3@@、@@M@@\gcd(4+1,15)=5@@，得 @@M@@15=3\times5@@。
公式卡（数字版定理）：论文的线路族对每个 @@M@@N\ge2@@——包括 @@M@@N=15@@——都以概率恰为 @@M@@1@@ 输出完整分解；门数与量子比特数都不超过 @@M@@n=\max\{128,\lfloor\log_2 N\rfloor+1\}@@ 的某个固定多项式。
为什么值得关心
它厘清了”精确量子计算”的边界：不靠任意角度门、不靠额外输入，固定积木加多项式资源就足以必然正确地分解——尽管多项式很大，并不实用。
暂无形式化证明（AI 结果待核验）
第一级台阶
导读把 Shor 算法比作”掷骰子”：每次大概率成功，不中重来。翻译成半数学语言：对象是一台接收整数 @@M@@N@@ 的量子线路，以及它输出一串比特后被测量的过程；操作是把”成功概率很高”这一性质改造为”成功概率恰好等于一”——骰子不是被扔掉，而是被精确的振幅调整替换。约束是搭线路只许用一套固定的几种量子积木，积木种类不随 @@M@@N@@ 改变。
第二级台阶
用本科计算理论术语精确化。均匀电路族指每个比特长度 @@M@@n@@ 对应一条线路，且线路可由确定图灵机在 @@M@@\mathrm{poly}(n)@@ 时间内生成；多项式时间即门数与量子比特数都被 @@M@@n@@ 的某个固定多项式一致界定。求阶是核心子问题：对模 @@M@@m@@ 的单位 @@M@@a@@，找使 @@M@@a^r\equiv1\pmod m@@ 的最小正整数 @@M@@r@@。振幅放大是把目标分支的振幅经反射精确推到满格的操作——关键在于每一步的旋转角都须由固定门精确合成。
第三级台阶
定理在此语境下陈述：存在多项式时间、多项式规模的均匀量子线路族，门集固定为 NOT、CNOT、Toffoli、Hadamard 门与相位门 @@M@@S@@ 及其逆和单受控版本，对每个 @@M@@N\ge2@@ 以概率恰为 @@M@@1@@ 输出完整素因子分解。”只接收 @@M@@N@@、不许任意角度门、不许额外输入”这些假设各自挡住了三类作弊：运行时定制门参数、预知阶的倍数、外部建议比特——它们恰是此前精确算法赖以成立的宽松条件。结论换用这些术语说：固定积木加多项式资源即可必然正确地分解。论文同时声明多项式非常大，不构成实用改进。
本文构造出多项式时间均匀量子电路族：只用一组固定的有限门集，就能以概率 1 输出任意整数 @@M@@N\ge2@@ 的完整素因子分解，门数与量子比特数均为输入比特长度的多项式——把 Shor 分解算法的”高概率成功”升级为”必然成功”。
整数分解是计算数论的核心问题：给定二进制整数 @@M@@N\ge2@@，求其按非降排列、含重数的素因子列表。Shor 的量子算法实现了多项式时间分解，但只有有界误差（bounded error）：靠”重复直到成功”不能保证最坏情形多项式时间，而把任意角度旋转门近似到越来越高精度，在固定有限门集上也换不来概率为一的正确性。精确量子计算（exact quantum computation）方向已有进展：Mosca–Zalka 构造了精确傅里叶变换，但依赖计算中生成的旋转角；Mosca 的精确分解算法工作在允许运行时获取门参数的广义模型中；Imran 的精确求阶则要求预先提供未知阶的某个倍数——这些额外输入或门参数恰是标准分解问题不提供的。Nishimura 与 Ozawa 关于有限生成均匀电路族的结果也说明，近似通用性不能替代显式门分析。真正的卡点在于：电路只接收 @@M@@N@@、只许一组固定有限门集时，如何同时做到概率 1 正确与最坏情形多项式资源。
定理（论文 Theorem 1.1）：存在多项式时间均匀（uniform）、多项式规模的量子电路族，对每个输入整数 @@M@@N\ge2@@ 以概率 1 输出其完整素因子分解。门集固定且有限：NOT、CNOT、Toffoli、Hadamard 门 @@M@@H@@、相位门 @@M@@S=\operatorname{diag}(1,i)@@，以及它们的逆与单受控版本。门数与量子比特数都被比特长度 @@M@@n=\max\{128,\lfloor\log_2N\rfloor+1\}@@ 的固定多项式一致界定。论文明确声明：多项式参数很大，并非实用的资源改进，也不主张任何经典（确定性或随机）多项式时间分解算法。
证明分三步。第一步把 Shor 式求阶试验改造成”成功概率可精确控制”的试验。对模 @@M@@m@@ 的单位 @@M@@a@@，其乘法阶（multiplicative order）@@M@@r@@ 是使 @@M@@a^r\equiv1\pmod m@@ 的最小正整数；作者把求阶采样中的傅里叶相位 @@M@@e^{-2\pi iz}@@ 换成四分之一整数节点上的分段线性插值 @@M@@g@@：相位寄存器只需 Hadamard 加 @@M@@S@@、@@M@@S^2@@ 相位即可制备 @@M@@\ket{\chi}=Q^{-1/2}\sum_y i^{\lfloor4y/Q\rfloor}\ket{y}@@，受控模移位经相位反冲（phase kickback）给出矩阵 @@M@@A_{k,x}=Q^{-1/2}g(kx/Q)@@（@@M@@Q=B^{16}@@），再用连分数（continued fraction）从观测值 @@M@@k@@ 恢复既约分数标签 @@M@@(d,j)@@。难点是标签上的概率虽可逐点精确计算，求和却要枚举多达 @@M@@d@@ 个剩余类。作者用分片多项式系数上取整构造二进有理（dyadic rational）上估计，其总和借幂和（power sums）公式无需枚举即可精确算出；再叠加三个抽样模式（量子实验、补差额的均匀猜测、补余量），使真阶处每个既约分子的质量恰为 @@M@@\lambda(r)=2^{-\lceil\log_2r\rceil-10}@@，一次试验返回 @@M@@r@@ 的概率恰为 @@M@@\varphi(r)\lambda(r)@@，无需预知 @@M@@r@@ 或其分解。
第二步把试验嵌入递归分解过程，核心辅助数据是出现树（occurrence tree）@@M@@\mathcal{D}(N)@@：根记录 @@M@@N@@ 的素分解，每个奇素数 @@M@@p@@ 挂一个孩子 @@M@@\mathcal{D}(p-1)@@，形似 Pratt 素性证书；素数标签由附录中改造 AKS 得到的确定性素性测试（primality test）验证。由 @@M@@\mathcal{D}@@ 可分解 @@M@@\varphi(m)@@，从而精确回算任意单位的阶。控制器交替使用”列表转移”（抽 @@M@@K=n^5@@ 个随机单位，好列表含有使各素幂分量之阶的二进层次互异的元素）与”阶转移”（@@M@@K@@ 次阶试验）；层次互异时 @@M@@a^{r/2}@@ 在一部分素幂分量为 @@M@@-1@@、其余为 @@M@@1@@，@@M@@\gcd(a^{r/2}-1,m)@@ 即真分裂（Miller–Shor 归约）。每个转移的好输出概率 @@M@@s\ge1-2^{-2n}@@，且可由 @@M@@\mathcal{D}@@ 精确算出；总槽数不超过 @@M@@L=n^{10}@@。
第三步精确化。每个槽以 @@M@@1-2^{-2n}@@ 的概率走普通转移、否则均匀猜一个输出，而”好输出”检验被推迟到运行结束后，用运行自身生成并验证过的 @@M@@\mathcal{D}@@ 回溯计算；二进补全引理保证每槽通过概率恰为 @@M@@z=1-2^{-n}@@，故整体恰为 @@M@@p_*=(1-2^{-n})^{n^{10}}>1/2@@，且在运行前已知。关键论证把”推迟检验”与”真数据即时检验”识别为同一记录运行上的同一事件，既不引入建议（advice），也不以完成为条件。最后用独立舍入把成功概率调到恰 @@M@@1/4@@；一步精确振幅放大（amplitude amplification）——两次符号反射 @@M@@(2\ket{\psi}\bra{\psi}-I)(I-2\Pi)@@——把成功分支放大为范数 1 的纯态，测量必得正确分解，无需任意角度旋转门。
该文暂无 Lean 形式化证明，分段线性相位矩阵、二进上估计与”事件识别”等关键论证均需社区核验。结果族 279 目前仅此一篇手稿，构造自足：求阶试验、分解过程、精确化与素性测试附录四部分互相咬合；引言亦与 Mosca–Zalka、Imran 等先前精确算法明确区分了模型与输入。按 OpenAI 官方声明，未经形式化的结果可能有问题，请以同行评审与社区复核为准。
问 1：证明里最精妙也最脆弱的一步是什么？
（答：是”推迟检验”与”真数据即时检验”的事件识别论证（引言 1.2 节、引理 completion）。好输出检验被推迟到运行结束后，用运行自身生成并验证的出现树回溯计算；关键在于证明这与一条假想的”用真数据即时检验”序列标记同一批记录运行，从而既不引入建议比特、也不以完成为条件。这一步滑一点，整个概率为一的断言就会变成”以完成为条件的一”。）
问 2：为什么”固定有限门集、只接收 @@M@@N@@“这个模型限制不能放松？
（答：因为放松后问题早已被解决：Mosca–Zalka 的精确算法允许运行中计算出的旋转角，Mosca 的广义模型允许运行时获取门参数，Imran 的精确求阶需要预先供应阶的某个倍数。定理的分量恰恰在于同时拿掉门参数与额外输入——这些”方便条件”正是标准分解问题不提供的。）
问 3：与 Shor、Regev、Pilatte 相比真正的新意在哪里？
（答：Shor、Regev 与 Pilatte 的算法都保留非零失败概率；本文把成功概率做成恰好 @@M@@1/4@@ 后用一步标准振幅放大（两次符号反射）推到 @@M@@1@@，无需依赖成功概率的相位旋转。技术核心是分段线性相位插值给出可精确计算的二进有理质量，以及用幂和公式无枚举地精确求和。）
问 4：这个证明最可能以什么方式出错？
（答：精确概率簿记。每个槽的通过概率须恰为 @@M@@z=1-2^{-n}@@，总概率恰为 @@M@@(1-2^{-n})^{n^{10}}>1/2@@，再经独立舍入调到恰 @@M@@1/4@@——链条上任何一个常数不是精确二进有理、任何一个上取整或幂和求和有误，”恰等于”就退化为”约等于”，放大后概率不再是一。这类海量精确算术正是 AI 生成证明的典型风险点，且论文无形式化核验。）
问 5：出现树为什么要跟着分解过程一起递归生成？
（答：树根记录 @@M@@N@@ 的分解，每个奇素数 @@M@@p@@ 挂 @@M@@\mathcal D(p-1)@@，规模多项式；素数标签由附录改造 AKS 得到的确定性素性测试验证。只有靠它才能精确回算任意单位的阶与各转移的好输出概率 @@M@@s\ge1-2^{-2n}@@——概率可精确算出，”推迟检验”才有落点。）
问 6：这个结果对实践或密码学意味着什么？
（答：几乎没有直接意味，论文自己声明多项式参数极大、不构成实用资源改进，也不主张任何经典多项式时间分解算法。它的价值是概念性的：厘清固定门集下精确量子计算的边界——”必然对”不需要任意角度门或额外输入就能多项式达成。）
总评
这是一项模型界定型的构造工作，把精确量子分解从”依赖运行时参数”推进到”固定门集、纯输入 @@M@@N@@“，证明思路自洽且与先前工作切割清晰；最大风险在层层精确常数与事件识别论证的细节，未经形式化与实现验证前应保持谨慎。