# 279｜固定有限门集的精确量子分解：把成功概率提高到严格的一

> 官方问题族 279；本版含 1 篇稿件。以下为稿件结论的解释，未完成独立证明认证。来源版本：`adc7f1241b42`，核对日期：2026-10-07。

## A. 问题与历史背景

[Shor 算法](https://arxiv.org/abs/quant-ph/9508027)说明整数分解可以在量子计算机上以多项式资源和可放大的高成功率完成。这里问一个更细的问题：能否对每个输入保证输出正确、最坏情况下仍只用多项式门，而且整个算法始终来自一个固定有限门集？

“反复运行直到成功、平均时间多项式”不能保证每条随机分支都有多项式上界；“错误概率任意小”也不等于精确为零。有限门集又限制了可精确实现的旋转角度，不能给每个输入额外供应一个含答案的任意实数门。

## B. 稿件结论

对每个整数 $N\ge2$，令输入长度 $n=\lceil\log_2(N+1)\rceil$。原文声称存在可由经典多项式时间生成的统一量子电路族，在门数与比特数均由固定多项式 $\operatorname{poly}(n)$ 控制的情况下，以概率一输出完整素因子分解，包括重数。

一个固定有限、有限作用元数的门集就足够：NOT、CNOT、Toffoli、Hadamard、$\operatorname{diag}(1,i)$，它们的逆及单控制版本。这里包括受控 Hadamard 等门，不能把定理随意改述成只用 Clifford 门。

结论属于理想电路模型的**精确函数计算**。统一性意味着生成电路的程序无需预先知道 $N$ 的分解；最坏资源界排除了把无界重复藏在“概率一最终结束”里。

## C. 物理和计算意义

**潜在积极影响：**它会展示一个重要量子算法任务可以兼顾精确性、统一性和有限指令集，为研究量子干涉、离散门代数以及精确复杂性类提供新工具。算法结构若能迁移，可能帮助其他代数问题消除理论上的算法失败概率。

不过从普通 Shor 的高成功率到概率一，主要是复杂性理论上的增强；实际设备仍有门误差、退相干和测量误差。定理没有提供“无需纠错”的分解机器，也不自动减少资源常数，更不证明量子计算能高效解决所有 NP 完全问题。

从研究投入看，应先核验固定门集下每个精确子程序、所有测量分支的资源界和统一电路生成，再比较实际门数。对物理学的直接影响较前面的凝聚态与场论条目间接，但它属于官方数学物理分类，因此在本报告中完整保留。

## 原稿及配套材料

- **O279-01** [Exact quantum factoring over a fixed finite gate set](https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026/main.pdf)。形式化目录：未列入。BibTeX 键：`OAI:Exact-quantum-factoring-over-a-fixed-finite-gate-set-September-25-2026`。

[返回总览](../README.md) · [来源与核验记录](../sources.md)