[發明專利]一種求解約束優化問題的量子近似算法

在審

• 申請號: 202210435636.3
• 申請日: 2022-04-24
• 公開（公告）號: CN115577780A
• 公開（公告）日: 2023-01-06
• 發明（設計）人: 申元霞;劉暢;謝悅;阮越;張學鋒
• 申請（專利權）人: 安徽工業大學
• 主分類號: G06N10/60
• 分類號: G06N10/60
• 代理公司: 合肥昊晟德專利代理事務所(普通合伙) 34153
• 代理人: 何梓秋

本發明公開了一種求解約束優化問題的量子近似算法，屬于量子計算技術領域。本發明將二次無約束的二元優化方法和量子交替算符擬設方法融合在同一量子近似優化算法框架中，利用經典的貪心算法，對帶約束的優化問題進行求解，得到的近似最優解作為一個約束條件，根據約束條件重新設計編碼演化算符，使得表征解的量子態演化限制在可行解范圍內，并且，將約束優化問題通過添加懲罰項轉化為無約束優化問題，當有解違反約束時，在目標函數中添加懲罰項，使不滿足約束條件的解的期望值比滿足約束條件的解要差，通過本發明方法能高效的求解約束優化問題。

技術領域

本發明涉及量子計算技術領域，具體涉及一種求解約束優化問題的量子近似算法。

背景技術

當傳統計算模式趨近瓶頸時，下一代計算模式的重大變革也即將到來。“在不久的將來，量子計算可以改變世界”已經成為了共識。量子計算作為一種新興的計算范式，有望解決在組合優化、量子化學、信息安全、人工智能領域中經典計算機難以解決的技術難題。目前量子計算硬件與軟件都在持續高速發展，不過未來幾年預計仍無法達到通用量子計算的標準。因此短期內如何利用量子硬件解決實際問題成為了當前量子計算領域的一個研究熱點，探索近期量子硬件的應用對理解量子硬件的能力與推進量子計算的實用化進程有著重要意義。

目前的量子計算設備通常被稱為含噪聲的中型量子設備。它們運行在少量的量子位上，并且具有有限的糾錯能力。要在這些設備上展示量子優勢，需要開發可以使用適度量子電路深度運行的算法。在含噪聲的中型量子技術的支持之下，具備50-100個量子比特的量子計算機也許能夠執行超越當前經典數字計算機能力范圍的任務。我們將有機會將其應用于探索更多現有經典計算機無法進行但更具開拓性的研究領域，也意味著人類即將進入一個量子技術發展的關鍵新時代，即含噪聲的中型量子時代。在量子信息和量子計算領域正在發生的是，量子信息是一切自然界行為的通用語言這一點越來越清晰。MIT量子專家Seth Lloyd提出，量子計算更擅長機器學習，能夠發現傳統計算無法發現的數據模式，解決傳統計算機無法解決的難題。隨著量子計算的發展，密碼破解、模擬量子物理系統、模擬材料學、化學和生物學、以及人工智能中的很多問題或許都可迎刃而解。

基于含噪聲的中型量子設備,最常見的算法模型為混合量子-經典算法，旨在借助經典計算機的力量盡可能發揮含噪聲的中型量子計算設備的能力去解決具體的問題。混合量子-經典算法的一部分任務由量子計算設備完成,然后通過經典計算調整量子計算部分的可調參數,反復迭代最后輸出結果。由于采用的電路擬設可以由含噪聲的中型量子設備高效實現,混合量子-經典算法被認為可以基于近期設備發揮量子優勢。混合量子-經典算法在諸多領域有著廣泛應用,其中最具有代表性的包括求解組合優化問題的量子近似優化算法與求解基態能量問題的變分量子本征求解器。

量子近似優化算法由MIT的物理學教授Farhi提出，最早針對圖論中無約束的Max-Cut問題，嘗試給出了超越經典近似算法的近似解。它的算法框架中包括量子和經典兩大部分，其中量子部分實質是參數化的量子門線路對量子絕熱演化的模擬，經典部分則用于尋找控制量子線路演化的最優參數。這種經典+量子的混合算法是當前在含噪聲的中型量子設備上進行算法設計的一個主要思路。Max-Cut是無約束的優化問題，現實中眾多的應用問題都是有約束的問題，如何在量子近似優化算法框架內高效的處理約束，是量子近似優化算法最終能否成功(部署在商用環境中)必須要解決的一個關鍵問題，為此，提出一種求解約束優化問題的量子近似算法。

發明內容

本發明所要解決的技術問題在于：如何解決在經典的量子近似優化算法在處理帶約束的優化問題時，在整個空間(包括可行解和不可行解)中搜索最優解，搜索所需的迭代步數較多，且準確性不高的問題，提供了一種求解約束優化問題的量子近似算法。

本發明是通過以下技術方案解決上述技術問題的，本發明包括以下步驟：

S1：對選取的帶約束的優化問題進行貪心算法求解，獲得近似最優解A；