Shor算法分解的最大整數？
我正在研究 Shor 的量子分解算法。我想知道他們能夠用小型量子電腦分解的最大整數是多少。有人對此有任何想法嗎？
想知道他們能夠用小型量子電腦分解的最大整數是多少
特技
在目前的答案之前，量子相關因式分解的最大主張似乎是4088459 =2017×2027，作者 Avinash Dash、Deepankar Sarmah、Bikash K. Behera 和 Prasanta K. Panigrahi，在
$$ DSBP2018 $$ 在 IBM 量子電腦(arXiv:1805.10478, 2018) 上使用 2 個量子位（根據他們的測量）具有 5 個量子位和 16 個量子位的 IBM 量子處理器分解大型雙素數和一個三素數的精確搜尋算法。 這是一個純粹的噱頭，沒有應用於密碼學，比 Nikesh S. Dattani 和 Nathaniel Bryans 的早期工作更高程度，56153 的量子分解，只有 4 個量子位(arXiv:1411.6758, 2014) “分解”，例如56153 =233× 241. 該方法僅適用於非常窄的整數類（整數的乘積僅相差 2 位，可能還有一些其他約束）。4088459 和 56153 被確定為適合該方法。
上述“因式分解”在不需要任何實驗改進的情況下擴展了由 Nanyang Xu、Jing Zhu、Dawei Lu、Xianyi Zhou、新華鵬和杜江峰在偶極上 143 的量子因式分解中的143 =11×13 的早期記錄-耦合核磁共振系統（物理評論快報，2012 年）。他們的技術將兩個奇數恰好 4 位整數的整數乘積分解為因子（因此每個因子有兩個未知位）。範圍內素數的稀缺性
$$ 8,15 $$使 143 成為該技術可以分解的兩個不同質數的唯一乘積。他們的實驗設置迭代地最小化具有 2 位輸入的函式。 Soham Pal、Saranyo Moitra、VS Anjusha、Anil Kumar 和 TS Mahesh 的混合分解方案聲稱對 3 位輸入進行了實驗改進，適用於551 =19×29：使用 3 量子位核磁共振量子分解 551絕熱處理器(arXiv:1611.00998, 2016)。作者承認該技術可能無法分解一些更大的 10 位整數。影響可以分解的整數的量子比特數取決於所使用的分子（二溴氟甲烷）。
Zhaokai Li, Nikesh S. Dattani, Xi Chen, Xiaomei Liu, Hengyan Wang, Richard Tanburn, Hongwei Chen, Xinhua Peng, Jiangfeng Du’s High-fidelity adiabatic quantum computation using the intrinsic Hamiltonian of a spinsystem: Application to the experimental factorization of 291311 (arXiv:1706.08061, 2017) tackle 291311 =523×557 using a different molecule ( $ ^3C $ -標記的氟代丙二酸二乙酯）。然而，他們仍然使用 3 個量子比特，我認為更多的是對整數因子的一些預篩選，而不是分子的變化（這似乎旨在提高實驗準確性），這解釋了更大的值。
突發新聞：我在此要求一項新的特技記錄。我將等式 (2)的最後一行更改為$$ DSBP2018 $$從 $ 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×618970019642691017 $ 2^{178}-(13\times2^{91})+651=(2^{89}-21)\times(2^{89}-31) $ .
上面的任何特技分解都可以使用費馬方法的第一步獲得¹：讓 $ n $ 是要考慮的整數；讓 $ u=\left\lceil\sqrt n,\right\rceil $ ; 如果 $ v=\sqrt{u^2-n} $ 是一個整數，那麼 $ u-v $ 和 $ u+v $ 是因素 $ n $ . 線上試用（在 Python 中）！
絕熱量子計算記錄
對於一些非特技，定義為旨在將大部分任意複合材料分解到某個極限，記錄²可能是 Raouf Dridi 和 Hedayat Alghassi使用量子退火和計算代數幾何的素數分解（在 Nature 科學報告，2017 年）分解使用 D-Wave 2000Q（絕熱量子電腦）到223357 =401×557 。一年後，關於它可以模擬的真正量子電腦的大小的爭論仍在激烈進行。
注意 - 以上所有內容實際上毫無意義！
上述技術都沒有實現 Shor 算法。他們將分解表示為組合最小化問題，使用 Grover 算法的變體或絕熱量子計算來解決。沒有論據希望這些方法可以擴展到加密感興趣的整數的因式分解。
量子電腦上的 Shor 算法
我們必須單獨考慮標題的問題：
Shor算法分解的最大整數？
沒有使用 Shor 的原始算法分解任何數字。
自 2001 年以來，多位作者發表了聲稱使用 Shor 算法在量子硬體上使用因子 15 和 21 的論文，但後來發現他們使用的是特定基數 $ a $ 這樣就需要更少的量子比特。為了知道這個值 $ a $ ，您需要知道這些因素（即您需要知道 21 = 7 x 3）。在事先不知道這些因素的情況下，您需要檢查 $ a $ ，用 Shor 的原始算法分解 15 需要 8 個量子位，但曾經使用過的最大的是 7 個。
事實證明，如果你事先知道因子，你可以用少量的量子比特來分解任何數字，而論文“Pretending to factor large numbers on aquantum computer”展示了“Shor 算法”分解 RSA-768 只有 2量子比特，還有一個只有 2 個量子比特的 20,000 位數字（參見第 4 頁的表 1）。該論文解釋說，迄今為止，Shor 算法的所有實現都是使用素因數知識完成的（如果您想對因數未知的 RSA 數進行因式分解，那麼您在現實生活中無法做到這一點）。
這篇論文最終以 John A. Smolin、Graeme Smith 和 Alexander Vargo的題為Oversimplifyingquantum factoring (2013) 發表在Nature上。
更新（2020 年 9 月）
出現了更多的特技分解（見我的批評者），但這個答案中的那個仍然是這個可疑類別中真正的（如果報導不足）冠軍。
對於使用量子絕熱電腦³和 Schor 算法的組合方法，實驗性非特技實現的進展似乎已經停止。我們確實更好地了解了目前硬體的局限性：Mirko Amico、Zain H. Salee 和 Muir Kumph使用 IBM Q Experience 對 Shor 分解算法的實驗研究（物理評論 A，2019 年 7 月）得出結論，他們的工作“未能分解 N= 35"。實驗性量子計算目前更傾向於不關注在現有問題上擊敗經典電腦，而是關注發現超出量子電腦模擬的問題。
一項有趣的新工作在假設的量子電腦上進行了因式分解的心理實驗：參見 Craig Gidney，Martin Ekerå 的如何使用 2000 萬個雜訊量子位在 8 小時內分解 2048 位 RSA 整數（arXiv:1905.09749，2019 年 12 月）。
¹任何分解方法僅限於 $ n $ 從密碼學的角度來看，費馬的一步是毫無意義的。反之則不成立。
² Shuxian Jiang, Keith A. Britt, Travis S. Humble, and Saber Kais in Quantum Annealing for Prime Factorization (arXiv:1804.02733, 2018) “present how to factorize” 376289 =571×659，但有人指出它不是一個實驗結果，很抱歉粗心。
³近距離接觸是 Baonan Wang、Feng Hu、Haonan Yao 和 Chao Wang 的基於 Ising 模型參數優化的素數分解算法（科學信函，2020 年 4 月），該算法聲稱一種新的組合方法將所有整數分解為 10000，並且屬於特技類別1028171 = 1009×1019，但由於是在模擬D-Wave 量子電腦上而被從兩個列表中刪除。