兩位華人76頁論文解決量子領(lǐng)域核心問題：首次證明偽隨機(jī)性真實(shí)存在

作者：量子位 2025-04-02 09:40:00

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

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

事情是這樣的。

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

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

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

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

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

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

同時(shí)，MIT量子計(jì)算研究員Alexander Poremba也表示：

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

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

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

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

要想理解這項(xiàng)研究，我們首先需要了解隨機(jī)幺正（Random unitaries）這個(gè)概念。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

研究方向?yàn)榱孔佑?jì)算及其對密碼學(xué)、復(fù)雜性理論和物理學(xué)的影響。

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

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

其研究方向?yàn)椋?/span>

責(zé)任編輯：張燕妮來源：量子位