谷歌量子AI的最新理論研究表明，大規(guī)模量子計算機能夠解決傳統(tǒng)經(jīng)典計算機無法處理的某些優(yōu)化問題。

從設(shè)計更高效的航線到組織臨床試驗，優(yōu)化問題無處不在。然而對于許多現(xiàn)實世界的挑戰(zhàn)，即使是最強大的超級計算機也難以找到最佳解決方案。這引發(fā)了量子計算領(lǐng)域一個持續(xù)數(shù)十年的重要問題：量子機器能否在經(jīng)典計算機失敗的優(yōu)化問題上取得成功？這一直是一個極其困難的數(shù)學(xué)問題，在很大程度上仍未解決。隨著量子硬件能力的快速發(fā)展，研究大規(guī)模容錯量子計算機最終商業(yè)和科學(xué)用例的理論問題變得越來越緊迫。

在最近發(fā)表的《自然》論文中，來自谷歌量子AI以及斯坦福大學(xué)、麻省理工學(xué)院和加州理工學(xué)院的合作研究人員為這個問題帶來了新的見解。我們介紹了一種高效的量子算法——稱為解碼量子干涉（DQI）——該算法利用量子力學(xué)的波動特性創(chuàng)建干涉模式，收斂到使用經(jīng)典計算機極難找到的近最優(yōu)解。

不過，這里有一個問題。要構(gòu)建必要的干涉模式，必須解決另一個稱為解碼的困難計算問題。在解碼問題中，給定一個格子和空間中的一個點，需要找到最接近該點的格子元素。例如，棋盤上方格的角點形成一個二維格子。在棋盤上隨機位置撒下一粒沙子后，解碼問題就是找到最近的角點。雖然這個問題在二維方形格子中很容易解決，但在數(shù)百或數(shù)千維的某些格子中可能變得非常困難。

幸運的是，在過去幾十年中，解碼問題得到了極其深入的研究，主要是由于在糾正數(shù)據(jù)存儲或傳輸過程中產(chǎn)生的錯誤方面的應(yīng)用。人們已經(jīng)設(shè)計出許多復(fù)雜而強大的算法來解決各種特殊結(jié)構(gòu)格子的解碼問題。我們發(fā)現(xiàn)，對于某些類型的優(yōu)化問題，相關(guān)的解碼問題具有適合用這些強大解碼算法解決的結(jié)構(gòu)類型。然而，只有通過量子計算的力量，這些解碼算法才能被利用來解決優(yōu)化問題。通過將DQI的量子干涉與這些復(fù)雜的解碼算法相結(jié)合，足夠大的量子計算機可以找到這些優(yōu)化問題的近似解——這些解似乎超出了任何已知經(jīng)典方法的范圍。

這一為優(yōu)化提供加速的量子算法的數(shù)學(xué)發(fā)現(xiàn)提高了我們對量子計算機最終用例的理解。當(dāng)量子計算硬件足夠先進時，研究人員可以使用DQI算法來解決具有經(jīng)典挑戰(zhàn)性的優(yōu)化問題。

在這項工作中，我們的最佳結(jié)果是針對一個稱為最優(yōu)多項式交集（OPI）的問題。在OPI問題中，給定一個目標(biāo)點列表，希望通過調(diào)整次數(shù)低于點數(shù)的多項式系數(shù)來交集盡可能多的點。這是數(shù)據(jù)科學(xué)中稱為多項式回歸的常見任務(wù)。這個問題的變體在數(shù)字糾錯和密碼學(xué)背景下都有出現(xiàn)。因此，人們已經(jīng)開發(fā)出復(fù)雜的算法來在某些特殊情況下解決它，但對于其他情況，使用傳統(tǒng)經(jīng)典計算機的已知算法解決這個問題仍然極其困難。

使用DQI，量子計算機可以將此轉(zhuǎn)換為解碼里德-所羅門碼（在DVD和二維碼中廣泛使用的代碼系列）的問題。人們已經(jīng)開發(fā)出非常好的算法來解碼里德-所羅門碼，因此，使用DQI的量子計算機可以找到比經(jīng)典計算機上已知算法更好的OPI問題近似最優(yōu)解。例如，我們的分析表明，某些OPI問題的例子可以被量子計算機使用僅約幾百萬次基本量子邏輯操作來解決，而在傳統(tǒng)經(jīng)典計算機上使用最高效的已知經(jīng)典算法需要超過10的23次方（一千萬億億）次基本操作才能解決。

退一步來看，我們可以問為什么將優(yōu)化問題轉(zhuǎn)換為解碼問題會有優(yōu)勢？通過更深入地理解這一點，人們可以希望獲得直覺來指導(dǎo)尋找量子計算機可能提供優(yōu)勢的其他優(yōu)化問題。

我們開始的優(yōu)化問題和我們將其轉(zhuǎn)換的解碼問題都是稱為NP困難問題的東西。這表明，即使在量子計算機的幫助下，也不可能高效地找到這些問題所有實例的精確解。通過使用量子效應(yīng)，DQI將一個困難問題轉(zhuǎn)換為另一個困難問題。這如何實現(xiàn)任何目標(biāo)？關(guān)鍵在于NP困難性涉及給定問題最困難實例的難度。如果問題實例被限制具有一些額外結(jié)構(gòu)，這可以使它們更容易。DQI的承諾是，某些類型的結(jié)構(gòu)可能使解碼問題更容易，而不會同時使用傳統(tǒng)計算機解決優(yōu)化問題更容易。

在OPI問題中，產(chǎn)生的格子具有代數(shù)結(jié)構(gòu)；基向量的分量不是任意的，而是通過將一個數(shù)提升到連續(xù)更高次冪獲得的。這種代數(shù)結(jié)構(gòu)反映在原始優(yōu)化問題（OPI）和量子計算機可以將其轉(zhuǎn)換的解碼問題（里德-所羅門解碼）中。這種結(jié)構(gòu)使解碼問題變得更容易，但據(jù)我們所知，并不會使傳統(tǒng)計算機的優(yōu)化問題更容易。在這種情況下，使用量子計算的力量將優(yōu)化問題轉(zhuǎn)換為解碼問題的能力提供了優(yōu)勢。

在論文中，我們還考慮了缺乏代數(shù)結(jié)構(gòu)但基向量稀疏（即主要由零組成）的更通用格子。相應(yīng)的優(yōu)化問題稱為max-k-XORSAT。格子的稀疏性反映在每個約束只涉及少數(shù)變量（最多k個）這一事實中。在max-k-XORSAT中，約束比變量多，不可能滿足所有約束。相反，人們希望找到滿足盡可能多約束的解決方案。雖然聽起來很抽象，但max-k-XORSAT問題通常用作新優(yōu)化算法的測試平臺，并包括許多其他著名的優(yōu)化問題作為特殊情況，如max-cut和QUBO。

DQI可以將max-k-XORSAT轉(zhuǎn)換為由稀疏矩陣定義的代碼的解碼問題。這樣的代碼稱為低密度奇偶校驗（LDPC）代碼。在1960年代發(fā)現(xiàn)稀疏性使解碼問題變得更容易。然而，原始max-k-XORSAT問題的稀疏性也使其在傳統(tǒng)計算機上使用稱為模擬退火的算法更容易解決。因此，很難找到具有恰當(dāng)稀疏性的max-k-XORSAT問題，使解碼器比我們比較的模擬退火算法受益更多。在論文中，我們提出了一個例子問題，其中稀疏性恰到好處，使DQI似乎比模擬退火具有速度優(yōu)勢。然而，我們設(shè)法使用專門為我們的例子量身定制的專用算法在傳統(tǒng)計算機上高效地解決了這個問題。因此，目前，與OPI不同，我們沒有既可以被DQI解決又無法被在傳統(tǒng)計算機上運行的任何已知算法高效解決的max-k-XORSAT問題的例子。

由于稀疏優(yōu)化問題具有廣泛的實際應(yīng)用，我們繼續(xù)尋找DQI可能在稀疏優(yōu)化問題上實現(xiàn)量子優(yōu)勢的方法。特別是，DQI激發(fā)了對解碼LDPC代碼的經(jīng)典和量子算法的新研究方向。

DQI算法為開發(fā)量子優(yōu)化算法提供了強大的新工具包。這種將優(yōu)化問題轉(zhuǎn)換為解碼問題的方法為解決該領(lǐng)域最長期存在的問題之一提供了新途徑。我們很興奮地看到研究人員，無論是在谷歌還是在更廣泛的社區(qū)中，將用這些工具構(gòu)建什么。

Q&A

Q1：什么是解碼量子干涉算法？它有什么特殊之處？

A：解碼量子干涉（DQI）是由谷歌量子AI開發(fā)的一種高效量子算法，它利用量子力學(xué)的波動特性創(chuàng)建干涉模式，能夠找到經(jīng)典計算機極難找到的近最優(yōu)解。該算法的特殊之處在于能將優(yōu)化問題轉(zhuǎn)換為解碼問題，從而利用已有的強大解碼算法來解決優(yōu)化難題。

Q2：最優(yōu)多項式交集問題為什么適合用量子計算機解決？

A：最優(yōu)多項式交集問題具有代數(shù)結(jié)構(gòu)，其格子的基向量分量通過將數(shù)字提升到連續(xù)更高次冪獲得。這種結(jié)構(gòu)使得對應(yīng)的解碼問題（里德-所羅門解碼）變得更容易，但不會使原始優(yōu)化問題在經(jīng)典計算機上更容易解決，因此量子計算機能夠獲得優(yōu)勢。

Q3：DQI算法在實際應(yīng)用中有什么限制？

A：DQI算法需要解決解碼問題來構(gòu)建干涉模式，這本身也是一個困難的計算問題。此外，該算法需要大規(guī)模的容錯量子計算機才能實現(xiàn)，目前的量子硬件還無法支持。對于某些問題如稀疏優(yōu)化問題，找到量子優(yōu)勢仍然是個挑戰(zhàn)。