文章來源：新智元微信公眾號

互聯(lián)網(wǎng)時代絕大多數(shù)的加密，都由RSA算法完成。過去我們認為RSA不可破解，但隨著量子計算的發(fā)展，RSA的安全性正受到挑戰(zhàn)。今天刊發(fā)在《科學》雜志的最新論文，量子計算機有史以來第一次以可擴展的方式，用Shor算法完成對數(shù)字15的質(zhì)因數(shù)分解。IBM 物理科學高級主管Mark Ritter表示，將Shor算法實現(xiàn)出來這件事，能夠與經(jīng)典計算中的‘Hello，World’ 相提并論。

互聯(lián)網(wǎng)時代，密碼和網(wǎng)絡安全是通信的基礎，無論是微信聊天，還是淘寶交易，都需要密碼技術(shù)保障個人隱私和財產(chǎn)安全。

而現(xiàn)在的大部分加密，都由RSA算法完成，它基于一個非常簡單的數(shù)論事實：

將兩個大素數(shù)相乘十分容易，但是想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。

例如在一套 RSA 算法下，給定一對解密密鑰3和5，由用戶自己保存，那么3和5的乘積15，就成為公開的加密密鑰。

當把3和5變成1024位的素數(shù)A和B時，令C是A和B的乘積。那么驗證A乘以B等于C，是一件計算起來比較簡單的事，即用戶自己的密碼可以獲得通過；但是要從C倒推回A和B，卻是無比的艱難，其運算時間超出計算機的能力，所以密碼很難被破解。

所以RSA可以在公開加密密鑰、加密和解密算法的情況下，通過驗證和求解在時間復雜度上的極端不對稱性，建立電子加密的基礎。

RSA 是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的絕大多數(shù)密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標準。

今天，只有短的RSA鑰匙才可能被強力方式解破。到2008年為止，世界上還沒有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長度足夠長，用RSA加密的信息實際上是不能被解破的。但在分布式計算和量子計算機理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)。

Shor 算法

整數(shù)的質(zhì)因數(shù)分解，進入多項式的時間

早在 1994 年，Peter Shor就發(fā)明了一個量子算法（Shor算法），在整數(shù)的質(zhì)因數(shù)分解上，能實現(xiàn)

的時間。這在當年引起了轟動，它展示了一個足夠大的量子計算機，在理論上是能夠把質(zhì)因數(shù)分解的時間復雜性降到多項式的時間。

多項式時間在這里意義重大。因為RSA加密之所以有效，最重要的是因為整數(shù)的質(zhì)因數(shù)分解，在數(shù)字特別大的時候，傳統(tǒng)的計算方法根本看不到算完的那一天。現(xiàn)在最快的質(zhì)因數(shù)分解算法，其花費的次指數(shù)時間，也達到了

但如果能把解密復雜度變成多項式的時間，那么基本任何的RSA模型下的大數(shù)，都能夠很“輕易”的被破解。所以RSA加密在理論上已經(jīng)不再安全。

然而，這種算法需要依賴可操作大量量子的計算機。雖然有些人已經(jīng)嘗試了用各種量子系統(tǒng)來實現(xiàn)Shor的算法，但是沒有人能在超過幾個量子比特的系統(tǒng)上以可擴展（scalable）的方式這么做。所以Shor算法雖然具有理論的意義，但一直沒法真正在工程上使用。而世界上也很難找到比RSA更加簡單而有效的加密手段，所以RSA加密一直統(tǒng)治著世界，直到現(xiàn)在。

進入21世紀以來，量子計算機開始加速發(fā)展。2001 年，IBM的一個小組展示了Shor算法的實例，使用核磁共振的量子計算機，以及7個量子位元，將15分解成3×5。然而，對IBM的實驗的是否是量子計算的真實展示，有一些疑慮出現(xiàn)，因為沒有纏結(jié)現(xiàn)象被發(fā)現(xiàn)。在IBM 的實驗后，有其他的團隊以光學量子位元實現(xiàn)Shor算法，并強調(diào)其纏結(jié)現(xiàn)象可被觀察到。

《科學》雜志最新論文

論文標題：Realization of a scalable Shor algorithm

作者：Thomas Monz，Daniel Nigg，Esteban A。 Martinez，Matthias F。 Brandl，Philipp Schindler，Richard Rines，Shannon X。 Wang，Isaac L。 Chuang，Rainer Blatt

今天，在《科學》雜志最新發(fā)表的一篇論文中，量子計算機有史以來第一次以可擴展的方式，實現(xiàn)了 Shor 算法。

MIT和奧地利Innsbruck大學的研究者們報告說，他們設計并搭建了一臺在離子陷阱中只有5個原子的量子計算機。這臺計算機使用激光脈沖來在每一個原子上實行Shor的算法，分解數(shù)字15的質(zhì)因數(shù)。這個系統(tǒng)的設計允許通過增加原子和激光來搭建更大型更快速、能夠分解更大數(shù)字的質(zhì)因數(shù)的量子計算機。

“我們展示了，Shor的算法——目前為止已知的最復雜的量子算法——能夠以一種可擴展的方式實現(xiàn)：你需要做的一切就是，到實驗室去，用上更多的技術(shù)，然后你應該就能做出更大的量子計算機了，”Isaac Chuang說道，他是MIT物理學教授、電機工程和計算機科學教授，“量子計算機可能還是要耗費大量金錢才能造出來——暫時來看你還不會去造一臺量子計算機然后把它放在你的書桌上——不過現(xiàn)在它更多地成為了一個工程問題，而不是一個基礎物理學問題。”

穿越量子森林

在經(jīng)典計算中，用0和1的組合來表示數(shù)字，而計算是根據(jù)算法的“指導”來進行的，通過操作這些0和1將輸入的數(shù)字轉(zhuǎn)變?yōu)檩敵龅臄?shù)字。與經(jīng)典計算不同，量子計算依賴于原子標度的單位，或者叫做“量子比特”，它們可以同時是0和1——這種狀態(tài)被稱作“疊加態(tài)”。處于疊加態(tài)時，一個量子比特在本質(zhì)上可以同時進行2個獨立的計算流，使得計算效率大大高于經(jīng)典計算機。

2001年時，量子計算領(lǐng)域的開拓者之一，Chuang，設計了一臺基于一個分子的量子計算機，這個分子可以處于疊加態(tài)，通過核磁共振來進行操作，分解數(shù)字15的質(zhì)因數(shù)。實驗結(jié)果發(fā)表在了《自然》雜志上，這是第一次以實驗的方式實現(xiàn)Shor的算法。不過這個系統(tǒng)是無法擴展的：隨著加入的原子數(shù)量增多，控制這個系統(tǒng)變得越來越難。

“一旦你有太多的原子，它就好像成了一片森林——很難逐次控制單個原子，”Chuang說道，“難點在于，如何在一個分離程度足夠高的系統(tǒng)里實現(xiàn)這個算法。這樣的系統(tǒng)在量子力學的狀態(tài)里可以維持足夠久的時間，讓你能夠真正有機會完成整個算法。”

“直白明了的可擴展性”

Chuang和他的同事們現(xiàn)在終于研究出了一種全新的、可擴展的量子系統(tǒng)，能夠高效地分解質(zhì)因數(shù)。一般來說，分解數(shù)字15的質(zhì)因數(shù)需要用到12個量子比特，但是他們找到了一種方法使得對量子比特的需求降低到5個，每個量子比特都用一個單一原子來表示。每個原子都能處于疊加態(tài)，同時處在兩種不同的能量態(tài)中。研究者們在其中4個原子上使用激光脈沖來達到“邏輯門”——或者說Shor算法的元素——的效果。計算結(jié)果隨后由第5個原子來儲存、傳遞、提取、循環(huán)利用，由此以并行的方式實行了Shor的算法，用到的量子比特數(shù)量大為降低。

這支團隊通過在離子陷阱中控制這些原子來讓量子系統(tǒng)保持穩(wěn)定。量子陷阱中，他們在每個原子上都移除一個電子，讓它們帶電，隨后通過電場來擺放原子的位置。

“通過這種方式，我們能夠精確地知曉某個原子的位置，”Chuang解釋道，“然后我們用同樣的方式處理幾微米之外的另一個原子——這個距離大約是人類頭發(fā)寬度的1/100。把一些這樣的原子放在一起的話，它們?nèi)匀挥邢嗷プ饔茫驗樗鼈儙в须姾伞＿@種相互作用讓我們能夠進行邏輯門的操作，而邏輯門的操作帶來了實現(xiàn)Shor算法的基礎。無論我們把系統(tǒng)做得多大，我們都可以對其中任何一個原子進行邏輯門操作。”

Chuang的團隊首先完成了量子計算機的設計，隨后他在Innsbruck大學的同事基于他的理論方法搭建了一臺實驗設備。他們讓這個量子系統(tǒng)分解數(shù)字15的質(zhì)因數(shù)——這是能有意義地展示Shor算法的最小數(shù)字。在對答案沒有先驗知識的情況下，這個系統(tǒng)返回了正確的質(zhì)數(shù)，置信度超過99%。

“我們預見到了它未來能擁有直白明了的可擴展性——一旦儀器能夠捕獲更多的原子、用更多的激光束來控制激光脈沖，”Chuang說道，“我們沒有看出有任何物理學的理由阻止它成真。”

IBM物理科學高級主管Mark Ritter表示，這支團隊通過循環(huán)利用量子比特的方式將量子系統(tǒng)所需的資源降低了1/3——這是通往擴大量子計算規(guī)模的路上很小卻很重要的一步。

“將最新的技術(shù)改進1/3是很好的事，”Ritter說道，不過真正將系統(tǒng)擴大“需要的量子比特數(shù)量是現(xiàn)在的幾個量級，而這些量子比特必須穿梭在更先進的、有數(shù)以千計同時發(fā)射的激光控制脈沖的陷阱中。”

如果這支團隊能夠成功地向系統(tǒng)中加入更多量子元件，Ritter說，他們將會達成一項長期沒有人能完成的成就。

“Shor的算法是第一個不容小覷的量子算法，擁有對經(jīng)典算法進行指數(shù)級加速的潛力，”Ritter說道，“許多研究者都在關(guān)注量子計算，因為它或許能為算法帶來可觀的加速效果。因此，將Shor算法實現(xiàn)出來這件事能夠與經(jīng)典計算中的‘Hello， World’相提并論。”

這一切最終對于未來的加密機制來說有什么意義呢？

“好吧，一個影響是，作為一個國家，你可能不希望使用某些加密方法來儲存你的機密信息——那些基于分解質(zhì)因數(shù)是一個難以操作的問題而開發(fā)的加密方法，”Chuang說道，“因為當這些量子計算機開始進入使用階段時，你將能夠解密所有過去使用這些方法加密的機密文件。”

這個研究獲得了美國高級情報研究計劃署（IARPA）和MIT-Havard超低溫原子中心（一所國家科學基金會物理前沿中心）的支持。