快1.8億倍！九章光量子計算原型機成功求解圖論問題_最新消息

(相關資料圖)

8日，記者從中國科學技術大學獲悉，該校由潘建偉、陸朝陽、劉乃樂等組成的研究團隊，基于“九章”光量子計算原型機完成了對“稠密子圖”和“Max-Haf”兩類圖論問題的求解，通過實驗和理論研究了“九章”處理這兩類圖論問題為搜索算法帶來的加速，以及該加速對于問題規(guī)模和實驗噪聲的依賴關系。該研究成果系首次在具有量子計算優(yōu)越性的光量子計算原型機上開展的面向具有應用價值問題的實驗研究。相關論文日前以“編輯推薦”的形式發(fā)表在國際學術期刊《物理評論快報》上，并被物理網(wǎng)站專題報道。

國際學術界對量子計算的實驗發(fā)展制定了三步走的路線圖，其中第一步是實現(xiàn)“量子計算優(yōu)越性”，即通過高精度地操縱近百個物理比特，高效求解超級計算機無法在合理時間內解決的特定的高復雜度數(shù)學問題。這一步的意義在于首次從實驗上確鑿地證明量子計算加速，并挑戰(zhàn)“擴展的丘奇—圖靈論題”。因此，國際學術界下一階段的一個重要科研目標是探索利用量子計算原型機演示具有實用價值的問題的求解。

近期，潘建偉團隊在繼續(xù)發(fā)展更高質量和更強拓展性的光量子計算原型機的同時，開展了將“九章”所執(zhí)行的高斯玻色采樣任務應用于圖論問題的研究探索。圖論起源于著名的“哥尼斯堡七橋問題”，被廣泛用于描述事物之間的關系，例如社交網(wǎng)絡、分子結構和計算機科學中的許多問題均可對應到圖論問題。高斯玻色采樣與圖論問題具有緊密的數(shù)學聯(lián)系，通過將高斯玻色采樣設備的每個輸出端口映射到圖的頂點，將每個探測到的光子映射到子圖的頂點，研究人員可以利用實驗得到的樣本加速搜索算法尋找具有更大密度或Hafnian的子圖的過程，從而幫助這兩類圖論問題的求解。這兩類圖論問題在數(shù)據(jù)挖掘、生物信息、網(wǎng)絡分析和某些化學模型研究等領域具有重要應用。

此次研究中，研究人員首次利用“九章”執(zhí)行的高斯玻色采樣來加速隨機搜索算法和模擬退火算法對圖論問題的求解。研究人員在實驗中使用了超過20萬個80光子符合計數(shù)樣本，相比全球最快超級計算機使用當前最優(yōu)經(jīng)典算法精確模擬該實驗的速度快約1.8億倍。

(中國科大供圖)

關鍵詞：