量子计算论文精讲 | NISQ量子计算机上的整数因子分解

量子计算论文精讲 | NISQ量子计算机上的整数因子分解

引用

CSDN

1.

https://blog.csdn.net/2401_83053014/article/details/136993026

量子计算的发展对密码学造成了深远的影响：1994年诞生的Shor算法证明通用量子计算机能够有效地解决整数因子分解问题，使得广泛应用的RSA加密体系不再安全并推动了抗量子密码技术发展。尽管Shor算法可能需要上百万个嘈杂的物理量子比特才能攻破RSA——当前的量子计算机只能提供上百个物理比特——已经有研究者尝试利用当前的中规模嘈杂量子设备（Noisy Intermediate Scale Quantum，NISQ）进行整数因子分解，甚至有研究者宣称只需要372个量子比特即可以攻破RSA-2048，掀起轩然大波。RSA是否已被或即将被量子计算机攻克？本文围绕该争议论文的来龙去脉为您解读。

整数因子分解问题的经典算法

整数因子分解是一个兼具学术和实用价值的问题。科学上，给定任意整数，尽管可以用Miller Rabin算法（该算法为多项式复杂度的随机算法）高效地判定其是否为素数，但求取其质因子则是高度困难的问题——尽管尚未被证明是否属于NP复杂性类。经典计算机上已知最高效的几个方法有：普通数域筛法（General Number Field Sieve，GNFS），二次筛法（Quadratic Sieve，QS），椭圆曲线因式分解（Elliptic Curve Method, ECM）等，如表1所示。知名的开源求解器有cado-nfs、msieve等。

以整数因子分解问题的困难性做安全性保障，RSA加密协议曾广泛应用数十年，其核心是对形如：

整数的分解问题，其中N为多达2048位的已知整数，而p, q均为待求的质数。RSA实验室甚至发布了RSA挑战赛榜单，鼓励用各种求解系统对大数作分解，促进了该领域发展的同时也体现了RSA加密体系在经典计算机上的安全性。然而，1994年IBM公司的Shor发现在通用量子计算机上可以在

时间内分解N位整数，结合近年来量子计算领域的快速发展，对RSA加密体系产生了冲击，并推动密码学领域进入后量子时代。

格方法基础知识

格(lattice)在密码学中有广泛应用，篇幅所限，在此只介绍与论文相关的部分。由

中的基

可以定义格:

格问题中一般希望基向量尽可能的“正交”，Hadamard比率描述了格基的“正交”程度，定义为

即格基张成的平行多面体体积与对应的长方体的体积之比。通过对格基作整数系数的线性组合可以提高格的Hadamard比率，称作格约简(reduction)。LLL算法（K.Lenstra, H.W.Lenstra, Jr. and L.Lovasz）是经典的格约简算法.

格上的最短向量问题(Shortest Vector Problem, SVP)定义为

即寻找距离原点最近的格点。SVP已被证明是NP完备的。类似的，格上的最近向量问题（Closest Vector Problem, CVP）定义为

即要寻找距离给定的

最近的格点. CVP也是NP完备的。

如果将SVP和CVP中的目标松弛到最优解的γ>1倍，则相应的问题称作γ-SVP和γ-CVP问题，对足够大的γ有多项式算法。Babai的最近平面算法可以在多项式时间内求解

的γ-CVP问题，设

和

分别LLL约简基和Gram-Schmidt正交基（即对

正交化），Babai算法流程如下：

该算法有鲜明的几何意义：每一步迭代固定一个分量，即将候选的格点集合限制在分量对应的超平面中。那么，选取距离目标点t最近的超平面显然是合理的，这就是最近平面法。

Schnorr的工作

这篇由著名密码学家Claus P. Schnorr（Schnorr签名的作者）在2021年发表的工作这项工作将光滑关系对的采样问题转化为格理论中的最近向量问题（Shortest Vector Problem, SVP），通过原对偶约简（prime-dual reduction）求解SVP，宣称攻破了RSA加密体系，曾引起广泛讨论和争议。现在一般认为并未攻破RSA，但其采用的方向确有重大的理论价值，参考同行Léo Ducas的公开复现结果SchnorrGate。

作者给出格的构造方案如下。设N是待分解的整数，

是前n个质数，

是整数集

上的置换，

，取格基为

设每个格点

编码了潜在的光滑关系对

记作

. 记

和

的最后一个分量分别为

则有

当且仅当

时取到等号. 借助Tayler展开式

可以证明：

引理：对于

，只要

或

，就有

由此

被

控制，后者可以通过求解SVP问题最小化。根据光滑数的分布规律，

构成光滑关系对的概率为

，其中ρ为Dickman-de Bruijn函数，

. 通过设置不同的置换函数

并求解SVP问题，即可实现光滑关系对的采样。由此，光滑关系对采样问题转化为SVP求解。

作者宣称求解n位整数因子分解问题只需要

维格，进而用

次算数运算可以分解

，比二次筛和数域筛更快。然而同行指出作者高估了采样成功率，也低估了所需的格的维数，各种公开和私下的复现结果最终导向共识：数域筛和二次筛仍然是最快的两个整数因子分解算法。

清华大学龙桂鲁团队的工作

这篇文章沿用了Schnorr的工作，并用QAOA算法改进SVP解的质量（文中使用CVP形式，本质上和SVP相同），提出了亚线性资源的量子整数因子分解算法（Sublinear-resource Quantum Integer Factorization, SQIF），其整体框架如图所示。

作者用QAOA算法改进Babai算法的CVP解，其思想在约简格基下，对解（格点）的每个分量做±1的扰动（+1和-1只能选一个）或保持不动，以期得到更好的解。扰动的方向由Babai算法的取整的方向给出。具体的，设

和

分别是LLL约简基和相应的Gram-Schmidt正交基，Babai算法流程如下：

可见，Babai算法中计算系数c时对μ取整，当向下取整时，Babai算法给出的解的第j个分量比t大，应取-1作为扰动方向；当

是向下取整时，同理应取+1作为扰动方向。设

是Babai算法的解，扰动解构造为

其中

，符号选取如前所述。CVP问题表述为

这实质上是一个Ising问题，可以用QAOA算法求解，相应的哈密顿量为

其中

即将扰动映射到量子比特的Paoli-Z算符.

作者分别在11位数1961，26位数48567227和48位数261980999226229测试SQIF算法的效果，3用例分别使用了3个，5个和10个超导比特。如图2所示，超导量子计算机具有线性拓扑（A），而哈密顿量为全连接拓扑（B），故需要做比特映射。对于p层QAOA中的每一层演化（C），需要用

网络做路由（D），其

块可以由本地支持的Hadamard门和Rz门构建（E）。

对不同的用例及QAOA层数p，作者给出的QAOA算法的仿真和实验结果如图所示。可见，QAOA算法的实际采样成功率与含噪声仿真（Noisy）结果接近，与无噪声仿真结果（Theory）相去甚远。对于3比特(p=3)，5比特(p=3)和10比特(p=1)情形，采样成功率分别在0.5， 0.2和0.01数量级。三种情况分别采样20，55和221个光滑关系对。据此可以估算所需的采样次数至少分别是

，

和

数量级。

作者给出了考虑三种硬件拓扑下的线路深度估计。对三种有代表性的硬件拓扑：1）全连接拓扑Kn；2）1维链拓扑LNN；3）2维网格拓扑2DSL。对于n量子比特线路，每一层有n(n-1)/2个两比特ZZ耦合需要执行，三种情况下的作者给出的线路深度分别为

作者给出的线路实现分别是：

Kn：全连接图划分为n组完美匹配，每组含n-1个ZZ单元，每个ZZ单元深度为3，共3n层；

LNN：将ZZ单元升级为兼具SWAP功能的ZZ-SWAP单元，每个ZZ-SWAP单元深度为4. 按照并行冒泡排序（parallel bubble sort）算法执行n层ZZ-SWAP完成演化，共计4n层。

2DSL：原理与LNN情形相同，但按照文献给出的方案优化到

层。

综合以上结果，我们将作者演示的整数因子分解资源需求整理如下

作者对分解不同规模RSA数所需的量子线路规模做乐观估计，认为用372个物理量子比特即可以攻破RSA-2048，由此引起广泛关注和争议。

Google团队的评价

这篇来自Google的论文回顾了Schnorr和Yan等人的争议性工作，并提供了一个公开的框架来测试像SQIF这样的格-QAOA量子经典混合算法的实际效果。其中，经典部分按照Schnor的工作，求解

维格上的CVP；量子部分则采用两种方法：其一是枚举经典解邻域的2m个格点，选取最优解；其二是模拟QAOA算法。显然，QAOA算法的效果不会优于枚举法。

测试使用的机器是Google Cloud Platform (GCP)上的一台 a2-highgpu-1g型虚拟机。该机器包含GPU，程序中的线性代数及可以向量化的运算被移动到GPU上以提供加速。

作者给出的测试结果如表所示。可见，枚举法未能分解任何70位以上的整数。作者由此断定：用基于格CVP解，QAOA等量子求解器无法将可求解问题的规模进一步增大。

俄罗斯团队的评价

这篇来自俄罗斯的论文指出了SQIF算法文章存在漏洞，即对算法的经典部分缺乏系统严谨的分析，并提供了若干用例来说明SQIF实际需要更多的资源来完成其所宣称的目标。具体的，作者指出了以下几个漏洞：

1. 无法保证QAOA算法能凑齐足够的光滑关系对。实验中，作者发现对N=1961，n=3，即使在构造格时用尽全部可能的置换，也只能凑齐9个光滑关系对，低于所需的数目；
2. 对算法复杂度分析不足，特别是“亚线性资源”的宣称是有误导性的：
   (a) 一方面，经典部分使用的LLL算法只是γ-CVP算法，其中γ=(2/√3)^n，因此随问题规模增加，找到LLL算法给出短向量的概率指数下降；
   (b) 另一方面，量子部分所用的QAOA算法在高维情形缺乏收敛性保证，而一些数值仿真表明这可能造成问题；
3. 超参数取值依据不清晰：例如，作者为了提高采样得到光滑关系对的概率，将用于验证的因子基大小

取为

，这会造成规模较大时求解线性同余方程组的代价快速增加；
4. 一些关于格的表述细节问题。

上述这些质疑可以为Google团队的对SQIF的复现结果一致，论证格方法+QAOA路线的可扩展性并没有人们想象的那样乐观。

总结

本文介绍了一篇尝试在NISQ量子计算机上实现RSA大数分解的争议性文章，并介绍其来龙去脉。目前的结果显示，在当代的量子计算机上攻破RSA秘钥仍然是不太现实的。对于安全领域的从业者来说这似乎是一个好消息：在通用量子计算机诞生之前，我们仍有一些时间来开发抗量子密码，并升级生产系统中已有的协议。