量子領(lǐng)域的一個核心開放問題，就這樣被兩位華人研究員解決了？！

事情是這樣的。

一直以來，量子的隨機性在計算和密碼學(xué)中極為有用。

一方面，它可以用來提升算法效率、優(yōu)化復(fù)雜系統(tǒng)模擬，還能驗證量子計算結(jié)果的可靠性；另一方面，量子隨機性可用于生成真正隨機的密鑰，增強密鑰分發(fā)的安全性，從而保障信息安全。

但問題是，實現(xiàn)這種隨機性的成本很高。

因此，無數(shù)科學(xué)家們嘗試找出偽造這種隨機性的方法。

直到去年十月，華人研究員Fermi Ma和黃信元發(fā)表了一篇論文，提出了一種偽造隨機性的新方法。

按量子雜志的說法，他們的新方法“優(yōu)雅且安全”，還無需大量計算開銷。

同時，MIT量子計算研究員Alexander Poremba也表示：

• 我們首次有了確鑿的證據(jù)證明偽隨機性是一個真實存在的概念。

具體咋回事兒？下面咱們接著看。

核心用10頁論文證明了PRUs的存在

概括而言，兩位作者用76頁論文（核心證明過程僅10頁）證明了假設(shè)存在任何量子安全單向函數(shù)的情況下，偽隨機幺正態(tài)（PRUs）的存在。

要想理解這項研究，我們首先需要了解隨機幺正（Random unitaries）這個概念。

隨機幺正在量子計算中扮演著核心角色，它們是量子霸權(quán)實驗、量子算法和各種加密原語設(shè)計的基礎(chǔ)。在物理學(xué)中，它們用于模擬高度混亂的過程，例如黑洞動力學(xué)。

然而，隨機幺正變換需要大量時間（通常是指數(shù)級的）和計算資源來實現(xiàn)，因此現(xiàn)實層面很難操作。

于是乎，PRUs應(yīng)運而生。一旦證明存在PRUs，隨機幺正變換也能變得更加高效。

2017年，一篇論文引入了PRUs的概念，并試圖用一種結(jié)構(gòu)上可控的方法來模擬Haar隨機酉矩陣。

p.s. Haar隨機酉矩陣是數(shù)學(xué)家Alfréd Haar在20世紀(jì)初提出的概念，它定義了某種最純粹的“隨機”，即每個可能狀態(tài)都等概率地出現(xiàn)在酉矩陣空間里。

不過遺憾的是，作者未能證明其構(gòu)造的PRUs方法能像真正的Haar隨機酉矩陣一樣。

而在前人研究基礎(chǔ)上，兩位華人研究員首次證明了PRUs的存在。

從論文介紹來看，他們在存在量子安全單向函數(shù)的合理假設(shè)下，成功證明了標(biāo)準(zhǔn)PRUs和強PRUs的存在。

具體而言，他們使用了“凈化”（purification）這一量子信息理論中的老技術(shù)。

其核心思想是，一個復(fù)雜隨機系統(tǒng)，其實可以看成是一個更大、但狀態(tài)確定的系統(tǒng)的一部分。

通過提出“路徑記錄模擬”（path-recording simulation）這一新方法，他們能把酉算子在運算過程中的一些關(guān)鍵信息記錄下來，這樣就可以通過分析這些記錄來了解酉算子的特點，為后續(xù)的證明提供了一個有用觀察角度。

然后借助一種特殊函數(shù)——單向函數(shù)，即從一個方向計算很容易，但幾乎很難從結(jié)果反推回去，他們發(fā)現(xiàn)了一個之前被認(rèn)為是“弱偽隨機”的構(gòu)造，實際可以看作“真?zhèn)坞S機”。

• 在保持簡單結(jié)構(gòu)的同時，偽裝成Haar隨機酉矩陣。

此外，他們還證明了對于一些研究Haar隨機酉矩陣的量子算法，有一種高效的模擬方法，且模擬誤差幾乎可以忽略不計。

這一證明是通過仔細(xì)研究量子算法在執(zhí)行過程中的各種情況，再利用“路徑記錄模擬”記錄的信息，巧妙地設(shè)計出模擬過程來實現(xiàn)的。

論文最后，他們靈活運用膠合引理（能把證明過程中不同部分的結(jié)果連接起來的方法）完整地證明了偽隨機幺正態(tài)是存在的。

完整證明過程可查看以下章節(jié)部分：

作者為兩位華人

論文作者一共兩位，均為華人。

Fermi Ma，目前是西蒙斯-伯克利博士后研究員，于2021年獲得普林斯頓大學(xué)博士學(xué)位。

研究方向為量子計算及其對密碼學(xué)、復(fù)雜性理論和物理學(xué)的影響。

黃信元，目前是谷歌量子人工智能的高級研究科學(xué)家，這項工作是在他訪問西蒙斯計算理論研究所時進行的。

個人主頁顯示，他今年將加入加州理工學(xué)院任理論物理學(xué)助理教授。

其研究方向為：

• 量子機器何時能夠比傳統(tǒng)機器學(xué)習(xí)和預(yù)測得更好？
• 如何加速/自動化量子和物理科學(xué)的發(fā)展？
• 經(jīng)典機器和量子機器可以學(xué)習(xí)和發(fā)現(xiàn)哪些物理現(xiàn)象？

論文：
https://arxiv.org/pdf/2410.10116