在量子科學領域，一項長期懸而未決的難題似乎已被兩位杰出的華人科學家攻克。去年十月，Fermi Ma與黃信元共同發布了一篇革命性的論文，揭示了偽造量子隨機性的全新途徑。
量子隨機性在諸多領域具有不可估量的價值。它不僅能夠顯著提升算法效率，優化復雜系統模擬，還能驗證量子計算的準確性。在密碼學領域，量子隨機性是生成真正隨機密鑰的關鍵，對于保障信息安全至關重要。然而，實現這種隨機性的成本高昂，促使科學家們不懈探索偽造隨機性的方法。
Ma與黃信元的論文提出了一種前所未有的新方法，據《量子雜志》報道，該方法既優雅又安全，且無需高昂的計算成本。MIT量子計算研究員Alexander Poremba對此贊譽有加，稱這是首次有確鑿證據證明偽隨機性是一個真實存在的概念。
兩位科學家在76頁的論文中（核心證明僅10頁），基于量子安全單向函數的存在假設，成功證明了偽隨機幺正態（PRUs）的存在。要理解這一成果，首先需要了解隨機幺正的概念。隨機幺正在量子計算中至關重要，是量子霸權實驗、量子算法和各種加密原語設計的基礎。然而，實現隨機幺正變換需要巨大的時間和計算資源，因此實際操作極為困難。PRUs的出現為解決這一問題提供了可能。
2017年，一篇論文首次引入了PRUs的概念，并試圖通過一種結構上可控的方法來模擬Haar隨機酉矩陣。然而，該方法未能完全證明其構造的PRUs與真正的Haar隨機酉矩陣等效。在此基礎上，Ma與黃信元首次證明了PRUs的存在。
他們的證明過程巧妙運用了量子信息理論中的“凈化”技術，并提出了一種名為“路徑記錄模擬”的新方法。通過記錄酉算子在運算過程中的關鍵信息，他們得以分析酉算子的特點，為后續證明提供了有力支持。借助單向函數這一特殊工具，他們發現了一種之前被認為是“弱偽隨機”的構造，實際上具有“真偽隨機”的特性，能夠在保持簡單結構的同時偽裝成Haar隨機酉矩陣。
兩位科學家還證明了一種高效的模擬方法，該方法對于研究Haar隨機酉矩陣的量子算法具有極小的模擬誤差。這一證明過程涉及對量子算法執行過程的深入研究，以及巧妙利用“路徑記錄模擬”記錄的信息來設計模擬過程。最終，他們通過靈活運用膠合引理，完整地證明了偽隨機幺正態的存在。
關于論文的作者，Fermi Ma目前擔任西蒙斯-伯克利博士后研究員，于2021年獲得普林斯頓大學博士學位，專注于量子計算及其對密碼學、復雜性理論和物理學的影響。黃信元則是谷歌量子人工智能的高級研究科學家，這項工作是在他訪問西蒙斯計算理論研究所期間完成的。今年，他即將加入加州理工學院擔任理論物理學助理教授。
