量子求阶与因子后处理（Order Finding）¶

English · 简体中文

类别 C1 · 模块 oracq.algorithms.basics.number_theory · 阶段 —

概述¶

对与模数 \(m\) 互素的乘数 \(a\)，求满足 \(a^r \equiv 1 \pmod m\) 的最小正整数 \(r\)（阶）。实现依据 Shor 的构造（arXiv:quant-ph/9508027）：把模乘置换 \(U_{a,m}\) 作用于本征态 \(|1\rangle\) 的叠加分量，对相位寄存器做量子相位估计，读出 \(s/r\) 的近似分数，再由经典连分数还原候选阶并尝试分解 \(m\)。阶为偶数且 \(a^{r/2} \not\equiv -1 \pmod m\) 时，\(\gcd(a^{r/2} \pm 1, m)\) 给出非平凡因子。

接口与输入模型¶

order_finding(multiplier, modulus, *, precision=3, max_width=8)
factors_from_phase(value, precision, multiplier, modulus)

API 入口：order_finding、factors_from_phase

multiplier / modulus：与模乘相同的 CP 参数（经典整数直接参数化，无 oracle 输入）；底层模乘位宽预算由 max_width 控制。
precision：QPE 相位寄存器位宽。
factors_from_phase 为纯经典函数：value 是相位寄存器的整数读出（\(0 \le \text{value} < 2^{\text{precision}}\)），返回已验证的因子对（升序元组），或 None 表示该样本未能给出因子。

order_finding 返回 Operation，寄存器为 target: Bits(n)（\(n\) 为模乘位宽）与 phase: Bits(precision)。模块属性：

属性	含义
`algorithm`	`"order_finding"`
`modulus` / `multiplier`	调用参数回显
`readout_register`	`"phase"`（读出后需经典后处理）

实现要点¶

生成链为 modular_multiply → phase_estimation：先在 target 最低位加 X 制备 \(|1\rangle\)，再调用 QPE。\(|1\rangle\) 在各阶循环本征态上均匀展开，故相位读出近似 \(s/r\)（\(s\) 均匀），单个样本不保证给出阶——factors_from_phase 用 Fraction(value, 2**precision).limit_denominator(modulus) 取候选阶，逐一校验偶数性和 \(a^r \equiv 1\)，再对 \(\gcd(a^{r/2}\pm1, m)\) 做验证，全部失败返回 None。乘数与模数不互素且公因子非平凡（\(1 < \gcd(a,m) < m\)）时跳过量子路径，直接返回由该公因子拆出的升序因子对。

适用边界：底层模乘是默认最多 8 位的有界置换合成（见模乘置换），因此求阶同样只面向小实例的接口与线路检查，不代表可扩展的 Shor 模算术。precision 不足时连分数可能还原不出正确的阶，调用方需按 \(r < m\) 选择相位位宽并接受多次采样。

验证方案¶

类别 C1（精确离散语义，判定准则见 ../../development/validation-plan.md §2）：输出分布与经典后处理结果须与精确构造逐点相等。证据：

结构：tests/core/test_algorithm_expansion.py:AlgorithmExpansionTests 的构造与属性断言（寄存器布局 target/phase、属性回显）。
数值：AlgorithmExpansionTests.test_modular_multiplication_and_order 同名见证 test_modular_multiplication_total_permutation_and_order——order_finding(2, 3, precision=2) 的相位分布逐点对拍：\(p(0) = p(2) = 0.5\)（阶 \(r=2\)，\(s \in \{0,1\}\) 各占一半）；后处理路径由 factors_from_phase(1, 2, 2, 15) == (3, 5) 与 factors_from_phase(0, 2, 2, 15) is None 覆盖。
绑定：本算法无独立绑定见证（无开放声明入口）。

已知缺口与计划阶段¶

缺口沿用验证矩阵口径：小规模见证已注明不可外推为完整 Shor（保留原有口径）；多采样成功率、相位位宽与还原成功率的定量扫描未做。阶段列为 —（不属 V1–V4 的任何一档）。

数值验证¶

论文级数值实验见 tests/verification/verify_nt_qlss_sde.py（nt_qlss_sde 组），全部在真实后端执行。

实验设计：(a) 对 7 个 \((a, m, p)\) 实例（\(m \in \{3,5,7,15\}\)，阶 \(r \in \{2,3,4\}\)，precision 3–5），在 reference 与 rir-pysparq 上运行完整求阶程序，phase 边缘分布对照独立理论：\(|1\rangle\) 在 \(r\) 个循环本征态上均布，每个本征相位 \(s/r\) 经 QPE 产生 Dirichlet 核峰，总分布为 \(\frac{1}{r}\sum_{s=0}^{r-1} D^2(y - 2^p s/r)\)（numpy 独立计算）；\((2,3)\) 例另加 adapter-pysparq 与 OriginIR-ext 全振幅路径。同时报告连分数还原出完整阶的概率。(b) factors_from_phase 穷举：\(m \in \{15,21,33,35\}\) × 全部 \(a \in [2, m-2]\) × 全部 \(2^8\) 个相位读出（precision=8，共 23552 次求值），任何返回因子对必须满足乘积为 \(m\) 且两因子非平凡；成功率按 QPE 理论分布加权，并与独立教科书预言（\(s\) 在 \([1,r)\) 均匀、候选阶 \(d = r/\gcd(s,r)\)、要求 \(d\) 偶且 \(a^d \equiv 1\) 且 \(\gcd(a^{d/2}\pm1, m)\) 非平凡）逐模数对比——实测低于预言的差额是 precision=8 对较大的阶的连分数还原分辨率损失（真实物理，非实现缺陷）。

关键指标：

案例	规模	路径	指标	数值
order-finding-2-3-p3	\(r=2\)	四路径	TVD vs Dirichlet 理论 / 阶还原概率	4.4e-16 / 0.500
order-finding-2-5-p4、3-5-p4	\(r=4\)	双路径	TVD / 阶还原概率	6.7e-16 / 0.500
order-finding-2-7-p4、4-7-p4	\(r=3\)	双路径	TVD / 阶还原概率	8.6e-16 / 0.459
order-finding-2-15-p5、7-15-p5	\(r=4\)	双路径	TVD / 阶还原概率	7.8e-16 / 0.500
factors-from-phase-exhaustive	4 模数 × 56 单位群	经典 oracle	无效因子对 / 加权成功率均值 / 与教科书预言最小比值	0 / 0.2925 / 0.791

逐模数成功率（实测 vs 教科书预言）：\(m=15\)：0.500 vs 0.500；\(m=21\)：0.214 vs 0.233；\(m=33\)：0.185 vs 0.233；\(m=35\)：0.271 vs 0.318。奇阶或 \(a^{r/2}\equiv-1\) 的固有失败单位占 16/56，与 Shor 构造的理论预期一致。

复现：

PYTHONPATH=src /home/agony/projects/qcfd-dev/quantum-cfd-software/.venv/bin/python tests/verification/verify_nt_qlss_sde.py

产物：out/verification/nt_qlss_sde.json（order-finding-*、factors-from-phase-exhaustive 共 8 个案例）。