IBM全新量子算法將加速隨機數生成
責編：gltian ｜2023-07-14 14:34:09生成隨機數看似容易，但其難度卻出乎意料——尤其是在隨機數的概率分布非常復雜的情況下。
在科學研究中（例如在訓練神經網絡時），經常會遇到這種情況。在這種情況下，研究人員可以使用一種通用計算最早使用的技術：Metropolis算法。該算法于1953年首次在開創性的MANIAC計算機上運行，而它的現代版名稱則是馬爾科夫鏈蒙特卡羅（MCMC）算法。
7月12日，來自IBM Quantum的科學家Layden等人在《自然》雜志上撰文，通過使用量子計算機來加速程序的性能，報告了這一算法發展中更為現代的轉折。
“Quantum-enhanced Markov chain Monte Carlo”
MCMC算法是一種根據指定概率分布生成隨機數的框架，這項任務被稱為采樣。該框架包含多種變體，所有變體都涉及樣本的迭代；經過足夠多的循環后，需要保證樣本的分布符合所需的目標分布。
這一過程中的每次迭代都包含兩個部分：
– 建議步驟，即在當前樣本的基礎上建議一個樣本；
– 接受或拒絕步驟，即接受新樣本作為迭代中的下一個樣本，或拒絕新樣本以重復上述過程。
馬爾科夫鏈蒙特卡羅（MCMC）算法從目標概率分布中抽取隨機數，涉及的兩個步驟：提出一個樣本，然后接受該樣本作為迭代中的下一個樣本；或者拒絕該樣本，從而觸發該過程重新開始。這兩個步驟的設計都必須保證足夠的迭代次數，以便最終得到符合目標分布的樣本，實現這一目標所需的迭代次數稱為收斂時間(convergence time)。具體來說，樣本收斂到目標分布的迭代次數比使用傳統MCMC算法的迭代次數更少。
MCMC 算法的變體可通過每個步驟所使用的不同策略來區分。最重要的是，這兩個步驟必須以這樣一種方式構建，即保證重復這兩個步驟最終得到的樣本分布符合所需的分布。因此，“需要多長時間”是任何MCMC變體的關鍵屬性。
在樣本按照目標分布分布之前，這個過程需要重復1000次嗎？還是一百萬次？
所需的迭代次數稱為收斂時間，它取決于隨機變量的維度——描述采樣變量所需的比特數。維數越大，收斂時間越長。不幸的是，對于目前使用的大多數 MCMC 變體而言，收斂時間與變量維度的確切數學關系并不嚴格。然而，這并沒有阻止人們使用MCMC算法：他們傾向于利用收斂的經驗和統計特征。
Layden等人設計了一種MCMC變體：利用量子計算機在提議步驟中產生樣本。在任何迭代中，隨機樣本都被編碼為量子態，并對其進行一系列量子運算以產生輸出態，該輸出態可被測量以生成新樣本。這本身并不特別：在MCMC算法的提議步驟中，幾乎任何程序都可以用來生成新樣本（包括簡單地對當前樣本施加噪聲）。
然而，此次的研究人員必須能夠證明這些步驟收斂到了目標分布，而這對于任意的提議程序來說是不可能的。這就引出了Layden及其同事的關鍵創新：他們設計了一套量子操作，當量子提議步驟與標準的接受或拒絕步驟相結合時，就可以驗證收斂性。
作者通過數值模擬和早期量子計算硬件實驗相結合的方式，展示了他們的量子增強MCMC算法。他們的研究結果表明了迭代對目標分布的預測收斂性。更重要的是，他們還證明了該收斂速度快于之前為提議步驟設計的幾種經典替代方案。
實際的收斂速度很難測量，作者僅對有限復雜度的過程進行了測量——那些目標變量分布最多可由10比特描述的過程；他們還對20比特變量目標分布的收斂率進行了近似計算。
在所有情況下，他們都發現了令人信服的證據，證明量子版MCMC算法的收斂速度比經典版更快。他們根據經驗確定，這種速度提升是多項式的，量子增強策略的收斂時間約為傳統策略收斂時間的立方根。
這種速度提升從何而來？與大多數量子增強一樣，很難將其歸因于量子系統的任何一個特征。Layden等人提供的數字證據表明，他們所選擇的量子操作在生成多樣化提案與滿足目標概率分布所施加的約束之間取得了微妙的平衡：這是經典提案策略難以實現的權衡。
平均收斂速率模擬。
收斂率實驗。
量子加速機制。
盡管Layden及其同事的工作很全面，但也存在一些局限性。
首先，量子增強算法的收斂性證明只有在量子操作完美執行的情況下才是有效的：在硬件不產生任何噪聲的情況下。然而，他們的實驗結果表明，收斂率對噪聲具有一定的穩健性，尤其是當硬件噪聲可以隨機化時。
其次，加速收斂僅在小規模問題中觀察到，在更大規模問題中可能會消失，特別是在存在噪聲的情況下。如果作者對加速原因的解釋是正確的，并且如果硬件噪聲可以在更大尺度上被抑制，加速很可能會持續下去——但這在現階段還遠遠不能確定。
最后，盡管Layden等人已經證明他們的量子增強算法比一些常見的經典提議策略收斂更快，但他們還沒有測試更多MCMC變體。因此，這一差距有可能被現有的或可能設計出的其他經典提議策略彌補，甚至有可能是受到這項工作的啟發。
盡管存在這些局限性，Layden及其同事的研究為早期含噪聲量子計算機生成有用的解決方案提供了一個重要而令人興奮的應用，同時也為富有成果的未來研究確定了許多方向。
參考鏈接：
[1]https://www.nature.com/articles/s41586-023-06095-4
[2]https://www.nature.com/articles/d41586-023-02176-6
來源：光子盒