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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Q&A

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

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

Q2：最優(yōu)多項(xiàng)式交集問(wèn)題為什么適合用量子計(jì)算機(jī)解決？

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

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

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