#1 楼
怀疑用小型量子计算机可以分解的最大整数是什么
特技
在给出当前答案之前，与量子有关的分解的最大主张似乎是在[DSBP2018]中使用精确的搜索算法在IBM量子计算机上分解大型双数素数和三边形，得到了Avinash Dash，Deepankar Sarmah，Bikash K. Behera和Prasanta K. Panigrahi的4088459 = 2017×2027。（arXiv：1805.10478，2018）使用2量子位（按其度量）的5量子位和16量子位的IBM量子处理器。
这是纯粹的特技，无需应用密码学，其带来的程度要高于Nikesh S. Dattani和Nathaniel的早期工作。 Bryans，仅4个量子位的56153的量子分解（arXiv：1411.6758，2014）“分解”，例如56153 = 233×241。该方法仅适用于非常狭窄的整数类（这些整数乘积仅相差2位，可能还有其他一些限制）。确定了4088459和56153可以适合该方法。
上述“因式分解”在没有任何实验改进的情况下得以扩展，徐南洋，朱静，陆大为，周宪义，新华社的早期记录为143 = 11×13彭（Peng）和杜江峰（Dufengfeng Du）在偶极耦合核磁共振系统上对143进行量子分解的研究（物理评论快报，2012年）。他们的技术将两个奇数正好为4位的整数的整数乘积（因此每个因数具有两个未知位）。范围[8,15]中素数的稀缺性使143成为该技术可以考虑的两个不同素数的唯一乘积。他们的实验设置通过2位输入迭代地最小化了功能。
Soham Pal，Saranyo Moitra，VS Anjusha，Anil Kumar和TS Mahesh的混合因式分解方案声称对3位输入进行了实验性改进，并将其应用于551 = 19×29，使用3-qubit NMR量子分解551绝热处理器（arXiv：1611.00998，2016）。作者承认，该技术可能无法分解一些较大的10位整数。分解的数量取决于所使用的分子（二溴氟甲烷）。使用自旋系统的内在哈密顿量：应用于291311的实验因式分解（arXiv：1706.08061，2017）使用不同的分子（以$ ^ 3C $标记的二乙基氟丙二酸二乙酯）处理291311 = 523×557。
最新消息：我特此声明新的特技记录。我将[DSBP2018]中方程式（2）的最后一行从$ p_i = q_i = 1; \ i \ in \ {5,6,7,8,9 \} $更改为$ p_i = q_i = 1; \ i \ in \ {5,6，\ dots，87 \} $，并且完全相同的量子实验产生了178位双质数383123885216472214589586724601136274484797633168671371 = 618970019642690137449562081×618970019642690137449562091的“因式分解”，或者说$ 2 ^ {178}-（ 13 \ times2 ^ {91}）+ 651 =（2 ^ {89} -21）\ times（2 ^ {89} -31）$。
注意-以上所有内容实际上都是毫无意义的！
以上技术均未实现Shor算法。他们将分解表示为组合最小化问题，可以使用Grover算法的变体或绝热量子计算来解决。没有理由希望这些方法可以扩展到加密感兴趣的整数的因式分解。
量子计算机上的Shor算法
我们必须分别考虑标题的问题：
受Shor算法影响最大的整数？和Jeremy L. O'Brien在利用量子比特回收技术实现Shor量子因子分解算法的实验性实现中（Nature Photonics，2012年）。
这是由Lieven MK Vandersypen，Matthias Steffen，Gregory Breyta， Costantino S. Yannoni，Mark H. Sherwood和Isaac L. Chuang在利用核磁共振实验性地实现Shor量子因子分解算法的实验中（Nature，2001年），然后是其他几个。
如果这些因子确实是因子分解，这是有争议的，或更确切地确认已知的因式分解。约翰·斯莫林（John A. Smolin），格雷姆·史密斯（Graeme Smith）和亚历山大·瓦尔戈（Alexander Vargo）在“过度简化量子因式分解”中（Nature，2013年，以前的arXiv：1301.7007具有不同的标题）走到了：“编译”中存在危险Shor算法的演示。
更新（2020年9月）
出现了更多的特技分解因果关系（见我的批评家），但其中一个在这个可疑类别中，这个答案仍然是真正的冠军（如果未被报道）。
对于使用量子绝热计算机²的组合方法和Schoor算法，实验性非特技实现的进展似乎都已停止。我们可以更好地了解当前硬件的局限性：Mirko Amico，Zain H.Salee和Muir Kumph使用IBM Q Experience对Shor分解因式算法进行的实验研究（物理评论A，2019年7月）得出结论，他们的工作``未能分解为N = 35英寸。实验性量子计算目前更倾向于不关注在现有问题上击败传统计算机，而更关注发现量子计算机模拟之外发生的问题。请参阅Craig Gidney，MartinEkerå的《如何使用2000万个噪声量子比特在8小时内分解2048位RSA整数》（arXiv：1905.09749，2019年12月）。
¹Shuxian Jiang，Keith A.Britt，Travis S. Humble和Saber Kais在《量子退火中的素数分解》（arXiv：1804.02733，2018）中“介绍了如何分解” 376289 = 571×659，但有人指出这不是实验性的结果，对您的粗心大意感到抱歉。
²紧要关头的是王宝南，胡峰，姚浩南和王超的基于Ising模型参数优化的素因数分解算法（科学字母，2020年4月），它要求一种新的组合方法，将所有整数分解为10000，然后特技类别为1028171 = 1009×1019，但由于是在D-Wave量子计算机上进行模拟而从两个列表中都删除了。
评论
$ \ begingroup $
您如何得出结论，哈密顿优化因子分解是Grover算法的一种变体？为什么与通过基本相同的方法对143进行因式分解相比，对4088459进行因式分解具有更多或更少的特技？
$ \ endgroup $
–吱吱作响的s骨
18-6-5在13:15
$ \ begingroup $
@SqueamishOssifrage：首先，我承认我距离我的舒适区很远。我在引用的第一篇论文摘要中将“ Grover算法的变体”基于“我们的工作利用了通用的Grover算法”，我的理解是，在前两篇论文中，因式分解本质上是在寻找未知位（例如4或4）。这样）解决了组合问题，类似于格罗弗的算法。我将“特技”基于此最小化所涉及的少量位数，这仅限于特殊形式的整数。
$ \ endgroup $
–fgrieu♦
18-6-5在13:24
$ \ begingroup $
经典的归约步骤仅取决于整数的形式，以使其能够以规定的具体数量的qubits实现，但渐近增长仍然是$ n $的对数增长。在某些情况下，整数的形式似乎是有意义的，因为通过减少二进制乘积获得的关系对于多个整数具有相同的系数位解而具有相同的解。悬而未决的问题是量子退火步骤的成本如何随着位数的增加而增加。
$ \ endgroup $
–吱吱作响的s骨
18年6月5日在13:33
$ \ begingroup $
这就是说：需要进行经典的简化（减少因子与乘积之间的关系，为量子电路建立固定的基础），以使计算适合我们现在可用的数量的qubit。如果可以将量子电路或量子退火器扩展到数千个量子比特，则它们不是必需的。限制是量子位的数量，而不是因数分解或周期查找方法。经典因式分解或离散对数算法的超多项式成本是否对应于缩放到许多量子位的超多项式成本？也许！
$ \ endgroup $
–吱吱作响的s骨
18年6月5日在13:57
$ \ begingroup $
@fgrieu 376289实际上不是您提到的第一篇“非特技”论文中的因素。他们在摘要中说，他们“展示了如何做”，这在我看来是一种误导，因为严格地说，他们实际上甚至“展示了”如何分解RSA-4096。在论文的最后，他们说他们不能考虑376289，因为D-Wave机器上没有足够的量子比特。我认为该记录仍低于30万。
$ \ endgroup $
–user1271772
20年5月10日在18:18
评论
看这里。 （没有足够的声誉作为评论添加）请注意：与Shor相比，使用量子计算机进行因子分解的方法更多，您可能需要扩展问题以询问“用Shor分解的最大整数”和“最大因子分解”。