中國科學(xué)技術(shù)大學(xué)潘建偉、陸朝陽(yáng)、劉乃樂(lè )等組成的研究團隊基于“九章”光量子計算原型機完成了對“稠密子圖”和“Max-Haf”兩類(lèi)圖論問(wèn)題的求解，通過(guò)實(shí)驗和理論研究了“九章”處理這兩類(lèi)圖論問(wèn)題為搜索算法帶來(lái)的加速，及該加速對于問(wèn)題規模和實(shí)驗噪聲的依賴(lài)關(guān)系。該研究成果系首次在具有量子計算優(yōu)越性的光量子計算原型機上開(kāi)展的面向具有應用價(jià)值問(wèn)題的實(shí)驗研究。相關(guān)論文近日以“編輯推薦”的形式發(fā)表在國際知名學(xué)術(shù)期刊《物理評論快報》上，并被Physics網(wǎng)站專(zhuān)題報道。
圖片1：“九章”量子計算原型機與圖論問(wèn)題對應關(guān)系原理示意圖
量子計算機的物理實(shí)現是當前科技前沿的重大挑戰之一。國際學(xué)術(shù)界對量子計算的實(shí)驗發(fā)展制定了三步走的路線(xiàn)圖，其中第一步是實(shí)現“量子計算優(yōu)越性”。“量子計算優(yōu)越性”是指，通過(guò)高精度地操縱近百個(gè)物理比特，高效求解超級計算機無(wú)法在合理時(shí)間內解決的特定的高復雜度數學(xué)問(wèn)題。這一步的意義在于首次從實(shí)驗上確鑿地證明量子計算加速，并挑戰“擴展的丘奇—圖靈論題”。
2019年底，美國谷歌公司利用超導量子比特宣布實(shí)現“量子計算優(yōu)越性”，但隨之經(jīng)典模擬算法取得快速發(fā)展，谷歌的這一宣稱(chēng)受到挑戰。2020年，中國科大潘建偉團隊成功構建了76個(gè)光子100個(gè)模式的高斯玻色取樣量子計算原型機“九章”，首次達到基于光子的“量子計算優(yōu)越性”里程碑。2021年，潘建偉團隊進(jìn)一步成功研制了 “祖沖之二號”和“九章二號”，使得我國成為唯一在兩種技術(shù)路線(xiàn)都達到了“量子計算優(yōu)越性”的國家。
目前，僅有谷歌、中國科大以及加拿大Xanadu三個(gè)團隊實(shí)現了“量子計算優(yōu)越性”的目標。而只有在實(shí)現“量子計算優(yōu)越性”的基礎上，量子計算應用的實(shí)驗研究才有望帶來(lái)量子加速。因此，國際學(xué)術(shù)界下一階段的一個(gè)重要科研目標是探索利用量子計算原型機演示具有實(shí)用價(jià)值的問(wèn)題的求解。
近期，潘建偉團隊在繼續發(fā)展更高質(zhì)量和更強拓展性的光量子計算原型機的同時(shí)，開(kāi)展了將“九章”所執行的高斯玻色采樣任務(wù)應用于圖論問(wèn)題的研究探索。圖論起源于著(zhù)名的“哥尼斯堡七橋問(wèn)題”，被廣泛用于描述事物之間的關(guān)系，例如社交網(wǎng)絡(luò )、分子結構和計算機科學(xué)中的許多問(wèn)題均可對應到圖論問(wèn)題。高斯玻色采樣與圖論問(wèn)題具有緊密的數學(xué)聯(lián)系，通過(guò)將高斯玻色采樣設備的每個(gè)輸出端口映射到圖的頂點(diǎn)，將每個(gè)探測到的光子映射到子圖的頂點(diǎn)，研究人員可以利用實(shí)驗得到的樣本加速搜索算法尋找具有更大密度或Hafnian的子圖的過(guò)程，從而幫助這兩類(lèi)圖論問(wèn)題的求解。這兩類(lèi)圖論問(wèn)題在數據挖掘、生物信息、網(wǎng)絡(luò )分析和某些化學(xué)模型研究等領(lǐng)域具有重要應用。該工作中，研究人員首次利用“九章”執行的高斯玻色采樣來(lái)加速隨機搜索算法和模擬退火算法對圖論問(wèn)題的求解。研究人員在實(shí)驗中使用了超過(guò)20萬(wàn)個(gè)80光子符合計數樣本，相比全球最快超級計算機使用當前最優(yōu)經(jīng)典算法精確模擬該實(shí)驗的速率快約1.8億倍。
該論文第一作者是博士研究生鄧宇皓、龔思秋、顧義超。上述項目受到了安徽省、科技部、中科院、上海市和基金委的支持。
論文鏈接：https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.190601
Physics網(wǎng)站報道：https://physics.aps.org/articles/v16/s64
（合肥微尺度物質(zhì)科學(xué)國家研究中心、物理學(xué)院、中科院量子信息與量子科技創(chuàng )新研究院、科研部）
