在量子世界中，不確定性是基本規(guī)則。一個(gè)粒子可以同時(shí)存在于多種量子狀態(tài)，直到被觀測(cè)的瞬間才“選擇”一個(gè)確定的結(jié)果。這種內(nèi)稟的隨機(jī)性不僅是量子力學(xué)的基礎(chǔ)，更是量子計(jì)算和現(xiàn)代密碼學(xué)領(lǐng)域需要的資源。然而，完美地生成和操控量子隨機(jī)性一直是一項(xiàng)成本高昂且極具挑戰(zhàn)的任務(wù)。但現(xiàn)在，一項(xiàng)突破性研究證明了我們可以用一種更為“經(jīng)濟(jì)”的方式，來(lái)可靠地模擬這種強(qiáng)大的隨機(jī)力量。
來(lái)自美國(guó)加州大學(xué)伯克利分校西蒙斯計(jì)算理論研究所的博士后研究員 Fermi Ma 和谷歌量子人工智能的高級(jí)研究科學(xué)家的黃信元（Hsin-Yuan Huang）在預(yù)印本網(wǎng)站arXiv上發(fā)布了題為《如何構(gòu)建隨機(jī)酉矩陣》（How to Construct Random Unitaries）的論文。
這項(xiàng)工作正面回應(yīng)并解決了量子信息科學(xué)領(lǐng)域一個(gè)長(zhǎng)期懸而未決的核心問(wèn)題：是否存在可以被高效構(gòu)建和運(yùn)行的量子電路，其行為與真正完全隨機(jī)的量子演化（即 Harr 隨機(jī)酉變換，Haar-random unitaries）在計(jì)算上無(wú)法區(qū)分？
他們的答案是肯定的，團(tuán)隊(duì)證明了這類被稱為“偽隨機(jī)酉算子”（PRUs，Pseudorandom Unitaries）的電路確實(shí)存在。這一結(jié)論建立在一個(gè)密碼學(xué)領(lǐng)域廣泛接受的基礎(chǔ)假設(shè)之上——即存在能夠抵抗量子計(jì)算機(jī)攻擊的“量子安全單向函數(shù)”（quantum-secure one-way function）。
隨機(jī)性的魅力與困境
在量子領(lǐng)域，理想的隨機(jī)性通常通過(guò)“Harr 隨機(jī)酉矩陣”來(lái)數(shù)學(xué)化描述。酉矩陣（Unitary matrix）代表了一個(gè)封閉量子系統(tǒng)隨時(shí)間的演化過(guò)程，它保證了量子態(tài)的總概率始終為 1。而“Harr 隨機(jī)”則意味著，這種演化過(guò)程是從所有可能的酉變換中完全均勻、無(wú)偏地隨機(jī)抽取的，好比在一個(gè)高維球面上完全隨機(jī)地選擇一個(gè)點(diǎn)。
這種完美的 Harr 隨機(jī)性是眾多理論研究的基石，涵蓋了量子算法設(shè)計(jì)、判定量子計(jì)算機(jī)是否超越經(jīng)典計(jì)算機(jī)的“量子霸權(quán)”實(shí)驗(yàn)、量子機(jī)器學(xué)習(xí)、各種量子密碼協(xié)議的設(shè)計(jì)，以及對(duì)極端物理現(xiàn)象（如黑洞內(nèi)部信息處理等高度混沌系統(tǒng)）的建模。物理學(xué)家們常常將黑洞看作是自然界的信息“攪拌器”，其動(dòng)力學(xué)行為就被認(rèn)為非常接近 Harr 隨機(jī)酉變換。
然而，理論上的完美往往伴隨著實(shí)踐中的巨大障礙。Harr 隨機(jī)酉矩陣存在一個(gè)根本性的問(wèn)題：它們?cè)诒举|(zhì)上是“非物理的”。要精確地描述一個(gè)作用于 n 個(gè)量子比特（qubit，量子信息的基本單元）系統(tǒng)的 Harr 隨機(jī)酉矩陣，需要大約 2^n 乘以 2^n 個(gè)參數(shù)來(lái)定義。這意味著，其復(fù)雜性隨著量子比特?cái)?shù)量的增加呈指數(shù)級(jí)爆炸式增長(zhǎng)。僅僅是“寫下”這樣一個(gè)矩陣的完整描述，就需要耗費(fèi)遠(yuǎn)超現(xiàn)有及可預(yù)見未來(lái)的經(jīng)典，或量子計(jì)算機(jī)能力的天文數(shù)字般的資源，更不用說(shuō)在實(shí)際的量子硬件上精確地實(shí)現(xiàn)它了。
這種指數(shù)級(jí)的復(fù)雜性使得 Harr 隨機(jī)酉矩陣在實(shí)際應(yīng)用中幾乎遙不可及。這自然引出了一個(gè)長(zhǎng)期困擾研究人員的關(guān)鍵問(wèn)題：我們能否找到一條“捷徑”？是否存在某種可以被高效構(gòu)建的量子電路，它本身并非真正的 Harr 隨機(jī)，但其行為效果對(duì)于任何實(shí)際可行的計(jì)算探測(cè)手段（即任何在多項(xiàng)式時(shí)間內(nèi)運(yùn)行的量子算法）來(lái)說(shuō)，都與真正的 Harr 隨機(jī)酉矩陣無(wú)法區(qū)分？
這正是 PRU 概念試圖解決的問(wèn)題。PRU 的核心思想與經(jīng)典計(jì)算機(jī)科學(xué)中的“偽隨機(jī)函數(shù)”（PRFs，Pseudorandom Functions）一脈相承。經(jīng)典 PRF 是由 Oded Goldreich 等人在 1986 年的奠基性工作中提出的。它指的是一類函數(shù)，可以由一個(gè)相對(duì)較短的密鑰（或稱為種子，seed）通過(guò)高效算法計(jì)算得出，但對(duì)于不知道這個(gè)密鑰的觀察者來(lái)說(shuō)，其輸出表現(xiàn)得就像一個(gè)完全隨機(jī)選擇的函數(shù)。
類似地，PRU 是一個(gè)由（相對(duì)）短的密鑰參數(shù)化的、可以被高效實(shí)現(xiàn)的量子電路家族。其核心安全保證是：對(duì)于任何計(jì)算能力受限于多項(xiàng)式時(shí)間的量子算法（通常被稱為“敵手”，Adversary），如果讓它與一個(gè)從 PRU 家族中隨機(jī)選擇密鑰生成的電路進(jìn)行交互，或者與一個(gè)真正的 Harr 隨機(jī)酉矩陣進(jìn)行交互，那么這個(gè)敵手無(wú)法以不可忽略的優(yōu)勢(shì)（即成功概率僅略高于隨機(jī)猜測(cè)）來(lái)區(qū)分這兩者。簡(jiǎn)單來(lái)說(shuō)，PRU 在效果上足夠“隨機(jī)”，同時(shí)在構(gòu)造上又足夠“簡(jiǎn)單”，使得它們有望在真實(shí)的量子計(jì)算機(jī)上被建造出來(lái)。
自 2017 年 PRU 概念被正式提出以來(lái)，其是否存在一直是量子信息領(lǐng)域的核心開放問(wèn)題之一。
在 Fermi Ma 和黃信元的工作之前，研究人員已經(jīng)取得了一些重要進(jìn)展，成功構(gòu)建了滿足較弱安全定義的偽隨機(jī)結(jié)構(gòu)。例如，一些工作構(gòu)造出了只能抵抗“非自適應(yīng)”（non-adaptive）敵手的 PRU（這類敵手必須一次性提交所有查詢請(qǐng)求，不能根據(jù)中間結(jié)果調(diào)整后續(xù)查詢）。然而，能否構(gòu)建能夠抵抗一般“自適應(yīng)”（adaptive）敵手（可以根據(jù)之前的查詢結(jié)果動(dòng)態(tài)調(diào)整后續(xù)查詢策略）的標(biāo)準(zhǔn) PRU，以及能否抵抗更強(qiáng)大的、可以同時(shí)查詢酉算子 U 及其逆算子 U? 的敵手，一直是橫亙?cè)谘芯咳藛T面前的一座大山。
路徑記錄與量子純化
而 Fermi Ma 和黃信元此次的研究成果一舉掃清了這些障礙。他們的工作不僅證明了標(biāo)準(zhǔn) PRU 的存在性，甚至更進(jìn)一步，證明了更為強(qiáng)大的“強(qiáng) PRU”的存在性。后者要求即使敵手擁有查詢酉算子 U 及其逆算子 U? 的雙重能力，也無(wú)法將 PRU 電路與真正的 Harr 隨機(jī)酉矩陣區(qū)分開來(lái)。而這兩種 PRU 的存在性證明都建立在同一個(gè)堅(jiān)實(shí)（盡管仍是假設(shè)）的基礎(chǔ)之上：存在量子安全的單向函數(shù)。
單向函數(shù)（One-way function）是現(xiàn)代密碼學(xué)的基石。它指的是一類函數(shù)，其正向計(jì)算（給定輸入計(jì)算輸出）非常容易，但其反向計(jì)算（給定輸出找到對(duì)應(yīng)的輸入）則極其困難，對(duì)于任何已知的算法（包括量子算法，對(duì)于量子安全單向函數(shù)而言）來(lái)說(shuō)，在多項(xiàng)式時(shí)間內(nèi)完成反向計(jì)算都是不可行的。這就像打碎一個(gè)花瓶，正向操作（打碎）很簡(jiǎn)單，但逆向操作（將碎片完美復(fù)原）幾乎不可能。密碼學(xué)中的許多安全構(gòu)造和證明都依賴于單向函數(shù)存在性的假設(shè)。研究團(tuán)隊(duì)的工作揭示了，只要這個(gè)被廣泛信任的密碼學(xué)基石在量子計(jì)算時(shí)代依然穩(wěn)固，那么高效模仿量子隨機(jī)性的 PRU 就必然存在。
他們?nèi)〉眠@一突破的核心在于一種新的模擬 Harr 隨機(jī)酉矩陣的方法，他們稱之為“路徑記錄諭示”（path-recording oracle）V。他們證明，任何與 Harr 隨機(jī)酉矩陣交互的量子算法的行為，都可以被一個(gè)在量子計(jì)算機(jī)上高效運(yùn)行的模擬過(guò)程所精確復(fù)制。
這個(gè)模擬過(guò)程的核心，是追蹤并記錄下算法與酉矩陣交互的“路徑”或歷史信息。具體而言，路徑記錄諭示 V 作用于算法當(dāng)前的查詢量子態(tài)|x?A 以及一個(gè)存儲(chǔ)交互歷史的輔助量子寄存器|R?R。R 代表一個(gè)關(guān)系的集合，例如包含了過(guò)去的輸入輸出對(duì) {(x1, y1), ..., (xt, yt)}。
V 算符將輸入態(tài) |x?A |R?R 映射到一個(gè)新的量子態(tài)。在這個(gè)新態(tài)中，A 寄存器處于所有可能的輸出 y 的均勻疊加態(tài)上，但這些 y 必須是“新”的，即不能等于 R 中任何已有配對(duì)的輸出（y ? Im(R)，以保持映射的單射性）。同時(shí)，R 寄存器則更新為包含了新輸入輸出對(duì) (x, y) 的狀態(tài) |R ∪ {(x, y)}?R。形式上可以寫作：V: |x?A |R?R ? (1/√Zx,R) Σy∈[N], y?Im(R) |y?A |R ∪ {(x, y)}?R，其中 Zx,R 是確保歸一化的因子。
研究的關(guān)鍵成果在于證明了這個(gè) V 操作不僅可以被量子計(jì)算機(jī)高效執(zhí)行，而且它所模擬的 Harr 隨機(jī)酉矩陣與真實(shí)的 Harr 隨機(jī)酉矩陣之間，對(duì)于任何進(jìn)行了 t 次查詢的高效算法所產(chǎn)生的最終狀態(tài)，其跡距離（trace distance）差異極小，僅為 O(t2/2?)（n 為量子比特?cái)?shù)）。這意味著對(duì)于多項(xiàng)式次數(shù)的查詢 t，這種模擬在統(tǒng)計(jì)意義上是極其精確的。路徑記錄框架因此提供了一種全新的、更為簡(jiǎn)潔的分析 Harr 隨機(jī)性的有力工具，成功繞開了傳統(tǒng)研究中對(duì)復(fù)雜的魏因加滕微積分（Weingarten calculus）及其漸近界估計(jì)的依賴。
基于這一模擬工具，研究者進(jìn)一步將 PRU 的存在性與密碼學(xué)的基礎(chǔ)假設(shè)量子安全單向函數(shù)的存在性聯(lián)系起來(lái)。他們采用了一種被稱為 PFC 構(gòu)造的方法來(lái)構(gòu)建標(biāo)準(zhǔn) PRU。最終輸出的酉算子形式為 O = Pπ · Ff · C。這里的 Pπ是由均勻隨機(jī)選取的置換（Permutation）π決定的置換算子；Ff 是一個(gè)對(duì)角算子，其相位由均勻隨機(jī)選取的布爾函數(shù) f 決定；而 C 則是一個(gè)從任意酉 2-設(shè)計(jì)（unitary 2-design）分布 D 中隨機(jī)抽取的酉矩陣，常見的例子包括克利福德群（Clifford group）電路或 Harr 隨機(jī)本身。
證明的核心邏輯結(jié)合了純化（Purification）技巧和路徑記錄框架。通過(guò)引入純化寄存器來(lái)表示隨機(jī)的π和 f，對(duì)隨機(jī) PFC 算子的查詢被轉(zhuǎn)化為對(duì)一個(gè)固定的“純化”諭示 pfO 的查詢。然后，研究者建立了 pfO 與路徑記錄諭示 V 之間的緊密聯(lián)系，證明了在一個(gè)部分等距同構(gòu)算子 Comp 的作用下，兩者在特定子空間上的行為近似等價(jià)。
最后，酉 2-設(shè)計(jì) C 通過(guò)纏繞（twirling）效應(yīng)有效地隨機(jī)化輸入，極大地抑制了算法查詢過(guò)程中輸入發(fā)生碰撞的概率。當(dāng)輸入無(wú)碰撞時(shí)，pfO 的行為與 V 高度一致。結(jié)合 V 與 Harr 隨機(jī)的高度不可區(qū)分性，最終證明了 PFC 構(gòu)造（在 OWF 假設(shè)保證了偽隨機(jī)置換和函數(shù)存在的前提下）確實(shí)產(chǎn)生了標(biāo)準(zhǔn) PRU。
強(qiáng) PRU 的構(gòu)建與模擬
研究團(tuán)隊(duì)還進(jìn)一步探索了如何構(gòu)建安全性要求更高的“強(qiáng) PRU”。標(biāo)準(zhǔn) PRU 的安全性定義是針對(duì)那些只能進(jìn)行“前向”查詢（即只能調(diào)用酉算子 U）的敵手。而強(qiáng) PRU 則要求即使敵手被賦予了更強(qiáng)大的能力——可以同時(shí)進(jìn)行前向查詢（調(diào)用 U）和“反向”查詢（調(diào)用 U 的逆算子 U?）——也無(wú)法將 PRU 電路與真正的 Harr 隨機(jī)酉矩陣區(qū)分開來(lái)。
為了構(gòu)建強(qiáng) PRU，他們采用了一個(gè)稍微修改的構(gòu)造：D · Pπ · Ff · C。這里，C 和 D 都是從 n-qubit 克利福德群（或任何 2-設(shè)計(jì)）中獨(dú)立隨機(jī)抽取的酉算子，Pπ 仍然是隨機(jī)置換，而 Ff 這次被選為一個(gè)隨機(jī)的三值相位函數(shù)（即 f(x) 可以取 0, 1, 2 中的隨機(jī)值，對(duì)應(yīng)于乘以相位因子 ω = exp(2πi/3) 的不同冪次）。引入兩個(gè)隨機(jī)酉算子 C 和 D 以及使用三值相位是為了應(yīng)對(duì)反向查詢帶來(lái)的額外挑戰(zhàn)。
對(duì)這個(gè)新構(gòu)造的純化版本進(jìn)行分析時(shí)，他們發(fā)現(xiàn)情況變得更為復(fù)雜和有趣。當(dāng)敵手可以進(jìn)行前向和反向查詢時(shí)，純化寄存器不再是簡(jiǎn)單地記錄一個(gè)包含所有 (x, y) 對(duì)的集合 S。取而代之的是，它似乎同時(shí)維護(hù)著兩個(gè)獨(dú)立的記錄集合：一個(gè) S^for，大致對(duì)應(yīng)于前向查詢所建立的路徑信息；另一個(gè) S^inv，大致對(duì)應(yīng)于反向查詢所建立的路徑信息。更復(fù)雜的是，兩者之間存在互動(dòng)：一次前向查詢有時(shí)會(huì)像之前一樣向 S^for 中添加一個(gè)元組 (x, y)，但有時(shí)卻可能需要從 S^inv 中刪除一個(gè)元組。反向查詢同樣會(huì)對(duì) S^inv 和 S^for 產(chǎn)生類似的、可能涉及增刪的復(fù)雜操作。
他們通過(guò)推導(dǎo)證明了，這種看似混亂的復(fù)雜行為實(shí)際上精確地對(duì)應(yīng)于一個(gè)更廣義、更對(duì)稱化的“路徑記錄諭示”? 的行為。同樣地，他們證明了只要 C 和 D 是從 2-設(shè)計(jì)中隨機(jī)抽取的，那么敵手就無(wú)法區(qū)分對(duì)構(gòu)造 D · Pπ · Ff · C 的查詢和對(duì)這個(gè)新的路徑記錄預(yù)言機(jī) ? 的查詢。最后，結(jié)合 ? 的行為與真正的 Harr 隨機(jī)酉矩陣（即使在允許反向查詢的設(shè)置下）的不可區(qū)分性，他們成功地證明了強(qiáng) PRU 的存在性。這個(gè)證明過(guò)程比標(biāo)準(zhǔn) PRU 的證明更為錯(cuò)綜復(fù)雜，巧妙地利用了 2-設(shè)計(jì)酉算子在作用于兩個(gè)量子系統(tǒng)（通過(guò)張量積 C ? C*，其中 C* 是 C 的復(fù)共軛）時(shí)展現(xiàn)出的一些特殊平均性質(zhì)。
這項(xiàng)研究對(duì)于量子信息領(lǐng)域而言意義重大，除了為通用 PRU 和 sPRU 的存在性提供了嚴(yán)格的數(shù)學(xué)證明之外，研究提出的“路徑記錄”框架本身也是一個(gè)強(qiáng)大的新理論工具，有望簡(jiǎn)化對(duì)隨機(jī)酉變換性質(zhì)的分析。
在實(shí)際應(yīng)用層面，PRU 的存在意味著未來(lái)可以設(shè)計(jì)出更高效的量子算法和實(shí)驗(yàn)方案。例如，演示量子優(yōu)勢(shì)的實(shí)驗(yàn)可以利用 PRU 來(lái)替代難以實(shí)現(xiàn)的 Harr 隨機(jī)電路，從而降低成本、擴(kuò)大規(guī)模。黃信元指出：“這些構(gòu)造對(duì)整個(gè)量子技術(shù)非常重要……我們能用更高效的資源來(lái)做這些量子優(yōu)勢(shì)實(shí)驗(yàn)?！?/p>
當(dāng)然，這一切都建立在量子安全單向函數(shù)存在的假設(shè)之上。盡管這是主流假設(shè)，但其最終的可靠性仍有待數(shù)學(xué)證明。盡管如此，這項(xiàng)成果無(wú)疑極大地推動(dòng)了我們對(duì)量子隨機(jī)性的理解和操控能力。隨著量子計(jì)算技術(shù)的發(fā)展，高效利用和模擬量子隨機(jī)性的能力將日益重要，而這項(xiàng)工作恰逢其時(shí)地提供了一把關(guān)鍵的鑰匙。獲取和利用量子隨機(jī)性的高昂成本，將因此而開始“下降”。
參考資料：
1.https://arxiv.org/abs/2410.10116
2.https://www.quantamagazine.org/the-high-cost-of-quantum-randomness-is-dropping-20250328/
運(yùn)營(yíng)/排版：何晨龍
熱門跟貼