就算是一臺超級計算機有可能在數(shù)年的時間內(nèi)計算出任意質(zhì)因數(shù)，這也是得不償失的。為了科學地解決這個問題，麻省理工學院（MIT）的科學家找到了明確的方法。今天，《科學》雜志最新發(fā)表的一篇論文顯示，量子計算機有史以來第一次以可擴展的方式，實現(xiàn)了Shor算法。

據(jù)外媒Engadget報道，MIT和 Innsbruck大學的計算機科學家組裝了一臺5量子比特的量子計算機，它將能夠用Shor算法完成對數(shù)字15的質(zhì)因數(shù)分解。他們研發(fā)了一臺量子計算機原型，然后使用一系列離子，借助激光脈沖來在4個量子比特上執(zhí)行Shor算法，令其分解數(shù)字，第5個量子比特則用于儲存和輸出結(jié)果。目前的結(jié)果是，這臺計算機不僅能夠比現(xiàn)有量子系統(tǒng)更高效地計算出方案，而且區(qū)間縮放相對容易。

據(jù)維基百科解釋，Shor算法（秀爾算法）是一個在1994年發(fā)現(xiàn)，以數(shù)學家彼得·秀爾命名，針對整數(shù)分解的量子算法（在量子計算機上面運作的算法）。比較不正式的表述是，它解決題目如下：給定一個整數(shù)N，找出他的質(zhì)因數(shù)。

在一個量子計算機上面，要分解整數(shù)N，秀爾算法的運作需要多項式時間（時間是log N的某個多項式這么長）。更精確的說，這個算法花費O((log N)3)的時間，展示出質(zhì)因數(shù)分解問題可以使用量子計算機以多項式時間解出，因此在復雜度類BQP里面。這比起傳統(tǒng)已知最快的因數(shù)分解算法，普通數(shù)域篩選法，其花費次指數(shù)時間——大約O(e1.9 (log N)1/3 (log log N)2/3)，還要快了一個指數(shù)的差異。

秀爾算法的重要性不言而喻，實現(xiàn)它我們就有望破解已被廣泛使用的公開密鑰加密方法——RSA加密算法。RSA加密算法是一種非對稱加密算法，在公開密鑰加密和電子商業(yè)中RSA被廣泛使用，其高度可靠的秘密在在于：對極大整數(shù)做因數(shù)分解的極大難度。也就是說，對一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。但是，假如有人找到一種快速因數(shù)分解的算法的話，那么用RSA加密的信息的可靠性就肯定會極度下降。此前，世界上還沒有任何攻擊RSA算法的可靠方式。

然而，秀爾算法展示了因數(shù)分解這問題在量子計算機上可以很有效率地解決，所以一個足夠大的量子計算機可以破解RSA。這對于建立量子計算機和研究新的量子計算機算法，是一個非常大的動力。

生成海報

免責聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準確性及可靠性，但不保證有關(guān)資料的準確性及可靠性，讀者在使用前請進一步核實，并對任何自主決定的行為負責。本網(wǎng)站對有關(guān)資料所引致的錯誤、不確或遺漏，概不負任何法律責任。任何單位或個人認為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實內(nèi)容時，應及時向本網(wǎng)站提出書面權(quán)利通知或不實情況說明，并提供身份證明、權(quán)屬證明及詳細侵權(quán)或不實情況證明。本網(wǎng)站在收到上述法律文件后，將會依法盡快聯(lián)系相關(guān)文章源頭核實，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。