量子計算核心突破!Shor算法實現或使密碼成擺設

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

互聯網時代，密碼和網絡安全是通信的基礎，無論是微信聊天，還是淘寶交易，都需要密碼技術保障個人隱私和財產安全。

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

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

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

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

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

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

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

Shor算法

整數的質因數分解，進入多項式的時間

早在1994年，Peter Shor就發明了一個量子算法（Shor算法），在整數的質因數分解上，能實現

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

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

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

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

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

《科學》雜志最新論文

論文標題：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

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

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

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

穿越量子森林

在經典計算中，用0和1的組合來表示數字，而計算是根據算法的“指導”來進行的，通過操作這些0和1將輸入的數字轉變為輸出的數字。與經典計算不同，量子計算依賴于原子標度的單位，或者叫做“量子比特”，它們可以同時是0和1——這種狀態被稱作“疊加態”。處于疊加態時，一個量子比特在本質上可以同時進行2個獨立的計算流，使得計算效率大大高于經典計算機。

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

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

“直白明了的可擴展性”

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

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

“通過這種方式，我們能夠精確地知曉某個原子的位置，”Chuang解釋道，“然后我們用同樣的方式處理幾微米之外的另一個原子——這個距離大約是人類頭發寬度的1/100。把一些這樣的原子放在一起的話，它們仍然有相互作用，因為它們帶有電荷。這種相互作用讓我們能夠進行邏輯門的操作，而邏輯門的操作帶來了實現Shor算法的基礎。無論我們把系統做得多大，我們都可以對其中任何一個原子進行邏輯門操作。”

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

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

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

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

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

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

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

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

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