平面超導器件上非平面圖問題的量子近似優化

2021-02-20 量子計算漫談

本文在Google Sycamore超導晶片上實驗了QAOA算法，並在三類不同連通性的圖問題上比較了算法的效果。

題目：Quantum Approximate Optimization of Non-Planar Graph Problemson a Planar Superconducting Processor

作者：Google AI Quantum and Collaborators

Scite：45次

arXiv：2004.04197

量子近似優化算法（Quantum approximate optimization algorithm，QAOA）是目前研究最多的利用近期（near-term）量子器件進行優化的門電路模型算法，也是用來測試量子硬體系統整體性能的一種通用基準；有關QAOA的實驗已在超導量子比特[1]，離子阱[2]以及光學系統[3]等多種不同的物理系統上實現。而本文則首次在實驗上顯示了隨著深度的增加，QAOA算法的性能也隨之提高；另外，文獻[1,2,3]等都只對定義在物理器件拓撲圖上的問題進行了實驗，本文則首次將QAOA算法應用在非平面圖問題上，包括Sherrington-Kirkpatrick 模型以及 3-正則圖最大割問題。

本文研究的問題是最小化代價函數C(z)，即

其中zj為變量，權重wjk的取值為{0，±1}；通過將變量替換為泡利Z算符，C(z)對應一個量子算符C，

其中Zj表示作用在qubit j上的泡利Z算符。由於式中每一項ZjZk至多作用在兩個qubit上，因此我們可以將上述問題的實例對應到圖上；具體來說，當wjk≠0時，圖上的點j和k之間就存在一條邊。

 

QAOA算法是量子絕熱算法的離散化版本，最基本的QAOA算法由兩個酉算符構成，其中第一個是目標函數C對應的酉算符，

第二個為轉移算符，用來完成問題的解空間中不同疊加態之間的轉移，定義為：

上述兩個算符的交替執行就構成了QAOA算法的基本框架；若算法的重複次數（深度）為p，qubit的個數為n，則算法中將有2p個參數，記為：

根據以上參數，算法首先會製備量子態

其中|+>n是定義在2n個計算基態上的均勻疊加態。然後通過對量子態的測量以及經典計算機的輔助，算法找出最優的參數最小化代價函數C的期望：

令Cmin=minzC(z)，則算法在不同實例的性能由<C>/Cmin表示。本文中Cmin一般是負數，所以實際上是在最大化<C>/Cmin。

   

通過將上述問題限制在不同連通性的圖上，本文研究了QAOA算法在三類不同問題上的應用表現，包括：

硬體格點問題。問題所對應的圖為物理器件拓撲圖，因此算法在執行過程中不需要使用swap門將邏輯量子門編譯到物理量子門上，這是最簡單的實例。

Sherrington-Kirkpatrick(SK)模型。問題定義在完全圖上，其中權重wij是從集合{1,-1}中隨機挑選得到，這是最困難的實例。

隨機3正則圖上的最大割問題。當權重wij都為1時，原問題等價於最大割問題（實際上最大割的代價函數與本文中所定義的相差一個常數項）；而Farhi[4]等人證明在3正則圖上，p=1的QAOA算法對於最大割問題的近似比為0.6924。因此本文實驗了算法在隨機3正則圖上的性能。

本文的實驗均是在谷歌Sycamore超導處理器上進行，使用了其中23個量子比特，兩比特門的平均保真度為99.4%，量子比特的平均測量保真度為95.9%，器件拓撲圖如下圖所示。

圖1.實驗物理器件拓撲圖

本文首先考慮了當p=1時，不同的參數γ與β對QAOA算法性能的影響，主要結果如圖2所示：

圖2. p=1時，QAOA算法性能理論與實驗立體峰圖

上圖中，硬體格點圖問題的qubit數為23，3正則圖最大割問題為14，SK模型為11。從中可以看出實驗中QAOA算法的能量峰圖與理論預測符合得很好，圖中紅色的線是算法使用梯度下降法從初始參數出發到達局部最優參數的路徑，表明QAOA算法在這三個問題上可以成功運行。

 

此外，本文研究了在不同qubit數n與深度p下，QAOA算法的性能，並使用<C>/Cmin作為衡量算法性能的指標，其中最優解的取值為1，隨機猜測的取值為0；主要結果如圖3,4所示。

圖3. QAOA算法性能隨qubit數n變化曲線圖

從上圖可以看出當p=3時，隨著qubit數的增加，<C>/Cmin在硬體格點圖問題上趨向於某一常數，與n無關，這是由於期望<C>中ZiZj項的計算只會涉及在圖上與i,j距離小於p的qubit，因此當p固定時，ZiZj項的誤差不會隨n而變化，那麼<C>/Cmin相對於n就是常數。而非局部的誤差會破壞這一性質，因此在圖2中，硬體格點圖問題實驗數據表現出了與n無關的性質，而SK模型的性能則隨著n的增大而迅速下降。

圖4. QAOA算法性能隨深度p變化曲線圖

理論上，隨著深度p的增加，算法性能也將隨之提升，但是由於噪聲的影響，深度p增加會帶來額外的誤差。此前，只有在n=2的小規模問題上能夠觀察到性能隨深度提升。而在本文的實驗中，對於10<n≤23的規模，大約有一半的實例在p=3時達到性能的最大值，且隨著深度p的增加，<C>/Cmin趨向於平緩，並未顯著下降。

目前有關QAOA的實驗大多都是最小深度（p=1）的，並且其代價函數所對應的圖往往都是物理器件本身或是其子圖，而絕大多數現實世界中組合優化問題的實例都是無法直接映射到物理器件的拓撲圖上，通常需要使用swap門以及路由量子比特來將其編譯到物理器件上，但是額外增加的代價則要求量子硬體具有更高的保真度；依託Google最先進的Sycamore晶片，本文在非平面圖問題上展示了量子近似優化算法在實際設備上實現和性能方面的重要進展，同時也著重強調了在將量子優化算法應用到實際問題上所將出現的各種挑戰。

[1] D. M. Abrams, N. Didier, B. R. Johnson,M. P. d. Silva, and C. A. Ryan, Implementation of the XY interaction familywith calibration of a single pulse, (2019), arXiv:1912.04424 [quant-ph].

[2] G. Pagano, A. Bapat, P. Becker, K. S.Collins, A. De, P. W. Hess, H. B. Kaplan, A. Kyprianidis, W. L. Tan, C.Baldwin, L. T. Brady, A. Deshpande, F. Liu, S. Jordan, A. V. Gorshkov, and C.Monroe, Quantum approximate optimization with a trapped-ion quantum simulator,(2019), arXiv:1906.02700 [quant-ph].

[3]X. Qiang, X. Zhou, J. Wang, C. M.Wilkes, T. Loke, S. O』Gara, L. Kling, G. D. Marshall, R. Santagati, T. C.Ralph, J. B. Wang, J. L. O』Brien, M. G. Thompson, and J. C. F. Matthews,Large-scale silicon quantum photonics implementing arbitrary two-qubitprocessing, Nature Photonics 12, 534 (2018).

[4]E. Farhi, J. Goldstone, and S. Gutmann, Aquantum approximate optimization algorithm, (2014), arXiv:1411.4028 [quant-ph].

相關焦點

  • 高溫超導量子相變領域取得重大研究進展!電子科技大學在《Science...
    電子科技大學電子薄膜與集成器件國家重點實驗室博士生楊超（導師李言榮院士）為第一作者，熊杰教授為通訊作者，張萬裡教授、李言榮院士為共同作者。這是該校首次以第一單位在《科學》正刊上發表研究成果，該發現是在該校國家重點實驗室做出的原創成果，標誌著電子科技大學在高溫超導量子相變領域取得了重大研究進展。
  • Science:膠體量子點器件綜述
    然而，傳統的半導體器件往往用於製作面積較小的平面晶片，當需要大面積應用時成本很高，此外，受限於其堅硬的特點，不能應用於紙、纖維、塑料等柔性襯底及彎曲的表面，這些都限制了傳統半導體材料在現代生活中的應用。近年來，「一個器件即是一塊晶體」的概念逐漸興起，這對材料的發展提出了挑戰，並提出了自下而上製作器件的思路。
  • 超導量子計算進展:多體局域化遷移率邊界的量子模擬
    多體局域化在很多方面和安德森局域化類似，但不同之處在於其存在長程關聯，或者更廣泛的含義上屬於「非可積系統」。過去幾年相關課題進展很多，可以研究豐富的物理現象。各態遍歷的熱化與多體局域化量子相之間的轉變是一種非平衡量子相變，它關注的是高激發態的性質。為了更加清晰地研究這一量子相變，人們引入能量密度譜來區分一個量子態到底是高激發態還是靠近基態。
  • 算法:平面圖自動生成
    ,期望可以啟發對CAAD感興趣的同學 平面圖生成(EFP)是一個實驗性的項目，研究平面的生成及優化的可能性。初始條件為各個房間關係及人流分布, 通過一個遺傳算法來優化生成平面圖，其優化的限制因素為步行時間和走廊的長度等。EFP項目只是從設定的優化條件來進行平面布局，而不去考慮傳統的布局要求及可建性等因素。EFP的目標是如何通過算法將顯性、隱性的限制條件結合起來,生成高複雜度的平面圖。EFP的平面圖是從它的遺傳編碼中「生長」出來，使用的算法是圖像收縮方法生成布局及蟻群算法生長走廊。
  • 3.4規律性和非規律性骨骼平面構成ps基礎
    就像我們學習繪畫時，無論是素描還是色彩，老師都會告訴我們，在構圖上要注意黃金比例，構圖要有一個形式線，比如三角形構圖，其實就是我們設計中講的骨骼。平面構成常見的構成形式分為規律性和非規律性兩大類：有規律的構成形式有重複、近似、漸變、發射、特異等；非規律的構成形式有密集、對比、分割、肌理、空間等。1. 規律性骨骼有精確嚴謹的骨骼線，有秩序的排列。
  • 用超導鄰近效應探測分子輸運性質
    分子電子學中的關鍵問題之一是研究分子的導電性機理。更具體地說，關鍵問題是確定分子結是表現為隧道勢壘，還是提供電子或空穴傳導通道。由於最高佔據分子軌道（HOMO）和最低未佔據分子軌道（LUMO）之間的大能隙，通常在計算中假設分子僅包含一個用於電子或用於空穴的導電通道。實驗上，無論使用局部探針還是兩個金屬電極之間小間隙的測量，強烈依賴於分子和與之接觸之間的連接性質；這種連接難以優化。
  • 中科院戰略性先導科技專項B類「超導電子器件應用基礎研究」
    會議現場9月9日，中國科學院戰略性先導科技專項B類「超導電子器件應用基礎研究」實施方案論證會在北京召開。中國科學院副院長陰和俊、秘書長鄧麥村、副秘書長潘教峰出席會議。會上，項目負責人謝曉明研究員作了專項實施方案報告，專家就專項的應用驗證、平臺工藝、合作單位、國際委員會作用、平臺的開放性、發展方向等問題進行了質詢。
  • 超導維度、超越維度
    據說這一理論對後續涉及電磁相互作用與弱相互作用的統一問題有借鑑意義。由此，我們已經感覺到有一點高大上了。 (4) 到了高溫銅氧化物超導電性那裡，原本BCS 理論的無磁性單態被量子磁性取代，電子自旋的作用凸顯出來。除此之外，諸如d 波配對機制等新物理也大行其道。
  • 看懂室內平面圖畫法、平面配置原則,一次了解常見的平面圖種類!
    室內平面圖是做建築設計或室內裝修時很重要的參考圖面，所有的工程都會依照規劃的平面圖進行施作。在從前沒有電腦的時代，平面設計師也許都是用手繪；可是在電腦發達的現今社會，使用AutoCAD等軟體繪製已經是相關產業的基本功夫。
  • 優於現有量子計算機性能 日本量子退火機真有這麼牛?
    為此，科技日報記者採訪中國科學院量子信息重點實驗室教授韓正甫得知，原來，這臺計算機不是傳統的量子計算機，而是一種專用量子計算機，又被稱為量子退火機，或被稱為量子模擬機。「準確地說，這臺計算機是日本科研人員用光學器件構成的量子退火機，和加拿大D-Wave公司用超導器件構成的量子退火機放在一起比較，日本的量子退火機在某些指標上相對優越。」韓正甫說。
  • 平面圖表現 怎樣有效的傳達圖片信息 畫出高大上的平面圖
    但是小編還是得在開頭簡單講講：什麼是平面圖？平面圖需要包含什麼信息？怎麼樣進行平面表現？首先大家應該了解的一個問題是我們為什麼要在每次作品匯報時放上我們的平立剖以及透視。答案就四個字：傳達信息。很多同學，尤其是學霸們總會在最後一刻通宵達旦，指望通過霸氣的圖面博得老師的青睞。
  • 戶型平面圖要怎麼看 看懂戶型平面圖很重要
    對於大家來說，房子購買了之後自己是要長期居住的，所以在自己購買房屋的時候就需要挑選一個好的戶型才行，而現在大家去開發商處看房屋戶型的時候一般都只能看到戶型平面圖，但是很多人都不太會看戶型平面圖，那麼戶型平面圖要怎麼看呢？接下來大家就來一起了解一下吧。
  • Microwave Office 微波平面電路設計工具介紹
    引言 從八十年代開始,國際上微波電路技術已經從傳統的波導及同軸線元器件和系統轉移到採用微波平面電路(又稱微波集成電路或微波印刷電路), 其特點是把電路印製在介質基片平面上。 體積,重量和成本都大大減小。 除了微帶,共面波導,槽線,懸置線等無源電路以外, 微波半導體器件也可以集成在平面電路上, 構成混合微波集成電路。
  • 複平面與非歐幾何
    黎曼幾何中的一條基本規定是：在同一平面內任何兩條直線都有公共點（交點）。這個非歐幾何的規定，沒有點想像力，的確很難理解。我們先嘗試用複平面來理解。如封面的圖，從北極連接到球面上的一點總是可以投影到複平面上的一點。
  • 【泡泡圖靈智庫】使用二次曲面和平面的結構感知SLAM(arXiv)
    同時定位和建圖（SLAM）是移動機器人的一個基本問題。雖然基於點的SLAM方法提供了精確的相機定位，但隨著生成的地圖缺乏語義信息。另一方面，目前先進的目標檢測方法可以根據單個圖像提供關於場景中存在的物體的豐富信息。這項工作將兩者結合起來，並提出了一種將通用對象表示為二次曲面的方法，該方法允許對象檢測無縫地集成到SLAM框架中。對於場景覆蓋，主要平面結構被建模為無限平面。
  • 二維超導材料
    近年來，許多二維材料例如石墨烯、FeSe-SrTiO3、單層的NbSe2和MoS2等材料相繼被報導出超導電性，並展現出豐富的物理性質(例如電荷密度波(charge density wave，CDW)、Ising 超導、量子Griffiths 相變、量子金屬態等)。此外，二維超導材料在超導微納器件中具有重要的潛在應用價值。
  • 從波的角度理解平面波和K點採樣 (深度好文)
    上圖中，左邊是實空間中的一個一維波函數示意圖，它由一系列頻率不同的正弦波組成，這個波函數被一個原子核吸引。右邊是這些波的頻率(x軸)及每個頻率上波的數量，對應於平面波的線性組合係數。如上圖註解所述，每個格點r上的波函數在倒空間中沿G展開，這就是說，我們這裡有多少G值，那麼真實空間中就有多少個對應頻率的正弦波基函數，而這些正弦波基函數再線性組合而成體系波函數，從而密度泛函問題轉化成正弦波的係數問題，而正弦波的係數問題，又轉變為倒空間裡G值上的強度問題。4.
  • 如何實現100萬個量子比特的糾纏和量子計算
    超導量子計算機的核心部件是超導量子處理器晶片，和半導體集成電路晶片一樣，規模大了以後純靠人手工無法完成設計、仿真，需要EDA軟體輔助設計和仿真。超導量子處理器晶片基於獨特的超導約瑟夫森結這種非線性器件，基本組成單元是量子器件而不是傳統電子學元件。
  • 只需要7nm晶片1.25%的能耗,就能運行這顆超導晶片,包含冷卻開銷
    蕭簫 發自 凹非寺量子位 報導 | 公眾號 QbitAI一顆7nm製程的晶片，所需能量竟然能被用來運行80個超導晶片？沒錯，全球首個絕熱超導微晶片MANA，現在已經問世。這種超導晶片在處理數據時，運行效率可達2.5GHz，與目前所需的計算技術相匹配。如果進一步研發的話，處理速度還能再進一步優化。
  • Science封面:谷歌實現量子化學模擬,迄今為止全球首例!
    8月27日，谷歌量子計算研究團隊宣布其使用量子計算機對化學反應路徑進行建模取得了突破性進展，這是迄今為止首次，也是最大規模的化學量子計算。其發表的題為《超導量子比特量子計算機的 Hartree-Fock 近似模擬》（Hartree-Fock on a Superconducting Qubit Quantum Computer）的成果論文，當天便登上了《自然》雜誌封面。