兩位華人76頁論文解決量子領域核心問題：首次證明偽隨機性真實存在
量子領域的一個核心開放問題，就這樣被兩位華人研究員解決了？！
事情是這樣的。
一直以來，量子的隨機性在計算和密碼學中極為有用。
一方面，它可以用來提升算法效率、優(yōu)化復雜系統(tǒng)模擬，還能驗證量子計算結果的可靠性；另一方面，量子隨機性可用于生成真正隨機的密鑰，增強密鑰分發(fā)的安全性，從而保障信息安全。
但問題是，實現這種隨機性的成本很高。
因此，無數科學家們嘗試找出偽造這種隨機性的方法。
直到去年十月，華人研究員Fermi Ma和黃信元發(fā)表了一篇論文，提出了一種偽造隨機性的新方法。
按量子雜志的說法，他們的新方法“優(yōu)雅且安全”，還無需大量計算開銷。
同時，MIT量子計算研究員Alexander Poremba也表示：
我們首次有了確鑿的證據證明偽隨機性是一個真實存在的概念。
具體咋回事兒？下面咱們接著看。
核心用10頁論文證明了PRUs的存在
概括而言，兩位作者用76頁論文（核心證明過程僅10頁）證明了假設存在任何量子安全單向函數的情況下，偽隨機幺正態(tài)（PRUs）的存在。
要想理解這項研究，我們首先需要了解隨機幺正（Random unitaries）這個概念。
隨機幺正在量子計算中扮演著核心角色，它們是量子霸權實驗、量子算法和各種加密原語設計的基礎。在物理學中，它們用于模擬高度混亂的過程，例如黑洞動力學。
然而，隨機幺正變換需要大量時間（通常是指數級的）和計算資源來實現，因此現實層面很難操作。
于是乎，PRUs應運而生。一旦證明存在PRUs，隨機幺正變換也能變得更加高效。
2017年，一篇論文引入了PRUs的概念，并試圖用一種結構上可控的方法來模擬Haar隨機酉矩陣。
p.s. Haar隨機酉矩陣是數學家Alfréd Haar在20世紀初提出的概念，它定義了某種最純粹的“隨機”，即每個可能狀態(tài)都等概率地出現在酉矩陣空間里。
不過遺憾的是，作者未能證明其構造的PRUs方法能像真正的Haar隨機酉矩陣一樣。
而在前人研究基礎上，兩位華人研究員首次證明了PRUs的存在。
從論文介紹來看，他們在存在量子安全單向函數的合理假設下，成功證明了標準PRUs和強PRUs的存在。
具體而言，他們使用了“凈化”（purification）這一量子信息理論中的老技術。
其核心思想是，一個復雜隨機系統(tǒng)，其實可以看成是一個更大、但狀態(tài)確定的系統(tǒng)的一部分。
通過提出“路徑記錄模擬”（path-recording simulation）這一新方法，他們能把酉算子在運算過程中的一些關鍵信息記錄下來，這樣就可以通過分析這些記錄來了解酉算子的特點，為后續(xù)的證明提供了一個有用觀察角度。
然后借助一種特殊函數——單向函數，即從一個方向計算很容易，但幾乎很難從結果反推回去，他們發(fā)現了一個之前被認為是“弱偽隨機”的構造，實際可以看作“真?zhèn)坞S機”。
在保持簡單結構的同時，偽裝成Haar隨機酉矩陣。
此外，他們還證明了對于一些研究Haar隨機酉矩陣的量子算法，有一種高效的模擬方法，且模擬誤差幾乎可以忽略不計。
這一證明是通過仔細研究量子算法在執(zhí)行過程中的各種情況，再利用“路徑記錄模擬”記錄的信息，巧妙地設計出模擬過程來實現的。
論文最后，他們靈活運用膠合引理（能把證明過程中不同部分的結果連接起來的方法）完整地證明了偽隨機幺正態(tài)是存在的。
完整證明過程可查看以下章節(jié)部分：
作者為兩位華人
論文作者一共兩位，均為華人。
Fermi Ma，目前是西蒙斯-伯克利博士后研究員，于2021年獲得普林斯頓大學博士學位。
研究方向為量子計算及其對密碼學、復雜性理論和物理學的影響。
黃信元，目前是谷歌量子人工智能的高級研究科學家，這項工作是在他訪問西蒙斯計算理論研究所時進行的。
個人主頁顯示，他今年將加入加州理工學院任理論物理學助理教授。
其研究方向為：
- 量子機器何時能夠比傳統(tǒng)機器學習和預測得更好？
- 如何加速/自動化量子和物理科學的發(fā)展？
- 經典機器和量子機器可以學習和發(fā)現哪些物理現象？
