企业官网建设流程全解析

factoring_sqif 全解析：基于 Schnorr 格分解与 QAOA 量子优化的整数分解实现

【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research

本文基于 factoring_sqif/README.md 及其配套源码，系统讲解 Google Research 子项目 factoring_sqif：一个将经典 Schnorr 格分解算法与量子优化（QAOA / 穷举）结合、用于整数分解的实现。你将掌握其环境搭建、命令行用法、lattice_parameter、precision_parameter、平滑界B₂等关键超参数的含义与取值策略，并通过源码级调用链理解"CVP 问题 → Ising 自旋玻璃哈密顿量 → 低能态采样 → SR-pair → 线性方程组 → 因子提取"的完整流水线。

一、项目定位与算法背景

factoring_sqif 是 Google Research 仓库（当前工作目录google-research）下的一个独立子项目，其核心是实现 arXiv 论文Sublinear Quantum Integer Factoring（arXiv:2212.12372）中提出的 SQIF（Sublinear Quantum Integer Factoring）算法，并在此基础上做了若干工程化改动。

从代码结构看（factoring_sqif/factoring_sqif），该项目由以下模块组成：

算法思想可概括为：把整数分解问题归约为在特定格上求解最近向量问题（CVP），再用量子优化手段在 Babai 给出的近似解附近搜索更优解，从而收获足够多的"光滑关系对"（SR-pair），最终通过求解模 2 线性方程组还原出 N 的非平凡因子。

需要说明的是，README 明确指出 Schnorr 算法本身在经典密码学界仍有争议——在声称的亚线性格维度下能否产生足够多的优质 SR-pair 并不明确（README 引用了经典密码社区的多处讨论）。本仓库的价值在于：提供了一个可复现的实验平台，用于检验"量子优化增强 CVP 求解"这条技术路线，而非宣称已经破解大整数。

二、环境搭建与安装

README 给出两条安装步骤，均在factoring_sqif子项目根目录（即包含 dependencies.yaml 和 pyproject.toml 的目录）下执行。

第一步：用 conda 创建开发环境

conda env create -f dependencies.yaml -n factoring conda activate factoring

dependencies.yaml 中锁定的关键依赖包括：

• python=3.10、numpy=1.21：基础运行环境；
• fpylll=0.5.9：FPLLL 的 Python 接口，用于 LLL 格基规约与 Babai 近似最近向量；
• sage>=9.8：SageMath，用于在-b模式下随机生成指定比特位的半素数（见 main.py 中n_bit_integer对sage.arith.misc.random_prime的调用）；
• cudnn=8.2.1、cudatoolkit=11.3.1：CUDA 环境，对应 requirements.txt 中的cupy-cuda11x（GPU 上的哈密顿量能量枚举依赖 CuPy）；
• numba：对能量计算热路径的 JIT 加速。

第二步：安装库本体

pip install .

pip install .会依据 pyproject.toml 构建并安装factoring_sqif包。该文件的[project]段还揭示了项目元信息：包名为factoring_sqif，描述为 "Implementation of sublinear quantum integer factorization algorithm"，要求python>=3.10，作者为 Tanuj Khattar 与 Nour Yosri。requirements.txt中git+https://github.com/quantumlib/ReCirq表明其依赖 ReCirq 仓库中的优化器（README 提到论文使用其中的 Model Gradient Descent，详见下文 QAOA 小节）。

三、命令行用法与参数速查

运行入口是main.py，其命令行接口由 main.py 顶部的argparse定义。运行python factoring_sqif/main.py --help可查看完整用法：

usage: Integer factoring using Schnorr's algorithm + quantum optimization. [-h] (-N NUMBER_TO_FACTOR | -b BITSIZE) [-l LATTICE_PARAMETER] [-c PRECISION_PARAMETER] [-s SEED] [-m {qaoa,bruteforce}] [-p QAOA_DEPTH] [-NS NUM_SAMPLES] Implementation of integer factoring algorithm described in https://arxiv.org/abs/2212.12372 options: -h, --help show this help message and exit -N NUMBER_TO_FACTOR, --number_to_factor NUMBER_TO_FACTOR Integer to factor. -b BITSIZE, --bitsize BITSIZE Bitsize of number to be factored. -l LATTICE_PARAMETER, --lattice_parameter LATTICE_PARAMETER Lattice parameter. -c PRECISION_PARAMETER, --precision_parameter PRECISION_PARAMETER Precision parameter. -s SEED, --seed SEED Seed for random number generation. -m {qaoa,bruteforce}, --method {qaoa,bruteforce} Method to use for finding ground states of the hamiltonian. -p QAOA_DEPTH, --qaoa_depth QAOA_DEPTH Depth of qaoa circuit. -NS NUM_SAMPLES, --num_samples NUM_SAMPLES Number of low energy states to sample

其中-N与-b构成互斥必选组：要么直接指定待分解整数N，要么指定比特位宽b（此时程序会用 Sage 随机生成一个b比特的半素数，见 main.py 的n_bit_integer）。

各参数在源码中的默认值如下（来自 main.py 的add_argument定义）：

最小可运行示例：README 用分解187 = 17 × 11演示了默认流程：

python factoring_sqif/main.py -N 187

50 比特随机整数 + 穷举法：

python factoring_sqif/main.py -b 50 --method bruteforce

50 比特随机整数 + QAOA（深度 3）：

python factoring_sqif/main.py -b 50 --method qaoa -p 3

分解成功时程序会输出形如Found factors (707933, 882727) for 624911573291 using 11 qubits via bruteforce.的结果（该行即来自仓库自带的 40 比特运行日志，见下文第七节）。

四、核心超参数（一）：格维度与lattice_parameter

Schnorr 算法广受讨论的要点之一，是它声称可以在仅随待分解数比特位宽亚线性增长的格维度下找到足够多的优质 SR-pair——这也正是论文将其作为量子优化起点的原因。但在经典密码学社区，求解声称维度格上的 CVP 是否真能产生足够 SR-pair 尚无定论（README 引用了 crypto.stackexchange 与相关讨论）。

在量子化方案中，格维度直接决定了所需的量子比特数（每个格维度对应一个 qubit）。本项目用可配置常数lattice_parameter控制格维度：

$$ n = \mathrm{lattice_parameter} \cdot \frac{\log_2(N)}{\log_2(\log_2(N))} $$

该公式在 number_theory.py 中实现为integer_to_lattice_dimension：

def integer_to_lattice_dimension(N, c=1): logN = round(math.log2(N)) return int(c * int(logN) // int(round(math.log2(logN))))

number_theory_test.py 给出了三个基准校验（对应 README 提到的论文复现样例）：

• integer_to_lattice_dimension(1961) == 3
• integer_to_lattice_dimension(48567227) == 5
• integer_to_lattice_dimension(261980999226229) == 8

一般来说，格维度越高，找到足够多优质 SR-pair 的概率越大（分解越可能成功），但算法的时间/空间复杂度也随之上升。值得注意的一个实现细节是：main.py 中SchnorrFactoringConfig.from_arxiv_paper_defaults的函数签名默认lattice_parameter=1，而论文复现样例run_arxiv_examples依次使用[1, 1.5, 1.5]；命令行默认值则是1.5。读者可以根据目标位数自由调节-l。

五、核心超参数（二）：精度参数c与格构造

精度参数c控制构造格所使用的基向量。原版 Schnorr 算法中，格 $B_{n,c}$ 构造为：

$$ B_{n,c} = \begin{bmatrix} f(1) & 0 & \dots & 0\ 0 & f(2) & \dots & 0\ \vdots & \vdots & \ddots & \vdots\ 0 & 0 & \dots & f(n) \ N^c\ln{p_1} & N^c\ln{p_2} & \dots & N^c\ln{p_n} \end{bmatrix} $$

其中 $f(i)$（$i=1,\dots,n$）是 $(\sqrt{\ln{p_1}}, \sqrt{\ln{p_2}}, \dots, \sqrt{\ln{p_n}})$ 的随机排列。

本项目（依据 arXiv:2212.12372）对其做了两处修改：

$$ B_{n,c} = \begin{bmatrix} f(1) & 0 & \dots & 0\ 0 & f(2) & \dots & 0\ \vdots & \vdots & \ddots & \vdots\ 0 & 0 & \dots & f(n) \ \lfloor10^c\ln{p_1}\rceil & \lfloor10^c\ln{p_2}\rceil & \dots & \lfloor10^c\ln{p_n}\rceil \end{bmatrix} $$

其中 $f(i)$ 改为 $(\lceil 1/2 \rceil, \lceil 2/2 \rceil, \dots, \lceil n/2 \rceil)$ 的随机排列，末行从 $N^c\ln{p_i}$ 改为取整后的 $\lfloor 10^c\ln{p_i}\rceil$。

对应实现位于 closest_vector_problem.py 的sample函数：它按上述公式构造一个 $(n+1)\times n$ 的IntegerMatrix，并生成稀疏目标向量 $t$——$t$ 只有最后一个分量非零，取值为 $\lfloor 10^c\ln{N}\rceil$。该函数 docstring 注明其构造方式对应论文第 13 页，并限制格维度 $n\le 25$（超出会报NotImplemented）。

READme 指出：格的行列式与精度参数 $c$ 正相关；论文猜想"找到接近目标向量的格向量的概率与 $c$ 正相关"，但作者也坦承这一推断的理由并不显然。因此-c是一个值得实验调参的对象，默认值 4。

六、核心超参数（三）：平滑界 $B_2$ 与采样数量

在 Schnorr 算法中，格上的每个点都可映射为一对整数 $(u,v)$，且按构造 $u$、$v$ 均为 $p_n$-光滑（即其素因子不超过第 $n$ 个素数 $p_n$，$n$ 为格维度）。算法要求找到"足够多"的 SR-pair $(u,v)$，使得 $u$、$v$ 都是 $p_n$-光滑，且 $|u - v\cdot N|$ 是 $p_{B_2}$-光滑（素因子不超过第 $B_2$ 个素数）。这里的 $B_2$ 是另一个超参数，通常至少取 $n$。

经验法则：SR-pair 的数量只需比平滑界 $B_2$ 多几个。本实现默认设置：

$$ B_2 = 2n^2 $$

$$ \mathrm{num_sr_pairs_to_sample} = B_2 + 2 $$

其中 $n$ 为格维度。源码中的对应关系在 main.py：linear_eq_system_dimension = 1 + 2 * n**2，num_sr_pairs_to_sample = linear_eq_system_dimension + 1，而solve内的实际光滑界取smooth_bound = config.linear_eq_system_dimension - 1（即 $2n^2 = B_2$）。以 40 比特运行日志为例，格维度 $n=11$ 时，日志显示smooth bound 242、243维线性方程组、需要244个 SR-pair——恰好满足 $2\times 11^2=242$、$1+242=243$、$243+1=244$。

$B_2$ 对算法的影响存在权衡：

1. $B_2$ 越大，满足 $|u - v\cdot N|$ 为 $B_2$-光滑的约束越容易满足，找到有效 SR-pair 的概率越高；
2. 但 $B_2$ 越大，需要采样的 SR-pair 数量越多，整体运行时间越长。

光滑性判定实现在 number_theory.py 的is_smooth，SR-pair 过滤在 hamiltonian.py 的sr_pairs_from_uv_pairs（对每个 UV-pair 检查abs(u - N*v)是否光滑）。此外 number_theory.py 的pairs_to_sr_possiblities还实现了一个技巧：按"最大素因子下标"排序 SR-pair，一旦前缀数量超过该下标即可构成有效的方程组前缀。

七、完整流水线：从 CVP 到因子（solve主循环）

main.py 的solve函数是整条流水线的核心，其迭代逻辑可归纳为五步，每一步都对应独立模块：

1. 构造格与目标向量：调用 closest_vector_problem.py 的cvp.sample(N, n, c, rs)得到 $(n{+}1)\times n$ 的格B与目标向量t；
2. Babai 近似最近向量：调用cvp.babai_algorithm(B, t)（closest_vector_problem.py）。该函数先用 fpylll 以delta=0.75对格基做 LLL 规约，再通过GSO.Mat(D).babai(t)得到近似解权重w、残差向量与rounding_direction（决定后续在超立方体中搜索的方向），封装为BabaiResult；
3. 构造问题哈密顿量：hamiltonian.hamiltonian_from_babai_result(qs, babai_result)（hamiltonian.py）把"在 Babai 近似解附近寻找更优格向量"编码为 Ising 型哈密顿量 $H = \sum_j (r_j - \sum_i X_i D_{ji})^2$，其中 $X_i$ 为投影算子，$D$ 为 LLL 规约后的格基，$r$ 为残差向量；
4. 采样低能态并过滤 SR-pair：按method选择bruteforce或qaoa得到低能态整数表示，随后依次经过integer_states_to_lattice_vectors→u_v_pairs_from_lattice_vectors→sr_pairs_from_uv_pairs（均位于 hamiltonian.py）把低能态映射回格向量、再映射回 $(u,v)$ 光滑对、最后过滤出 SR-pair 并入集合；循环直到收集够num_sr_pairs_to_sample个或达到max_lattice_iterations次迭代；
5. 解线性方程组提取因子：把 SR-pair 转成指数差向量（schnorr.sr_pair_to_differences），在GPU（CuPy）上做模 2 高斯消元（schnorr.py 的_gaussian_elementation_Z2）并枚举零空间（_null_space），得到指数组合，再由exponents_to_candidates构造候选因子并math.gcd(p, N)校验——一旦得到非平凡因子即返回SchnorrFactoringResult。

仓库results/目录下附带多组真实运行日志（如 40bit_l1_bruteforce.txt、70bit_qaoa.txt、128bit_l1_bruteforce.txt等），文件名即标注了比特位宽与lattice_parameter取值。以 40 比特日志为例，可观察到典型行为：

• 每轮迭代从 2048 个 UV-pair 中过滤出 0～24 个 SR-pair；
• 40 轮迭代累计 247/244 个 SR-pair 后停止，随后在 Z₂ 零空间搜索中成功找到因子707933与882727（624911573291 = 707933 × 882727），全程仅使用 11 个量子比特。

八、寻找哈密顿量低能态的三种途径

README 依次介绍了三种求解低能态（即寻找接近目标向量的格向量）的方案。

8.1 暴力枚举（Brute Force）

最简单的方法：穷举全部 $2^n$ 个比特串作为输入态（$n$ 为量子比特数/格维度）。复杂度随 $n$ 指数增长，并不具备可扩展性，其作用是"假设存在完美量子优化器"时验证其余经典归约的正确性。运行方式：

python factoring_sqif/main.py -b 50 --method bruteforce

实现上，hamiltonian.py 的brute_force_lowest_energy_states对全部 $2^n$ 个整数态调用energy_from_integer_states计算能量并稳定排序，取前num_samples个。energy_from_integer_states对单比特项（Z）与双比特项（ZZ）分别用 numba JIT 批量求值，双比特项通过 CuPy 上 GPU 加速（见_in_batches的cuda=True分支）。

8.2 QAOA（论文主推方法）

QAOA 是启发式算法，性能取决于两个可配置的启发式因素：

1. 电路深度 $p$：默认 $p=2$，可通过--qaoa_depth调大。电路构造见 qaoa.py 的generate_qaoa_circuit：先对所有 qubit 施加 Hadamard，再交替叠加 $p$ 层gamma（由哈密顿量各项分解为Z**与ZZ**门，见get_gamma_layer）与beta（对所有 qubit 施加X**，见get_beta_layer）；
2. 外层经典优化器：用于寻找变分电路的最优参数。论文声称使用 Model Gradient Descent（ReCirq 中有对应实现），但 README 说明作者尝试开箱即用的 MGD 实现并未收敛，因此在 qaoa.py 的find_optimal_parameters中改为调用 ReCirq 的minimize并以BFGS作为优化方法（代码注释保留了 TODO，说明仍在调研 MGD 不收敛的原因），欢迎读者自行尝试其他优化方法。

QAOA 采样的完整路径为sample_low_energy_states（qaoa.py）：生成电路 → BFGS 优化参数 → 用qsimcirq.QSimSimulator（8 线程）重复采样 10000 次 → 按频率返回比特串。运行示例：

python factoring_sqif/main.py -b 50 --method qaoa -p 3

此外 qaoa.py 还提供expected_energy_landscape与plot_energy_landspace，可在 $(\gamma, \beta)\in[0,\pi]^2$ 网格上绘制期望能量热力图，用于直观观察代价函数曲面——main.qaoa_main()（10 比特示例问题）演示了这一可视化流程。

8.3 DCQF（未来改进方向）

DCQF 是另一种启发式算法（arXiv:2301.11005），与 QAOA 不同，它不需要外层经典优化循环。README 明确指出：DCQF 的具体细节以论文为准，本仓库尚未集成其实现，留作未来改进方向。

九、测试与验证

仓库自带两组 pytest 测试，是验证经典归约正确性的关键证据：

• number_theory_test.py：校验格维度公式（1961→3、48567227→5、261980999226229→8）；
• hamiltonian_test.py：覆盖三个层面——test_hamiltonian用 test_data/3q/hamiltonian.txt 与10q/下预计算的低能态基准比对暴力枚举结果；test_hamiltonian_construction验证hamiltonian_from_babai_result与参考哈密顿量完全一致；test_u_v_pairs_from_integer_states与test_sr_pairs_from_uv_pairs验证低能态 → 格向量 → (u,v) 对 → SR-pair 的逐级映射（以 N=1961 为例，UV 对(1800,1),(1944,1),(2025,1),(3645,2)中仅前三个在平滑界 15 下构成 SR-pair）。

十、复现论文样例与进一步探索

main.py 的run_arxiv_examples内置了论文的三个复现目标：

有兴趣的读者可以在此基础上，围绕 README 与源码指出的开放问题做进一步实验：调节-l、-c、-p观察 SR-pair 产出率与运行时间的变化；尝试更换 qaoa.py 中的外层优化器（如复现论文的 MGD）；或按 README 的启发，探索比"超立方体搜索"更好的 CVP→量子优化归约方式。

参考资源

本文相关的背景文献（均为 README 原文引用，此处以文本形式列出）：

• Sublinear Quantum Integer Factoring（arXiv:2212.12372）——本实现所依据的核心论文；
• A note on Integer Factorization using Lattices，A. Vera（arXiv:1003.5461）；
• Schnorr's Approach to Factoring via Lattices，Léo Ducas（CWI RISC 讲座幻灯片）；
• SchnorrGate - Testing Schnorr's factoring Claim in SageMath，Léo Ducas——对 Schnorr 格分解主张的 SageMath 检验；
• DCQF 方法论文（arXiv:2301.11005）——README 中留作未来改进的量子优化方案。

【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research