2020年1月6日
如今,網上交易非常普遍。幾乎所有基於網絡的交易都受密碼保護,除了量子計算機之外,傳統計算機無法打破這種密碼。量子計算機確實可以輕鬆地向傳統的加密消息解密,可惜沒有計算機科學家能夠設計出一種協議(protocol)來證明量子計算機確實完成了所需要做的工作。要檢查量子計算機是否真的解密了消息,這很容易:只需讀取解密後的消息即可。但是,在某些情況下,量子計算的輸出無法真正告訴我們是否發生了任何量子計算。例如,我們使用量子計算機來模擬黑洞的演化。我們如何真正知道模擬實際上是由量子計算機完成?
量子驗證不僅是學術性質
在量子計算中最基本的問題是:如果您要求一個量子計算機來進行量子計算,您怎麼知道它是否真的按照您的指示進行,或甚至根本沒有做過任何事情?這問題稱為「量子驗證」(quantum verification)。
這個問題不僅是學術性質。研究人員希望量子計算機能夠對許多問題提供指數級的加速,從模擬黑洞周圍的行為到模擬大蛋白質如何折疊,但首先我們必須解決這個量子驗證問題。
一旦量子計算機執行了傳統計算機無法執行的計算,我們如何知道它是否正確呢?對普通計算機這不是問題,因為從理論上講,您可以自己檢查計算機計算的每個步驟,但是量子系統會抵抗這種檢查。一方面,它的內部工作異常複雜:要描述僅用幾百個量子位的計算機內部狀態,就需要比整個可見宇宙還要大的硬盤。
即使您有足夠硬盤空間來描述,也無法解決下一個問題:量子計算機的內部狀態通常由許多不同的非量子「經典」狀態疊加(superposition)而成(好像一隻同時死活的貓Schrodinger's cat)。一旦您測量了量子態,量子就會折疊(collapse)為經典態。如果你查看一個300量子位(qubit)的計算機狀態,基本上您看到的只是300個經典位(零和一)。
考慮到這些限制,計算機科學家很久以前就一直在想,量子計算機是否有可能提供任何鐵定的保證,以確保它確實完成了其聲稱的工作。
如果量子計算機可以解決傳統計算機無法解決的問題,這並不意味着解決方案將難以檢查。例如,分解大型因數問題,這任務被認為是經典計算機無法實現的,但量子計算機可以有效解決。然而,即使經典計算機不能分解一個數字,它可以輕鬆地檢查量子計算機的分解是否正確:只需要將這些因子相乘,看看它們是否能得出正確的答案。
但是計算機科學家相信量子計算機可以解決的許多問題都沒有此功能。換句話說,經典計算機不僅無法解決它們,甚至無法識別所提出的解決方案是否正確。有鑑於此,科學家們問能否提出任何協議,讓不具有量子觀察者來確實證明量子計算機做到了其聲稱的工作。
近幾年量子計算研究小組展示,量子計算機不必要向經典驗證者驗證其計算,只要用小型量子計算機向每一個量子位進行測量和驗證。
另一組研究人員表明,如果使用一對無法相互通信的量子計算機來進行量子計算,那麼一個完全經典的驗證程序可以檢查量子計算。但該方法是針對特定情況而量身定製的,無法概括。
近年來研究人員試圖得出一個「無條件」的結果,不必要假設量子計算機可以做什麼或不能做什麼。這就是所謂的「量子後」密碼學:即量子計算機也無法破解的密碼學。現今用於網絡交易的密碼學安全性取決於分解大量數據,其難度並非「量子後」:現代量子計算機可以輕鬆解決。這「無條件」方法的秘訣是使用密碼學來強迫量子計算機建立「秘密狀態」,這「秘密狀態」甚至量子計算機本身也不知道,只有我們的經典驗證程序才知道。這程序依賴於所謂的「活板門」(trapdoor)功能,該功能執行易但逆轉難,除非擁有秘密的加密鑰。該功能還必須是「二對一」的,每個輸出都對應於兩個不同的輸入。例如求數字平方的函數,每個輸出(例如9)都有兩個相應的輸入(3和-3)。
活板門核心功能 構建秘密狀態
有了這樣的功能,您可以讓量子計算機按如下方式創建秘密狀態:首先,您要求計算機為該功能建立所有可能輸入的疊加,這對於量子計算機來說實際上很容易。然後,您告訴計算機將該功能創建一個新狀態,該狀態是該功能所有可能輸出的疊加。輸入和輸出疊加將糾纏(entangled)在一起,換一種說法,如果你測量一個輸入將立即影響另一個輸出。
接下來,您要求計算機測量輸出狀態並告訴您結果。此測量將會令輸出狀態折疊,獲得眾多輸出的其中之一,同時輸入狀態會立即折疊以匹配它,因為輸出和輸入是糾纏的。例如,如果使用平方函數輸出狀態為9,輸入狀態將折疊為3和-3。
現在您可以應用活板門功能。您擁有活板門的秘密鑰,可以輕鬆找出構成輸入疊加的兩種狀態,但是量子計算機不能。而且,它不能簡單地通過測量輸入疊加來確定它的構成,因為這種測量會令輸入折疊,即使計算機找到兩個輸入之一,也無法知道另一個輸入。
要使活板門功能更強大,我們可以用一種名為「錯誤中學習」(learning with errors)的加密方法。記住,活板門的核心功能在構建一個甚至量子計算機本身也不知道的秘密狀態。
使用這些活板門功能,雲計算用戶能夠創建一個「盲」的量子計算來掩蓋其數據,即使雲計算機進行計算時也無法讀取它。
此後不久,科學家進一步完善了這些活板門功能,使用秘密狀態方法為量子計算機萬無一失地產生可證明的隨機數。
可惜,能夠構建秘密狀態並不代表已經找到量子驗證的協議,出發點在這裏:要檢查量子計算機首先要能夠測量每個量子位,經典驗證程序缺乏此功能。但是,如果能夠以某種方式迫使量子計算機自己執行測量並誠實地報告測量結果,這也許行得通。
棘手的部分是讓量子計算機在知道驗證者將要求哪種測量之前,承諾驗證者要測量的狀態——否則計算機很容易愚弄驗證者。
這就是秘密狀態方法發揮作用的地方:協議要求量子計算機首先創建一個秘密狀態,然後將秘密狀態與應該測量的狀態糾纏在一起,然後才讓計算機知道要執行哪種測量。
由於計算機不知道秘密狀態的構成,但驗證者知道,所以量子計算機不可能作弊。從本質上講,計算機要測量的量子位已「固定在加密石中」(set in cryptographic stone)。因此,如果測量結果看起來像是正確,驗證者可以確信它們是真實的。
「量子後」的密碼學標準
以上的一個驗證協議取決於一個假設:量子計算機無法破解「錯誤中學習」。目前,「錯誤中學習」被廣泛認為是「量子後」密碼學的領先候選者,甚至美國國家標準技術研究院(National Institute of Standards and Technology)很快就會採納它為新的密碼學標準,以取代當今可能會被量子計算機破解的密碼學標準,但是科學家警告,這並不能保證「錯誤中學習」永遠不會被量子計算機破解。
無論如何,以上的一個量子驗證協議應該是行得通的。量子計算機唯一可以欺騙這個協議的方法是有量子界天賦想出了如何破解「錯誤中學習」,這本身就已經是一個了不起的成就。
然而,這個量子驗證協議無望在不久將來能夠實現。目前,該協議需要太多的計算能力才能實用。但隨着量子計算機的發展以及研究人員簡化協議,這種情況在未來幾年可能會改善。
最後,計算機科學家認為量子計算和密碼學的統一並非故事的結局,而是新一代的初步探索。
作者為香港大學統計及精算學系講師
訂戶登入
下一篇: | 美伊衝突開年 金價支持偏強 |
上一篇: | 茅台股價潛在升幅兩成 |