光子盒子研究所出品
解決獨(dú)立集 (IS) 問題或其他組合優(yōu)化問題在經(jīng)濟(jì)學(xué)、生物學(xué)、芯片設(shè)計和計算機(jī)視覺等不同領(lǐng)域有著廣泛的應(yīng)用。
對于線圖、平面圖和樹狀圖等典型結(jié)構(gòu)，找到它們的所有獨(dú)立集是一個形式上復(fù)雜的問題，可以用經(jīng)典算法解決； 然而，對于一般圖來說，找到它們所有的最大 IS 早已被證明是一個 NP- (NP-) 問題。
然而，啟發(fā)式算法可用于找到近似的最大 IS。 此時，絕熱量子估計提供了一種解決 IS 等價問題的自然方法，但由于其比經(jīng)典算法更快的潛力而引起了強(qiáng)烈的興趣。 在絕熱量子估計中，首先將量子系統(tǒng)設(shè)想為簡單的初始能級?0，然后逐漸轉(zhuǎn)化為?的復(fù)雜目標(biāo)。 量子絕熱定律保證，如果艾頓的變化足夠慢，系統(tǒng)最終將達(dá)到 ? 的能級。
然而，瞬態(tài)多體伊寧頓的能級與第一爆發(fā)態(tài)之間的最小能隙Δmin通常隨系統(tǒng)規(guī)模呈指數(shù)增長，這意味著絕熱過程所需的運(yùn)行時間T將呈指數(shù)增長向下. 因此，雖然 ?0 和 ? 之間的絕熱演化的基本概念簡單而通用，但選擇合適的初始伊寧頓?0 和易于實(shí)現(xiàn)的演化路徑來解決特定的組合優(yōu)化問題可能是數(shù)學(xué)上具有挑戰(zhàn)性的任務(wù)。
幸運(yùn)的是，對于 IS 等價問題，對應(yīng)的多體系統(tǒng)具有相當(dāng)大的非阿貝爾規(guī)范對稱性——我們可以利用這一性質(zhì)。 它允許我們選擇 ?IS 作為初始和目標(biāo) 。 通過驅(qū)動系統(tǒng)沿著閉合路徑平緩演化，將一個容易預(yù)測的初始能級轉(zhuǎn)化為包含?IS的估計基礎(chǔ)能級（即對應(yīng)的獨(dú)立集）的疊加，從而得到IS問題的解。 這個過程可以看做中圖中的“量子擴(kuò)散（）”，命名為非阿貝爾絕熱混合（non-，NAAM）。
文章以“Using to Solve Set ”為題發(fā)表在PNAS上。
在5月22日發(fā)表于美國國立科技大學(xué)（PNAS）學(xué)報的文章中，潘建偉、陳玉傲、姚興燦等團(tuán)隊聯(lián)合報道了NAAM的原理證明，利用先進(jìn)的線性光量子網(wǎng)絡(luò)(LOQN ) 解決了通常圖 G(8,7) 上的 IS 問題。
由于 G(8,7) 有 7 個邊量子物理學(xué)名詞，至少需要 7 個概率雙位 C 相門來逼近 NAAM，導(dǎo)致在 LOQN 中成功的概率非常低（約為 ～10-7）。 為了克服這一障礙，該團(tuán)隊開發(fā)了一種結(jié)合路徑極化超糾纏的方法，以實(shí)現(xiàn)確定性雙量子位門陣列 (DGA)。 通過在 LOQN 的末層放置四個 DGA，整體成功率提高了四個數(shù)量級。
從圖表到概念電路。
(A) 代表圖 G(8,7) 沒有斷點(diǎn)。 (B) 8 維圖中“量子擴(kuò)散”過程的圖示。 白點(diǎn)和紅點(diǎn)代表真實(shí)狀態(tài)，即H的估計基態(tài)|gn?，而藍(lán)點(diǎn)和空心點(diǎn)代表假狀態(tài)，即不屬于|gn?的估計基態(tài)。 兩點(diǎn)之間的虛線和實(shí)線分別代表“量子擴(kuò)散”過程中的允許路徑和禁止路徑。 最后一張圖中虛線連接的黑點(diǎn)和藍(lán)點(diǎn)構(gòu)成了IS問題G(8,7)的中值圖。 (C) 實(shí)現(xiàn)-Zee 完整性ΓG(8,7) 和步驟 m 的示意圖。 每個預(yù)制組件對應(yīng)一個8量子比特的全連接線性光量子網(wǎng)絡(luò)。 黑色層代表伊寧頓數(shù)量?13+?57； 淺黃色層對應(yīng)?37； 深灰色層用于實(shí)現(xiàn)?12+?34+?56+?78。
實(shí)現(xiàn)概念電路的確定性門陣列 (DGA)。
(A) DGA 的量子電路。 上（下）量子比特是單個光子的偏振光（空間）模式； Ub 和 Ur 代表 SU(2) 旋轉(zhuǎn)門，由夾在兩個 QWP 之間的 HWP 實(shí)現(xiàn)。 (B) 實(shí)驗(yàn)裝置。 輸入 PBS 和輸出 PBS 結(jié)合紅色和藍(lán)色路徑上的 Ub 和 Ur 門，構(gòu)建 DGA，將輸入偏振光狀態(tài)轉(zhuǎn)換為偏振光空間糾纏態(tài)。 ( ) 干涉儀確保臂之間的相位穩(wěn)定。 (C) 實(shí)驗(yàn)過程矩陣 χex 的實(shí)部和虛部。 高保真 DGA 的實(shí)現(xiàn)大大提高了我們淺層電路的成功概率，為高精度解決 IS 問題 G(8,7) 鋪平了道路。
化學(xué)實(shí)驗(yàn)的實(shí)施。
兩個脈沖紫外 (UV) 激光器（390 nm 波長、140 fs 脈沖持續(xù)時間、76 MHz 重復(fù)頻率、300 mW 泵浦功率）通過 type-ii@SPDC 工藝同時形成兩個相關(guān)的光子對 1 AMP2 和 3AMP4。 之后，四個光子被注入一個淺電路，該電路由十個單位旋轉(zhuǎn)門、三個 C 相門和四個 DGA 組成。 八個測量模塊放置在淺層電路的輸出端口。 最后，光子由 16 個光纖耦合單光子探測器（量子效率 > 60%）測量，所有 256 個八重符合波由基于 FPGA 的符合計數(shù)系統(tǒng)記錄。
DGA有6個獨(dú)立可調(diào)參數(shù)，相當(dāng)于一個C-gate夾著兩個C-NOT門，從而大大提高了量子電路的深度量子物理學(xué)名詞，形成了0.930的高工藝保真度。 據(jù)報道，通過在σz的基礎(chǔ)上檢測最終的疊加態(tài)，成功識別了包括五個最大獨(dú)立集（ ）、（ ）、（ ）、（ ）和（ ）在內(nèi)的所有解。
實(shí)驗(yàn)結(jié)果
“我們的工作開辟了通過在未來的大規(guī)?？删幊?LOQN 上執(zhí)行 NAAM 來解決更復(fù)雜的 IS 等效問題的前景，”該團(tuán)隊說。
本實(shí)驗(yàn)實(shí)現(xiàn)了一個非阿貝爾絕熱混合過程來解決基于高級 LOQN 的一般 IS 問題 G(8,7)。 由于 LOQN 的高度靈活性和復(fù)雜性，該團(tuán)隊在非阿貝爾絕熱混合過程中實(shí)現(xiàn)了 0.930 的相當(dāng)高的保真度。 這又成功地解決了 IS 問題：在獲得最大獨(dú)立集時，成功找到解的概率為 0.875，找到非線性解的概率為 31.4%。
同時，論文中也提到，“我們目前的實(shí)驗(yàn)主要有兩個局限性：i）找到最大獨(dú)立集的概率較小；ii）求解更大的IS問題G(V, E) 然而，我們的工作表明，NAAM 可以用作解決具有固有非阿貝爾正則對稱性的 IS 等效組合優(yōu)化問題的一種有效且通用的方法。”
未來基于NAAM的算法潛在量子加速的探索和大規(guī)模量子模擬器的不斷改進(jìn)可以帶來近期的實(shí)際應(yīng)用，例如里德伯原子陣列中MIS問題的量子優(yōu)化、超導(dǎo)處理器的量子近似優(yōu)化問題，以及使用 qudit 系統(tǒng)等的非阿貝爾模型理論的量子模擬。
原文鏈接：