讓中央集體學習的量子科技究竟是啥？這個科普我已經做了五年（四）_風聞

導讀

　　分解300位和5000位的數字，量子算法會把所需時間從15萬年減到不足1秒鐘，從50億年減到2分鐘！

　　視頻鏈接：

　　西瓜視頻：

　　https://www.ixigua.com/6902292563307266573

　　本視頻發佈於2020年12月4日，播放量已超百萬

　　前三次我們説到，中央集體學習的量子科技，主要指的是量子信息（讓中央集體學習的量子科技究竟是啥？這個科普我已經做了五年（一）量子是什麼 | 袁嵐峯）。它分為量子通信和量子計算兩大領域，正如我們平時用的手機屬於通信，計算機屬於計算。這次我們就來講解量子計算。

　　量子信息學科內容

　　你可能早已聽説過，量子計算是真正的顛覆性技術，能夠做到很多現有的計算機做不到的事。但是，量子計算為什麼這麼厲害呢？很奇妙，大多數人的理解都是錯誤的。

　　媒體常見的説法是：量子計算機的運算速度特別快，比經典計算機快得多。這聽起來很容易理解，就好像486比386快，386比286快。如果媒體想解釋原理，還會説這是因為量子計算機是並行計算，一次能處理很多任務，而經典計算機一次只能處理一個任務。

　　並行計算

　　然而，這種話只能矇住外行。如果你對計算機科學稍有了解，你立刻就知道，並行計算並不是什麼特別的東西，現在的計算機就經常在用。例如所有的超級計算機，神威太湖之光、天河二號等等，都是用大規模並行計算達到超高速度的（中國超算全自主，重奪第一已出發 | 袁嵐峯）。

　　神威太湖之光

　　所以，量子計算真正的原理是什麼？我來向大家解讀一下。

　　這裏的關鍵在於，量子計算機不是幹什麼都特別快，而是隻對某些問題特別快，因為對這些問題能設計出快速的量子算法。也就是説，量子計算機優於經典計算機，並不是像486優於386那樣幹什麼都強，而是好比你的計算機能運行某個遊戲，而別人的計算機不能運行這個遊戲，所以在這方面你的計算機強。

　　量子計算機為什麼會有這樣的優勢呢？原因就在於量子力學三大奧義：疊加、測量和糾纏（讓中央集體學習的量子科技究竟是啥？這個科普我已經做了五年（二）量子力學三大奧義 | 袁嵐峯）。這是我們在前面兩期中講的，不瞭解的同學們請回去複習一下。

　　最基本的道理是，經典計算機的基本操作單元是比特，而量子計算機的基本操作單元是量子比特。比特好比開關，只有開和關兩個狀態。而量子比特好比旋鈕，有無窮多個狀態。所以顯然，量子比特有可能做到比經典比特更多的事。

　　具體而言，量子比特超越經典比特的辦法是這樣的。

　　如果有n個經典比特，每一個有兩個狀態，它們的組合就總共有2n個狀態。如果想知道一個操作對n個比特產生的效果，就需要把這個操作作用到這2n個狀態上，把所有的結果都試一遍。也就是説，需要2n次操作。

　　2n是個增長非常快的函數。學過數學的人都知道，指數增長比任何的多項式增長都要快，比如説比n10000都快。所以隨着n的增長，經典計算機的計算量很快就會爆炸。

　　指數增長比任何的多項式增長都要快

　　但對於量子比特，事情就不一樣了。一個量子比特有兩個基本狀態，一個一般的狀態等於這兩個基本狀態的疊加。對於n個量子比特的體系，基本狀態有2n個，一個一般的狀態等於這2n個基本狀態的疊加（讓中央集體學習的量子科技究竟是啥？這個科普我已經做了五年（三）量子糾纏 | 袁嵐峯）。

　　也就是説，n量子比特體系的一般狀態可以寫成

　　c(000…) |000…> + c(100…) |100…> + c(010…) |010…> + … + c(111…) |111…>，

　　其中每一個c都是一個係數，總共有2n個這樣的係數。

　　現在重點來了：對這樣一個一般的狀態做一次操作，就可以同時改變2n個係數，相當於對n個比特的經典計算機進行了2n次操作。一個頂2n個！

　　這是一個嚇死人的優勢。所謂量子計算機的優勢來自並行計算，實際指的就是這個意思。如果使用得當，這可以帶來指數級的加速。原來需要上億年的任務，現在可能一秒鐘就能搞定，這是多麼驚人的進步！

　　但是且慢，這一切有個前提，“如果使用得當”。什麼意思呢？因為把數據讀出來是大問題。

　　你要把這2n個數據讀出來，就需要做測量。但我們前面講過，測量的時候體系的狀態會發生突變，落到某一個基本狀態上面。結果就是，你雖然一下子獲得了2n個數據，但讀出的時候又只剩下一個了（量子計算機強在哪裏？不是因為能存下全世界的信息 | 袁嵐峯）。

　　因此，量子計算確實具有巨大的優勢，但這是個潛在的優勢，需要非常巧妙的算法才能發揮出來。只對少數特定的問題，人們設計出了這樣的算法。而對於大多數的問題，量子計算還沒有表現出任何優勢。

　　你也許會感到很失望，原來量子計算沒什麼用啊？別急。目前已知的能發揮量子計算優勢的問題雖然不多，但其中有些就非常重要，例如因數分解（factorization）和無結構數據庫的搜索。下面，我們就來解釋一下量子因數分解。

　　因數分解是什麼？就是把一個合數分解成質因數的乘積，例如21 = 3 × 7。只需要小學數學水平，就能理解這個概念。但重點在於，因數分解是一個經典的數學難題。

　　你也許會感到很奇怪，這有什麼難的？吶，分解一個小的數字當然很容易，你不管三七二十一就能分解21。但是來分解下面這個數看看：

　　267 - 1 = 147, 573, 952, 589, 676, 412, 927。

　　這是一個21位數。它是質數還是合數呢？這就遠不是一眼能看出來的了。

　　1644年，也就是李自成進北京、明朝滅亡的那一年，法國數學家梅森（Marin Mersenne，1588 - 1648）提出這個數是一個質數。

　　李自成

　　馬林·梅森

　　在那之後的很長時間裏，人們都這麼認為。直到1903年，清朝都快亡了，人們才發現它其實是一個合數，等於

　　193, 707, 721 × 761, 838, 257, 287。

　　大清亡了

　　為了分解這個21位數，消耗了一個朝代的時間！

　　因數分解為什麼這麼困難呢？因為沒有特別高效的算法。

　　如果讓我們分解一個數字N，我們能夠想到的最簡單的算法，就是從2開始一個個往上試。先問：它能不能被2分解？如果不能，再問：它能不能被3分解？這樣一個個試，直到根號N為止。如果到根號N都分解不了，説明它是個質數。由此可見，嘗試的次數大約是根號N。

　　這是個特別簡單也特別愚笨的算法。如果N表示成二進制有n位數，也就是N約等於2n，那麼計算量就約等於根號N即2n/2。這正是指數增長，所以隨着位數的增長，計算量很快就爆炸了。

　　顯然，數學家不會滿足於這麼愚笨的算法。經過幾百年的研究，人們提出了很多改進的算法，目前最高效的算法叫做“數域篩”（number field sieve）。這些算法確實快了很多，然而在基本面上沒有變化，計算量仍然是指數增長的。

　　比如説，一台計算機每秒做一萬億次運算，它用數域篩算法分解一個300位的數字需要15萬年，分解一個5000位的數字需要……50億年！地球的年齡也不過是46億年而已！所以，因數分解仍然是一個難題。

　　奇妙的是，分解不開對我們是一件好事，——可以用來保密。當今世界最常用的密碼體系之一叫做RSA，它就是基於因數分解的困難性設計出來的。RSA這個名字，是三位發明者李維斯特（Ron Rivest）、薩莫爾（Adi Shamir）和阿德曼（Leonard Adleman）的姓氏首字母縮寫。

　　RSA密碼體系的三位發明者

　　大致而言，RSA的操作方式是這樣的。讓我們把信息的發送方叫做Alice，接收方叫做Bob。

　　首先，Bob取兩個很大的質數p和q，求出它們的乘積

　　N = pq。

　　這一步是很容易的。但是如果有人只知道N，想求出p和q，就是很困難的。

　　然後，Bob把N向全世界公佈，這叫做公鑰。把p和q藏好不公佈，這叫做私鑰。

　　註釋一下，密碼學裏的密鑰這個詞念mì yuè。鑰匙的鑰（yào）這個字是個多音字，在這裏念yuè。你去百度一下或者翻一下字典，就能找到這個答案。

　　百度百科的密鑰詞條

　　然後，Alice把想發送的信息用公鑰N加密，用公開信道發給Bob。Bob拿到密文，用自己的私鑰p和q就可以解密。其他人雖然拿到了密文，但分解不開N，算不出p和q，所以無法竊密。

　　公鑰密碼體制

　　這確實是一個非常巧妙的思想。在這個意義上，我們平時的網購、網上銀行、瀏覽網站等習以為常的做法，都是依靠因數分解的困難性保駕護航的。經常有無知的人説，學數學有什麼用，又不能用來買菜。但實際上，如果沒有數學，你買菜的時候錢早就被別人轉走了！

　　然而，RSA真的可靠嗎？這其實並沒有證明，只是個經驗而已。

　　永遠不能排除這種可能：將來有個聰明人發明一種高效的算法，一下子就解決了因數分解。甚至還有可能，這樣的算法已經發明出來了，只不過沒有公佈。

　　設想一下，如果你是美國情報部門的領導人，你的手下有人發明了破解RSA的算法，你會公佈嗎？顯然，你更可能採取的做法是悶聲發大財，在暗中破解別人自以為安全的密碼。

　　斯諾登爆料五眼聯盟

　　如果説這些擔心是“隱患”，那麼量子計算已經帶來了一個“明患”。前面談的因數分解算法都是經典計算機上的算法，其中最高效的是數域篩。但是在1994年，美國科學家肖爾（Peter Shor）提出了一種高效的量子因數分解算法。

　　彼得·肖爾（http://www-math.mit.edu/~shor/）

　　高效到什麼程度呢？分解一個n位數的計算量大約是n2。跟以前的指數增長相比，這是一個指數級的節約。舉個例子，同樣還是分解300位和5000位的數字，量子算法會把所需時間從15萬年減到不足1秒鐘，從50億年減到2分鐘！

　　現在，大家明白量子計算的威力了吧？

　　許多媒體説，量子計算機可以破解全世界所有的密碼。這話基本是可以成立的，很有可能現在的各種密碼都會被量子計算破解。不過要加個限制條件，——除了量子密碼之外。

　　只有魔法才能打敗魔法，只有量子才能打敗量子。量子密碼保密的基礎是物理原理，而不是數學，所以即使是量子計算也無法破解。關於量子密碼，我們會在後面介紹。

　　話説回來，量子計算只是在算法層面破解了RSA。而在硬件層面，量子計算機還遠沒有達到實用的程度。迄今為止，量子分解的最大的數是

　　291, 311 = 523 × 557。

　　這是科大的杜江峯和彭新華等人在2017年實現的，他們在算法上又做了不少改進（https://arxiv.org/abs/1706.08061）。

　　杜江峯和彭新華等人2017年用量子算法分解291311的論文（https://arxiv.org/abs/1706.08061）

　　這離破解RSA有多遠呢？目前常用的RSA密鑰長度是1024，也就是説，密鑰是二進制的1024位數。上面提到的291, 311是一個十進制的六位數，換算成二進制是一個19位數，離1024位還遠。

　　因此，我們現在還在用RSA。但數據安全工作者都知道，這種狀況不會持續太久了。

　　例如谷歌CEO預測，加密技術的終結可能在5年內到來（美國哈德遜研究所發佈《高管的量子密碼指南：後量子時代中的信息安全》| 中國信息協會量子信息分會）。在我看來，無論是5年、10年還是15年，這個具體的時間並不重要，真正重要的是要意識到這個明確的趨勢，未雨綢繆。

　　谷歌首席執行官預測，加密技術的終結可能在5年內到來

　　那麼，量子計算什麼時候能實用呢？下次，我們就來介紹這方面的進展。