QAOA 求解最大割、獨立集問題——需要全局信息

2021-01-18 量子計算漫談

本文討論了在d-正則隨機二部圖上，淺層QAOA算法在最大割以及最大獨立集兩個問題上近似比的上界。

題目：The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph 

作者：Edward Farhi, DavidGamarnik, and Sam Gutmann

Scite：30 次

ArXiv：2005.08747


量子近似優化算法（QuantumApproximate Optimization Algorithm，QAOA）常被用來求解組合搜索問題的近似解，並且在諸如三正則圖上的最大割[1]等問題上被證明具有非平凡的近似比，但是QAOA算法是否在一些問題有比經典算法更好的近似比目前為止仍然是一個開放問題。本文則討論了在隨機d-正則二部圖上，當深度受限時，QAOA算法在最大割以及最大獨立集兩個問題上近似比的上界，表明淺層的QAOA算法在這兩個問題上的表現很難超越經典算法。


對於定義在圖上的問題，他們的代價函數可以被寫為如下形式：

其中Cij是與邊(i,j)相關的代價函數。假如頂點對應的值使得這條邊上的約束被滿足，則Cij=1，否則Cij=0；算法的目標則是儘可能增大的值。

 

在最大割問題中，邊(i,j)上對應的代價函數為

 

其中bi∈{0,1}，當bi，bj取值不同時，代價函數等於1，注意到每一個比特串都對應了一個圖上的割。


而對於d-正則圖上的最大獨立集問題，邊(i,j)上的代價函數為

其中bi∈{0,1}，這裡因為圖是d-正則的，如果將上式對所有邊進行求和，那麼其中第一項等價於計算比特串b=(b1,…,bn)的海明權重，即被選中的頂點集合的大小，但是由於任意一個比特串並不都對應一個獨立集，因此需要加入第二項進行約束，可以證明如果算法輸出的比特串b的代價C(b)=Cout>0，那麼通過剪枝可以輸出一個字符串，其對應一個大小至少為Cout的獨立集。


QAOA算法的相關內容可以參考本公眾號之前的一篇關於量子近似優化的文章。 


敘述本文的結果還需要用到以下圖論上的結果。在隨機d-正則圖上，對於最大割問題，存在常數ρd，使得對於充分大的n，最大割的大小以高概率等於


類似地，對於最大獨立集問題，也存在常數σd，使得對於充分大的n，最大獨立集的大小以高概率等於

本文作者在上一篇類似的工作中[2]已經討論了平均頂點度數為d的隨機圖上，深度受限的QAOA算法在最大獨立集問題上的近似比上界（~0.854），而本文討論了在隨機d-正則二部圖上，QAOA算法在最大割問題與最大獨立集問題上最壞的近似比上界。


具體來說本文證明了，在隨機d-正則二部圖上，若存在A<1，使得QAOA算法的深度p滿足如下關係，

則對於最大割問題以及最大獨立集問題，QAOA算法輸出的期望滿足

其中A<A'<1。而由文獻[3,4,5]可知，當d充分大時，

同時任意一個d-正則二部圖都有一個大小為nd/2的割，以及n/2的獨立集，因此當d變大時，QAOA對最大割問題的近似比不會好於1/2，對最大獨立集問題的近似比(~ln d/d)則會趨向於0 。


若將QAOA算法的輸出期望按照邊展開，可以得到下式：

由於QAOA算法本身的局部性，因此對於p層的QAOA算法，每條邊上的輸出期望都僅與和這條邊距離在p之內的邊有關，稱這些邊是這裡考慮的邊的p鄰居。同時，可以證明在隨機d-正則圖與隨機d-正則二部圖，當p足夠小時，對於幾乎所有的邊，其p鄰居都構成一顆樹，並稱這類邊為中心邊；顯然由中心邊的p鄰居構成的子圖之間是同構的，也就是說所有中心邊的輸出期望是相同的，因此QAOA算法的性能取決於如何評估中心邊上的輸出期望；本文通過在隨機d-正則圖上已知的關於最大割與最大獨立集的界（參見背景知識）給出了中心邊輸出期望的上界，並由此在隨機d-正則二部圖上證明了上文中的主要結論。


可以看到這一證明依賴於QAOA算法的層數p足夠小，而當QAOA算法的層數增加，使得每條邊的p鄰居都接近於完整的圖後，證明也相應的不再成立；換句話說，QAOA算法必須看到完整的圖，才有可能取得較好的性能。



本文所使用的的技術依賴於淺層QAOA算法在這些問題本身的局部性，而當深度增加或者相關的問題本身就具有某種全局性時，例如完全圖上的TSP問題，那麼因為QAOA算法能夠得到完整的圖的信息，本文的技術就不能應用了，那麼在這種情況下是否也能給出QAOA算法近似比的上界或者下界？

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv:1411.4028,2014.

[2] Edward Farhi, DavidGamarnik, and Sam Gutmann. The quantum approximate optimization algorithm needs to see the whole graph: A typical case. arXiv:2004.09002,2020.

[3] Don Coppersmith, David Gamarnik, Mohammad Hajiaghayi, and Gregory B Sorkin. Random max sat, random max cut, and their phase transitions. Random Structures &Algorithms, 24(4):502-545, 2004.

[4]Amir Dembo, Andrea Montanari, and Subhabrata Sen. Extremal cuts of sparse random graphs. The Annals of Probability, 45(2):1190-1217, 2017.

[5] A. Frieze. On the independence number of random graphs. DiscreteMathematics 81, pages 171-175,1990.

封面圖片來源於https://www.britannica.com/quiz/quantum-mechanics。



相關焦點

  • Arxiv網絡科學論文摘要16篇(2020-08-26)
    遏制疾病的互動區域政策;在Twitter上使用文本挖掘和圖機器學習來預測變化的個體;度差異：表徵複雜網絡中結構異質性的簡單方法;駕駛員學習城市規模的動態平衡;中國大氣臭氧對COVID-19鎖定的不同反應;考慮局部和全局信息傳播
  • Arxiv網絡科學論文摘要22篇(2020-08-04)
    鑑於現實生活中有多名警務人員在值班，這使問題更難以解決。在本文中，我們使用籤到，犯罪，事件響應數據和POI信息，為多名警官制定了動態犯罪巡邏計劃問題。我們提出一種聯合學習和非隨機優化方法，用於表示可能的解決方案，其中多個警官首先同時在高犯罪風險地區而不是低犯罪風險地區巡邏。後來，實施了元啟發式遺傳算法（GA）和布穀鳥搜索（CS）來找到最佳路線。
  • Arxiv網絡科學論文摘要17篇(2020-08-28)
    我們從健康病例的ECG數據中發現MRNs具有更高的互信息性，並且相互之間的信息高度一致，且各個程度分布之間的差異較小。在疾病的情況下，可以看到各層之間相似性的特定度量存在顯著差異。在與局部異常相關的疾病（例如束支傳導阻滯）的情況下，連貫性受影響最大。我們注意到，使用所有措施進行全面分析以得出針對特定疾病的模式非常重要。
  • Arxiv網絡科學論文摘要17篇(2020-08-20)
    我們還通過回溯數據集來估計首例病例和死亡發生的日期，並將它們與報告的日期進行比較。不受約束的方法通常無法將估計的變量保持在其物理範圍內，並且可能導致不可靠的估計，從而需要積極地平滑原始數據。為了克服這些缺點，提出了一種約束估計方法，該方法將模型變量保持在預定範圍內，並且還可以促進估計的平滑性。約束估計可以直接應用於原始數據，而無需預先平滑以及相關的信息丟失和額外的延遲。它也可以輕鬆擴展以處理其他信息，例如感染個體的數量。結果問題被轉換為具有線性和凸二次約束的凸二次優化問題。
  • Arxiv網絡科學論文摘要17篇(2020-08-10)
    從冪律到極值混合分布;電晶體：基於網絡科學的歷史視角;使用新Twitter數據集表徵COVID-19錯誤信息社區;NewsTweet：在線新聞的社交媒體嵌入數據集;調查高知名度Twitter帳戶的「社交」協調目標
  • 「割補法」,巧解幾何體的計算問題
    提示：若已知的幾何體為組合體，則需要先拆分為一個個常見幾何體——也即分解成多個「常見空間幾何體計算」基本問題來解決。2.割補法：需要時，可利用「割補法」先把組合體轉化成一個更方便求解的幾何體，再利用間接法或直接法求解。② 表面積多面體：把各個可見面的面積累計旋轉體：一般可把弧面部分展開成平面來計算；再把各個可見面的面積累計；計算組合體的表面積時，應注意重合部分的處理——不多、不重、不漏。
  • Arxiv網絡科學論文摘要18篇(2020-11-17)
    這些集中度度量中的一些可以使用節點的本地信息來計算，例如度集中度和半局部集中度度量。其他人則使用網絡的全局信息，例如緊密性中心，介數中心性中心，特徵向量中心，Katz中心性，PageRank等。在本次調查中，我們將討論這些集中度度量和最新技術文獻，包括將集中度度量擴展到不同類型的網絡，在動態網絡中更新集中度值的方法，識別top-k節點的方法，近似算法，開放式研究與領域相關的問題，等等。
  • Arxiv網絡科學論文摘要15篇(2020-08-17)
    傳輸網絡上的空間隨機SIR模型及其在中國COVID-19疫情中的應用;以貌取人：面部感知對社會網絡中心性的影響;使用移動數據對COVID-19暴發進行風險繪圖;基於大規模出行數據集的乘船旅行深度分析;宿主間空氣傳播的多相流問題用於基於科學的社會距離準則;一種標準不完全適合：Stack Overflow
  • 數學都知道 — arXiv專輯(2020.12.2)
    他在其學位論文和此期間發表的一系列文章中介紹了一種原始的形式化方法，來解決有限線性偏微分方程系統初始條件問題的可解性。他的構造隱式地將單項式偏微分方程系統解釋為單項式的乘法集的生成族。他介紹了一種在乘法集上的算法方法來計算相容性條件，並研究在給定初始條件下線性偏微分方程系統解的存在性和唯一性問題。使用對單項式的除法運算的細化來制定相容性條件，該單項式將變量集劃分為乘法和非乘法變量。
  • 170多萬篇論文,存儲量達1.1 TB,Kaggle上線arXiv完整數據集
    近期，為了讓 arXiv 可用度更高，康奈爾大學和其他一些開發者在 kaggle 上創建了一個免費、開放的 arXiv 數據集。該數據集是一個含有 170 多萬篇學術論文的存儲庫，用戶可以獲取論文的標題、作者、類別、摘要、全文 pdf 等。
  • 一文解析基於特徵點的視覺全局定位技術
    基於已建的地圖，匹配歷史中最相似的地圖子集（圖像/點雲/特徵點），根據匹配到的地圖子集所提供的歷史位姿真值、特徵點坐標真值，計算點對間的變換矩陣，求解當前相機位姿。在全局定位中，內點指正確的匹配，外點指錯誤的匹配，參數模型指匹配點對的空間變換矩陣。如 Fig. 14所示，經過 RANSAC 算法優化後，匹配更加合理。RANSAC 所期望找到的匹配子集需要滿足兩個指標：內點重投影誤差儘可能小；內點數量儘可能多。
  • Arxiv網絡科學論文摘要15篇(2020-09-29)
    同時相關性和多樣性：一種新的推薦推理方法;阿根廷銀行間貨幣市場的網絡拓撲;反應式監管：一種收集反諷數據的新方法;基於共享網絡的分解方法求解大規模多模校車路徑問題;放寬對社會網絡的共同信念;說服遇到AI：社會工程對策設計的倫理考慮;Twitter上COVID-19的（不實）信息生態系統
  • Arxiv網絡科學論文摘要13篇(2020-10-26)
    超圖的可控性原文標題： Controllability of Hypergraphs地址： http://arxiv.org/abs/2005.12244但是，這個問題空間跨越了視頻和問題的巨大差異。我們討論了創建和表徵社交VQA數據集的方法，包括1）眾包與內部創作，包括我們創建的兩個新數據集（TinySocial-Crowd和TinySocial-InHouse）與先前存在的Social-IQ數據集的樣本比較； 2）用於描述給定視頻的難度和內容的新規則； 3）用於描述問題類型的新規則。
  • 若DL沒了獨立同分布假設,樣本不獨立的機器學習方法綜述
    比較常見的需要處理 Non-IID 數據問題的應用場景包括：異常檢測（Outlier Detection）。訓練樣本數據中存在的異常值（例如人臉識別中的眼鏡、頭髮遮擋等），會在估計過程中引入較大方差。傳統機器學習算法一般通過擴大樣本數據集來解決這一問題。
  • Arxiv網絡科學論文摘要11篇(2020-08-05)
    量化這些變化需要一個慣常的反事實，即應對空氣汙染物的天氣和季節變化的原因。我們使用來自NASA GEOS-CF模型的信息驅動的機器學習算法來評估來自46個國家/地區的5,756個觀測點的二氧化氮（NO 2 ）和臭氧（O 3 ）的變化到2020年1月到2020年6月。
  • Arxiv網絡科學論文摘要16篇(2020-08-18)
    在使用三種不同規模，解析度和模式的移動性數據集（在七個不同城市的值機，大學中的WiFi連接事件以及電動自行車的GPS軌跡）的多智能體模擬中，普遍觀察到了這種趨勢。利用網絡在人類流動中的作用的策略在疾病控制和正常社交活動之間提供了更好的平衡。
  • Arxiv網絡科學論文摘要14篇(2020-09-09)
    為此，我們使用圖對輪廓匹配問題進行建模，並開發一種基於置信度傳播（BP）的算法，與現有技術相比，該算法以明顯更有效，更準確的方式解決了該問題。我們在三個真實的數據集（包括來自四個不同社會網絡的數據）上評估了所提出的框架，並展示了如何有效且高概率地匹配不同OSN中的用戶資料。我們表明，就用戶對的數量而言，所提出的模型生成具有線性複雜度，這比最新技術（具有三次複雜度）要有效得多。
  • Arxiv網絡科學論文摘要18篇(2020-11-03)
    在這裡，我們構建了一個關於中國大陸經濟活動的數據集，即網格化的企業數據集（GED），該數據集以經度尺度0.01 ^ circ 來衡量緯度0.01 ^ circ 的企業數量。具體來說，我們的數據集刻畫了2005-2015年間在中國大陸註冊的大約2550萬家公司的地理分布。細粒度和長期可觀察性的特性使GED具有很高的應用價值。
  • Arxiv網絡科學論文摘要9篇(2020-12-03)
    隨著網絡攻擊的盛行，衡量基礎設施網絡的健壯性已成為一個重要問題。迄今為止，已經為此目的提出了許多魯棒性度量。魯棒性度量具有以下三個屬性是理想的：考慮全局網絡拓撲，嚴格增加連結數量，以及在稀疏網絡上的節點數方面具有二次複雜性。當前，滿足這三個屬性的大多數度量都是基於圖譜的。本文提出了一種稱為「平均網絡流」（ANF）的魯棒性度量，該度量滿足這三個屬性，但不基於圖譜。
  • [年報]長城信息2005年年度報告
    年4月2日召開的公司第三屆董事會第九次會議上，林平先生因工作變動辭去了公司副總裁、財務總監職務，董事會聘任劉煌先生為副總裁，張葵女士為財務總監 2005年9月16日召開的公司第三屆董事會第十二次會議上，陳肇雄先生因工作需要辭去了公司董事及董事長職務，盧明先生因工作需要辭去了公司董事職務,提名李衛生先生和張安安女士為繼任董事候選人。