如何把量子計算機調教成終極隨機數生成器？_風聞
返朴-返朴官方账号-关注返朴（ID：fanpu2019）,阅读更多！2019-07-17 11:36
**來源 |**Quantamagazine
**翻譯 |**Leo
審校**| 劉金國**
編輯**| 陳安林**
來源：集智俱樂部
隨機數在計算機和密碼學等領域有廣泛的應用，目前已經有了許多生成隨機數的方法。但事實上，任何基於經典力學的過程所產生的隨機數，本質上都不是真隨機的。而量子世界特有性質使得可以從中產生可以驗證的純隨機 (pure random) 數。本文將介紹兩個把量子計算機變成隨機數製造工廠的技術。
我們的目標是獲得一個完全隨機且滔滔不絕的 01 數據流
如果你在一個計算機科學家的聚會上談論“量子優勢”（quantum supremacy），很可能會收到白眼。量子優勢是指，一台量子計算機能夠輕鬆地解決那些傳統計算機無法解決的某些特定的難問題，從而超越傳統計算機。然而遺憾的是，這些所謂量子計算機能輕鬆解決的難問題在現實中並沒有太多用武之地，這也就不奇怪為何會遭到白眼了。
但是，現在有傳言説，Google 的量子處理器將能夠實現這一目標。量子優勢終於能夠在一個方面得以應用——純隨機數生成。
在我們所使用的計算與通信基礎設施中隨機數的生成是極為重要的環節。特別是當涉及到數據加密問題時，隨機數生成就尤為重要。因為，從日常通信到金融交易乃至國家機密一切都被隨機數保護。
想象一個數列具備這樣的特徵：真正可以驗證的隨機性——永遠無法預測下一時刻這個數列會出現哪個數字。但這樣的數列極其難以獲得。
量子計算機能可能攻破這一難題。研究者最初做這樣任務可能只是為了展示量子計算機的威力所在，但是也有可能生成真正可以驗證的隨機數。“我們非常激動，”加州大學聖巴巴拉分校的物理學家、谷歌量子計算項目負責人 John Martinis 説，“我們希望這是量子計算機首次得以應用。”
隨機性與信息熵隨機性和量子理論就像打雷時下雨一樣，是相伴相生，量子理論必然會帶來隨機性。在量子世界中，系統常常處於組合狀態中——也就是所謂的“疊加”態。但是，當你去測量一個系統時，該系統就會塌縮到其中的某一種狀態。雖然量子理論允許我們去計算測量時出現不同狀態的概率，但從本質上來説，出現什麼結果是具有隨機性的。
物理學家一直都在試圖去利用這種關聯去製造隨機數生成器。這些都依賴於對某種量子疊加態的測量。儘管這樣的系統已經能夠滿足絕大多數人對於隨機性的需求，但卻很難實現。而且，要證明這些生成的隨機數的隨機性並不容易。最後，很多有效的驗證隨機性的方法要求把多台設備安置在彼此相隔甚遠的地方。
2018年，谷歌人工智能實驗室造出了一款名為 Bristlecone 的 72 量子比特 (qubit) 的量子處理器。
近期有學者提出了一個提議：如何從單個設備中獲得隨機性——僅靠一台量子計算機。這被稱之為採樣任務（sampling task）。這也是首批進行測試的量子優勢。我們可以這樣理解這項任務：
假設，有一個裝滿卡片的盒子。每一個棋子上都有一些諸如 000、010、101 的 01 序列。如果是三位數字，那麼一共有 8 種可能，但是每一種卡片都不是唯一的，也許會有 50 張“010”，25張 “001”。這些卡片數量的分佈情況決定了每次隨機抽取出一張卡片上數值的可能性。在上面那個例子中，拿出一張“010”的可能性是拿出“001”的兩倍。
對於一個採樣任務來説，其中包含着一個算法：一個盒子中裝有以一定概率分佈的各種卡片，從這個盒子中拿隨機抽出一張卡片。一種卡片的分佈概率越大，那麼它被算法抽出的可能性也越大。
當然，一個抽象的算法並不會真的把手伸到某個盒子裏去摸卡片。實以輸出一個50位長度的隨機數為例，實際上，這個算法首先會給出一個指定了這50位數所有可能的輸出組合的概率分佈，然後隨機輸出一個二進制數。
我希望這是量子計算機上的第一個應用。
——John Martinis，谷歌量子計算項目主管
對於一台傳統計算機來説，隨着輸出位數的增加，計算複雜度會指數快的增加。但是對於一台量子計算機而言，無論是 5 位還是 50 位隨機數的生成都一樣直接。
量子計算機從所有的量子比特（qubits）的某個特定狀態開始運算（比如，初始態為 0）。就像傳統計算機使用邏輯電路操縱比特一樣，量子計算機使用量子等價物（量子門）操縱量子比特。
但是有所區別的是，量子門可以把量子比特置於奇怪的狀態。比如，有一種門可以把始態為 0 的量子比特置入 0、1 疊加的狀態中。這時如果你去測量這個量子比特的狀態，它就會以相等的概率隨機的塌縮至 0 或 1 狀態。
更令人驚奇的是，同時作用於兩個或多個量子比特的量子門會導致這兩個量子比特發生糾纏。在這種情形下，量子比特的狀態的測量結果就會出現統計關聯。這時候，量子比特的狀態就只能用量子狀態來描述了。
如果把眾多量子門連接在一起，讓它們以特定的順序作用於一組量子比特，就創建了一組量子電路。以我們上面提過的例子來説，為了得到 50 位的隨機字符串，我們可以構建一個量子電路，把 50 個量子比特放在一起，形成一個疊加態，這個疊加態就包含了你可以調整的數位分佈。
當這些量子比特被測量時，它們整體的疊加態就會隨機的塌縮成一個 50 位的字符串。其中，所生成字符串的概率分佈由量子電路決定。測量這些量子比特就好像是蒙上眼睛，伸手從盒子中摸出一個遵循該分佈的隨機字符串。
德克薩斯大學奧斯汀分校的計算機科學家 Scott Aaronson 表示：“具備技術可行性的第一個量子計算機應用可能就是隨機數生成。”
我們是如何得到這些隨機數的？其中至關重要的一點是，被量子計算機所採樣的 50 位字符串的信息熵很高。熵被用來度量無序程度和不可預測性，因此也就可以用來度量隨機性。德克薩斯大學奧斯汀分校的計算機科學家 Scott Aaronson 認為：“實際上，隨機數生成非常重要。”他提出了一個新的方案。“並不是因為生成隨機數是量子計算機上最重要應用，而是在於這可能是在實際技術條件限制下，第一個量子計算機應用。”
Aaronson 的隨機數生成協議看起來非常的簡單。一台傳統計算機從一個可信的信源接受幾個比特的隨機數，並把這個隨機數作為“種子”來決定量子門的類型和作用的先後順序，並由此生成量子電路“圖紙”。而後，傳統計算機把這個“圖紙”發送給量子計算機，由量子計算機來運行量子電路。最後，測量量子比特，得到生成的 50 位字符串併發送回去。
一次又一次地重複上以過程，比如，一個量子電路重複採樣 10 次。利用統計學原理，傳統計算機能保證得到的字符串的信息熵很高。Aaronson 和陳立傑合作的工作（部分尚未發表）表明：在特定可信的假設下，這些問題在計算上是困難的，沒有一台傳統計算機能夠在做到量子計算機所做的類似工作並得到同樣的信息熵。在經過檢查後，傳統計算機把所有得到的 50 位的字符串拼接在一起，並輸入給了一個經典算法。“它得到了一個幾乎完全隨機的長字符串。”Aaronson 説。
參考論文：
Complexity-Theoretic Foundations of Quantum Supremacy Experiments
論文預印本：
https://arxiv.org/abs/1612.05903
量子陷門 (Trapdoor)不過，Aaronson 的協議適合具備大約 50-100 個量子比特的量子計算機。當量子計算機中的量子比特超過這個閾值時，傳統的超級計算機也難以應用這項協議。還有另外一項使用量子計算機生成可驗證的隨機數的方案。該方案運用了一項現有的數學技術，這項技術有着一個嚇人的名字——無爪陷門函數（trapdoor claw-free function）。“這玩意聽起來挺唬人的。”加州大學伯克利分校的計算機科學家 Umesh Vazirani 這樣評價道。他和 Zvika Brakerski、Paul Christiano、Urmila Mahadev 以及 Thomas Vidick 一同設計了這個方案。
參考論文：
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
預印本網址：
https://arxiv.org/abs/1804.00640
還用我們之前提過的盒子來打比方，這一次我們不再是伸手去抽取字符串，而是放入一個 n 位字符串 x；盒子輸出另一個 n 位字符串。這個盒子可以以某個方式把輸入字符串映射到輸出字符串。但是這樣的盒子有一個特性， 對於每一個字符串 x，都存在另一個字符串，使得這兩個字符串能得到同樣的輸出。
換句話説，存在兩個唯一的字符串 x、y，他們能得到同樣的輸出字符串 z。於是這三個字符串 x、y、z 就被稱之為爪（claw）。用計算機科學的話來説，這個盒子就是一個函數。給定 x 或 y，計算出 z 非常的容易。但是，已知 x、z 求出 y ——找出爪——就不容易了。即便是對於量子計算機而言也並非易事。
Urmila Mahadev， Umesh Vazirani 和 Thomas Vidick（從左至右）通過將密碼學和量子信息處理技術結合在一起，開發出了一種隨機數生成器。
如果你想得到爪的唯一辦法就是知道一些內部信息，也就是所謂的陷門（trapdoor）。
Vazirani 和他的同事們不僅想通過這些函數讓量子計算機生成隨機數，而且也希望驗證量子計算機的行為遵循量子力學原理——這一點對於隨機數的可信性尤為重要。
在該協議中，量子計算機把輸入的 n 位量子比特置於所有 n 位字符串的疊加態中。而後，由傳統計算機發送一個關於量子電路的描述，該描述刻畫了要作用於疊加態的函數——無爪陷門函數。量子計算機實現這個量子電路，但是並不具備陷門的信息。
在這一階段，量子計算機所處在的狀態是：其中一組 n 位的量子比特處於疊加態（x 或 y），另一組則保存了把前文提到的函數作用於該疊加態的結果（未塌縮的 z）。這兩組量子比特糾纏在一起。
然後，量子計算機去測量第二組量子比特，該組量子比特則隨機的塌縮成輸出結果 z。而第一組量子比特則是 x 和 y 疊加態塌縮的結果。因為，輸入 x 或 y 都能得到輸入結果 z。
傳統計算機把 z 作為輸入，可以做兩項工作。大多數時候，它可以要求量子計算機測量其餘的量子比特。因為塌縮至 x 或 y 的概率是均等的，所以這也就相當於隨機地得到 0 或 1。
有時，為了檢測量子計算機的量子性，傳統計算機會提出一個特別的測量。該測量方法及其結果被設計為，只有具備陷門信息的經典計算機才能保證應答設備確實是量子計算機。Vazirani 和他的同事們表明，如果做出正確應答的設備沒有使用塌縮的量子比特，那就等於不使用陷門信息就計算出了爪。然而這是不可能的，所以，為了應答詢問，該設備內部至少導致了一位量子比特的塌縮（給出 0 或 1 的隨機數）。Vazirani 表示，該協議能在一台不受信任的量子計算機內部創造出防篡改的量子比特。
在每次詢問時，這種防篡改的量子比特能提供真正的隨機比特信息。由此，就能用一個詢問序列創造出長的隨機字符串。
這個方案可能比 Aaronson 的量子採樣協議更快，但是它也有一個明顯的缺陷。Aaronson 認為：“讓該協議包含 50 或 70 個量子比特並不現實。”
現在，Aaronson 在等待谷歌的系統得以實現：“他們做出的東西是不是足夠好，能得到實際應用。這是一個大問題。”
如果，結果確實如此的話。那就意味着，由單台量子設備生成的可驗證隨機數就要實現了。Martinis 説：“我們認為它能夠實用並且有市場潛力。這就是我們想要提供給人們的東西。”
本文經授權轉載自微信公眾號“集智俱樂部”。原題：How to Turn a Quantum Computer Into the Ultimate Randomness Generator，查看原文請戳“閲讀原文”。
特 別 提 示
1. 進入『返樸』微信公眾號底部菜單“精品專欄“，可查閲不同主題系列科普文章。
2. 『返樸』提供按月檢索文章功能。關注公眾號，回覆四位數組成的年份+月份，如“1903”，可獲取2019年3月的文章索引，以此類推。
相關閲讀
1 量子計算，從經典-量子混合計算開始 | 諾獎得主Wilczek專欄
3 張量網絡、量子材料計算與人工智能的未來：開源TensorNetwork | 文小剛點評