IPFS星際大陸
好礦機 大陸造
作者：Neo Ge
校驗：Junkai Zeng
最近有很多朋友問到我關於量子計算機的問題，其中最大的隱憂是擔心量子計算會憑藉超強算力，使得加密貨幣不再加密，甚至摧毀區塊鏈網絡。先說答案：不會。不過要想明白這一點，就要了解什麼是量子計算和區塊鏈的密碼算法。
本文特別鳴謝Junkai Zeng提供的技術支持，他不僅是我的老同學，同時還是維吉尼亞理工物理學博士，研究方向便是量子計算，目前在LA一家紅杉投資的量子公司就職。
量子計算
要想明白量子計算，我們就要了解什麼是經典計算。我們要知道經典計算機發展道路上遇到的一個瓶頸叫做摩爾定律Moore’s Law，即集成電路上可容納的電晶體數量，每隔兩年便會增加一倍。
這就導致電晶體的體積越來越小，當它小到約2nm的時候，由於2nm級別上的電晶體只能容納10個原子，電子的行為將不再服從傳統的半導體理論，而是遵循量子力學。而隨著電晶體集成度的提高，晶片產生的熱量也會越來越高。
這些負面的影響都嚴重阻礙了經典計算機的發展。在這種擔憂之下，人們想出了諸如光子計算機、生物計算機、量子計算機等解決方法。
摩爾定律 - 集成電路晶片上電晶體的數量 (1971-2018)
人們為什麼這麼看重量子計算機？
首先，我們要知道經典計算機的運算是通過邏輯電路來完成的，二進位的1和0在計算機中代表邏輯運算，又叫布爾代數。
1代表真（高電平），0代表假（低電平）。
最常見的邏輯運算是與、或、非這三種。舉個例子，真與真結果是真，真與假結果是假；非真即假，非假即真。這些運算都是通過一個個邏輯門來完成的，其中這些邏輯門有可逆的也有不可逆的。比如非門輸入一個1（比特真），輸出為一個0（比特假），所以非門就是可逆門，因為我們可以通過輸出0（比特假）倒推出輸入1（比特真）。但如果一個與門的輸出是0（比特假），那麼輸入的比特有三種可能，分別是00、01、10，我們無法明確的一對一映射回輸入，所以與門就是不可逆門。本來兩個比特的信息通過與門之後變為一個比特的信息，這裡丟掉了一個比特的信息。
Landauer原理
Rolf Landauer
1961年，IBM工程師Rolf Landauer發現每擦除一個比特的信息需要熱力學成本，即產生至少kTln2的熱量，而寫入信息則不需要熱力學成本。其中，k是玻爾茲曼常數，T是環境溫度。這就是大名鼎鼎的Landauer原理，通過這個原理我們知道信息同樣具備物理性質。而經典計算機中基本上都是不可逆操作，所以經典計算機會產生越來越多的熱量。
這是Landauer在思考麥克斯韋妖的問題上得出來的結論：因為處理信息是要付出代價的，而小妖的記憶不可能是無限的，它總會刪除一些記憶導致熵增，所以小妖不能存在。
於是人們就想如果將經典計算機中的不可逆操作轉換成可逆操作，那問題不就解決了嘛。理論上，一個稱為么正變換的操作 – 對量子態的一種處理手段，放在經典計算機上剛好能解決散熱的問題。然而，經典計算機雖然擅長微分方程類問題，即模擬經典物理系統。但如果仍用微分方程來描述量子物理系統，經典計算機難以擔此重任。所以後來費曼等物理學家提出直接將經典比特轉換成量子比特，直接使用量子來模擬量子系統。（我們在文章開頭視頻中聽到的就是理察·費曼的聲音）
量子的天然優勢 – 並行計算
在經典計算機中，我們使用二進位來提高計算效率。假如你想讓經典計算機計算100+100，首先要將十進位的100轉換成二進位的1100100。在經典計算機中，需要使用7個不同狀態的電晶體來表示二進位的1100100。通俗來講，一個電晶體就是一個比特位，且只能表示1或0（高電平或低電平）。量子計算機不同，一個量子的雙態系統就是一個比特位，叫量子比特qubit。
雙態系統就像是電子的自旋、光子的偏振，最通俗的解釋是薛丁格的貓。薛丁格的貓在沒有進行觀測的時候，從量子力學角度來看，它既死又活，處於死和活的疊加態，這種狀態遵循的是量子的態疊加原理。假如我們把經典計算機中的電晶體換成薛丁格的貓，一個薛丁格的貓可以同時代表1和0，而不是經典計算機中的1或0了。兩個薛丁格的貓可以表示00、01、10、11四種狀態，而經典計算機中兩個比特位只能取這4種狀態之一。
那麼對於n個比特位，經典比特只能表示1個數，而量子比特在理論上可以同時表示2^n次方個數，這就是經典計算機和量子計算機的最大區別。2^n這種呈指數增長的碾壓式誘惑使得人們對於量子計算機有了這麼大的興趣 – 也就是天然並行計算的好處。
薛丁格的貓
如何實現量子計算機
難點1：拿什麼來做量子比特？
從物理學家的角度來說，理論上兩能級量子體系都可以作為量子比特。比如電子的自旋在沒有進行測量的時候處於既上又下的疊加態，一旦測量就會出現要麼朝上要麼朝下的本徵態。
電子的自旋
難點2：量子計算機的算法？
由於算法是計算機的靈魂，而經典算法只適用於經典比特，就算做好量子晶片，經典算法也不能在量子晶片上使用。1994年貝爾實驗室的彼得·秀爾發表了可以進行大數質因數分解的秀爾算法。
彼得·秀爾
質因數分解問題是一個NP問題，也就是在經典算法中它的複雜度不能夠在多項式時間內完成。一般的算法進行質因數分解複雜度是O即e^n，n指這個數用二進位表示的位數。目前使用最快的經典超算進行一個300位數（十進位）的質因數分解，需要花費約15萬年的時間。這也是為什麼大數的質因數分解可以用來進行加密的原因，因為幾乎沒有可能通過經典計算機暴力算出哪兩個質數相乘來解密。
但秀爾算法可以將複雜度降到 (logN)^3，也就是說秀爾算法將一個NP問題變成了P類問題。使用秀爾算法同樣進行300位數的質因數分解，理論上需要不到1分鐘的時間。
除此之外，秀爾還解決了一個困擾物理學家十幾年的問題，假如用秀爾算法使用量子比特進行計算，結果仍是一堆量子比特，我們需要對結果進行測量。然而薛丁格的貓告訴我們，測量貓死活的概率各佔50%，所以理論上測得的結果還是隨機的。
秀爾告訴我們，通過使用秀爾算法，需要的數據會相干相長，不需要的數據相干相消。最後的測量正確結果的概率是1。由於如今銀行乃至政府的保密資料都是基於質數的RSA算法進行加密的，所以自從1994年秀爾算法公布後，量子計算就引發了世界各國政府的強烈興趣。就連美國國防高級研究計劃局DARPA也加入了這場爭奪（DARPA曾經提出並投資了網際網路、Unix系統和全球定位系統GPS等）。
2001年IBM的華裔研究員艾薩克·莊他們的研究團隊，通過核磁共振進行了秀爾算法演示，即5個氟原子和兩個碳原子組成的一個分子，用每個原子的核自旋來做量子比特，7個qubit相當於2^7也就是128個經典比特。用這臺迷你量子計算機使用秀爾算法進行了15的質因數分解，給出的結果是3和5，成功證明了秀爾算法是可行的。後來證明，秀爾算法也可以用於離散對數問題上的求解。量子計算機的算法，除了秀爾算法還有Grover、QAOA、VQE算法等，後面我們還會再次提到Grover算法。
難點3：如何保持量子的相干性？
量子的相干性很難保持，就算不對處於疊加態的量子進行測量，它也會和周圍的環境發生量子糾纏然後變成確定的狀態，即變成經典的，也就是俗稱的波函數坍縮，這個過程叫做量子退相干。為了抵抗量子退相干帶來的影響，我們主要有兩種方法：
量子糾纏
量子糾錯；和經典計算機類似，以犧牲資源為代價，比如使用8個量子比特位當1個用，有一兩個退相干沒關係，將少數退相干的量子糾正過來。使用糾錯碼存在兩個問題：一個是量子計算每一步的操作必須低於某個比例，這樣錯誤才可以被糾正，比如錯誤率低於1%；另一個是糾錯碼需要用大量物理層面的量子比特來編碼一個邏輯層面的量子比特，這些都給在硬體層面實現量子計算帶來了極大的障礙。
更好的技術操控量子系統：因為量子力學的一些性質，即使是實現同樣的操作，物理層面上用不同的方式去控制量子比特也將會帶來截然不同的保真度。通過使用更好的方式去優化這些操作，可以將錯誤率控制在量子糾錯的閾值之下，為實現更通用的量子糾錯鋪路。
至此，量子計算機在理論上就不存在什麼難題了。至於物理層面，量子晶片怎麼做、用什麼做。這就是目前各大機構的主要研究方向，要保證量子比特在保持相干性的同時做到集成化。典型實現量子比特的硬體實現方案，主要包括光學系統、半導體量子點、超導電路、冷原子、離子井等等。谷歌、IBM和阿里達摩院等業界研究機構致力於的便是通過超導電路實現量子晶片。
今年9月，谷歌公司宣布成功使用包含53個有效量子比特的處理器實現了「量子霸權」（Quantum Supremacy）。需要指出的是，「量子霸權」指的是實現了在某些問題上面量子計算可以做到用經典計算機無法做到的事情，實現了「量子」對「經典」的霸權，也就是一個新技術對舊技術的霸權，而非某個企業或者研究機構在國際上領先，從對其他企業和研究機構產生了霸權。
區塊鏈的加密算法
這裡，我們以比特幣為例子向大家介紹區塊鏈的加密算法。比特幣的加密算法有兩類三種，分別是橢圓曲線算法、SHA256哈希算法和RIPEMD160哈希算法。大致流程如下：
私鑰 -> 橢圓曲線算法 -> 公鑰 -> SHA256 -> RIPEMD -> SHA256 -> SHA256 -> 地址
其中單向箭頭意味著經典計算中算法不可逆推，從地址逆推不了公鑰，公鑰逆推不了私鑰。由於量子計算就是將經典計算中的不可逆變為可逆，為了方便闡述，我們從地址開始向回逆推。
哈希算法
比特幣運用的兩種哈希算法中，SHA256是SHA-2下細分出的一種算法，它是一種密碼散列函數算法標準，由美國國家安全局研發；RIPEMD (RIPE Message Digest) 也是一種哈希函數。對於對稱加密與哈希函數，存在量子攻擊，但危險性較小。Grover算法只能將經典計算下2^256的難度降低到依然是天文數字的2^128，而從公鑰到地址需要進行1次RIPEMD和3次SHA256哈希運算，所以在針對對稱加密顛覆性量子算法誕生之前，我們不必過多擔心。
由於比特幣挖礦採用的是SHA256算法，今後如果有一種遠優於Grover算法的量子算法誕生，且隨著時間的推移，量子計算機的速度越來越快、價格越來越低，那麼量子計算機的確會在比特幣挖礦方面超越經典計算機。但這個進程就像是從CPU挖礦到GPU挖礦再到ASIC挖礦一樣，我們完全不必擔心。
橢圓曲線算法
從公鑰逆推回私鑰的壁壘只有一個---橢圓曲線密碼學（Elliptic curve cryptography），簡稱ECC，這是一種建立公開秘鑰加密的算法，也就是非對稱加密。從數學角度來看，橢圓曲線可以這樣表示：
比特幣基於secp256k1曲線的橢圓曲線數字籤名算法（ECDSA）便是橢圓曲線其中的一種。由於橢圓曲線算法依賴於離散對數困難問題，而上文提到的秀爾算法又可以被用為離散對數的求解，所以理論上擁有一定有效量子比特的量子計算機會對比特幣的橢圓曲線算法造成威脅。
然而secp256k1曲線的安全性是2^128 ，所以就算秀爾算法將其複雜度降低到 128^3，理論上攻擊secp256k1曲線的量子計算機也至少要有1500個邏輯量子比特。考慮到要使用量子糾錯，實際上需要的物理量子比特將遠遠高於這個數字。
今年9月份谷歌宣布的迄今為止最大的通用量子計算機也只有53個物理量子比特，錯誤率極高不說，並且只能在接近絕對零度的實驗室條件下運行。與此同時，谷歌使用的超導晶片在擴展性上天然存在很多問題，所以如何在保持可以操控的基礎上增加更多的量子比特在可預見的將來都將是一個非常大的挑戰。雖然不能完全預測量子計算將以何種速度發展，但預計比特幣的256位ECDSA密鑰至少在2040年之前是安全的。
比特幣本身已經具有一些內置的抗量子特質，如果你有一個好的比特幣使用習慣，即一個錢包地址只使用一次，那麼你的公鑰只有當你花費比特幣時才會被廣播到全網。這時，量子計算機將只有極短的時間來破解你的私鑰，即從交易發送到交易信息被添加到區塊中的這段時間。
讓我們假設你並沒有一個好的比特幣使用習慣，量子計算機發展也突飛猛進，所有常用的公鑰算法都被破壞了。比特幣還有一個殺手鐧，那就是升級它的加密算法。眾所周知，如果技術手段能夠破解一種密碼，它就必然可以再製造出一種破解不了的密碼。當前，在針對量子安全的公鑰加密算法之中，比特幣專家傾向於偏愛基於Lamport籤名的加密系統。雖然Lamport籤名的計算速度非常快，但也主要有兩個缺點：
籤名會非常大，至少數個kB（比現在大40-170倍），這對比特幣的整體可擴展性將是非常不利的。
在創建每個秘鑰對時，你需要設置可使用此秘鑰籤名的有效最大數量。若籤名超過此數目將變得不再安全。但如果你每個地址只是用一次，這並不是一個大問題。
除此之外，在密碼學家對後量子密碼學的研究中，超奇異橢圓曲線同源密鑰交換（SIDH）也有望取代當前的常規橢圓曲線密鑰交換（ECDH）。基於高維度向量空間的密碼學，即格密碼學也會將破譯難度再提升一個宇宙量級，足以對抗量子計算。新的公鑰算法將作為軟分叉添加到比特幣，比特幣用戶只需將其比特幣發送到新創建的地址即可實現量子安全。
密碼學與計算機科學
我們研究量子計算機對於區塊鏈的挑戰時，很難不去反覆思考密碼學與計算機科學的關係。歷史的事實總是驚人的糾纏相似，破譯密碼，本是計算機誕生的源動力。
第二次世界大戰期間，計算機科學與人工智慧之父 – 艾倫·圖靈受僱於英國皇家海軍從事對德國機密軍事密碼的破譯工作。當時的納粹軍方擁有一套複雜而精密的通訊安全系統 – Enigma密碼機。它由一系列不斷隨機變化的轉子組成，其複雜性高達1京即1億億，以當時的破譯手段極難攻克。圖靈利用他設計的破譯機bombe先是破譯了Enigma，接著破譯了Tunny密碼在內的當時納粹軍方使用的幾乎所有等級的通信加密系統。這使得盟軍對德國的軍事指揮和計劃了如指掌，硬生生幫助盟軍提前至少兩年戰勝了納粹德軍，結束了第二次世界大戰。
艾倫·圖靈
圖靈提出一種將人的計算行為抽象掉的數學邏輯機，即圖靈機。後來現代計算機之父馮諾依曼運用馮諾依曼結構完成了圖靈機的實現。以他名字命名的圖靈測試，作為一種用於判定機器是否具有智能的測試方法被廣泛使用。圖靈在數學和邏輯方面的輝煌成就也為計算機和整個數字時代的發展制定了宏偉的藍圖。為了表彰他的開創性貢獻，以其名字命名的計算機界的諾貝爾獎 – 圖靈獎作為該領域最高的獎項於1966年被正式成立。
對於即將到來的量子時代，作為區塊鏈從業者的我們應該懷著敬畏與期待的心情，迎接它的到來。量子計算機的價值在於解決典型的NPC問題和其他如三體、七橋、蛋白質摺疊、地震預測、天氣預報等問題。量子計算機不是萬能的，它並不能取代經典計算機。
參考資料
[1] Martin Roetteler, Michael Naehrig, Krysta M. Svore, and Kristin Lauter. 「Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms」 Microsoft Research, USA (2017): 1706.06752
[2] Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John Schanck. 「Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3」 Quantum Physics (2016): 1603.09383
[3] 孫昌璞, 全海濤. 「麥克斯韋妖與信息處理的物理極限」 物理·42卷11期 (2013): 10.7693
[5] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends et al. 「Quantum supremacy using a programmable superconducting processor」 Nature 574, no. 7779 (2019): 505-510
[6] I. Stewart, D. Ilie, A. Zamyatin, S.Werner, M. F. Torshizi and W. J. Knottenbelt. 「Committing to quantum resistance: a slow defence for Bitcoin against a fast quantum computing attack」 Royal Society Open Science 5, no. 6 (2018): 180410
[7] Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, and Marco Tomamichel. 「Quantum attacks on Bitcoin, and how to protect against them」 Quantum Physics (2017): 1710.10377
[8] Zhe Zhou. 「MommyTalk」 YouTube (2019): https://youtu.be/OHTqCYCQJe0
星際大陸——打造新一代網際網路基礎。星際大陸成立於2018年，是堅定的IPFS生態建設者、 去中心化存儲踐行者，致力於為用戶提供分布式存儲伺服器、應用軟體開發、 分布式存儲伺服器託管、數據中心運營等服務。