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

在審

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

1.一種求解約束優化問題的量子近似算法，其特征在于，包括以下步驟：

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

S2：將近似最優解A作為一個新的約束條件重新設計編碼可行解演化空間，縮小可行解演化空間，并將可行解演化空間制備成均勻疊加態|s，均勻疊加態|s為演化的初始量子態；

S3：在目標函數中添加懲罰項，使得不符合約束條件的解的期望值比符合約束條件的解的期望值要差，使得約束優化問題變為無約束優化問題；

S4：將初始量子態帶入量子近似優化算法框架中進行演化，最終得到的哈密頓量的基態，對其測量后，即得到期望值；通過判斷若期望值比集合A的長度|A|差，則近似最優解A即是問題的最優解，若期望值比集合A的長度|A|好或者等于|A|，則再帶入量子近似優化算法框架中進行演化，循環直到期望值比集合A的長度|A|差，即可得到問題的最優解。

2.根據權利要求1所述的一種求解約束優化問題的量子近似算法，其特征在于：在所述步驟S1和S2中，當選取的約束優化問題為求解最大優化問題時，則確定了漢明權重k＝|A|+1的所有可能狀態，比特串長度＝|V|的所有可能組合中1的個數＝k的均勻疊加態。

3.根據權利要求1所述的一種求解約束優化問題的量子近似算法，其特征在于：在所述步驟S1和S2中，當選取的約束優化問題為求解最小優化問題時，則確定了漢明權重k＝|A|-1的所有可能狀態，比特串長度＝|V|的所有可能組合中1的個數＝k的均勻疊加態。

4.根據權利要求1所述的一種求解約束優化問題的量子近似算法，其特征在于：在所述步驟S3中，在哈密頓量中通過添加懲罰項將約束優化問題轉化為無約束優化問題，即當有解違反約束時，在哈密頓量中添加懲罰項，使不滿足約束條件的解的期望值比滿足約束條件的解要差。

5.根據權利要求1所述的一種求解約束優化問題的量子近似算法，其特征在于：在所述步驟S4中，在量子近似優化算法框架中進行演化時，初始時處于哈密頓量的基態，經過演化后，處于哈密頓量的基態，得到哈密頓量的基態，通過測量得到期望值，再對期望值做出比較。

6.根據權利要求5所述的一種求解約束優化問題的量子近似算法，其特征在于：在所述步驟S4中，為混合哈密爾頓量，對應絕熱演化中的初始哈密爾頓量，誘導出帶參酉算子為問題哈密爾頓量，對應絕熱演化中的終止哈密爾頓量，誘導出帶參酉算子經過p步迭代，調節每一步演化時β和γ的取值,最終收斂到問題哈密頓量的某個基態，該基態對應問題的解，演化過程表示為如下的參數化酉變換：

其中，β_i,γ_i∈[-π,π]，是待優化的參數，p是迭代次數。

7.根據權利要求6所述的一種求解約束優化問題的量子近似算法，其特征在于：利用優化器優化參數通過對量子態進行測量，得到在上的期望值：

其中，期望值即是約束優化問題的最優解。

8.根據權利要求1或7所述的一種求解約束優化問題的量子近似算法，其特征在于：針對帶約束的優化問題，若期望值比|A|要差，即求解最大優化問題時得到的期望值比近似最優解A的長度要小或求解最小優化問題時得到的期望值比近似最優解A的長度要大，則求得的近似最優解A即為約束優化問題的最優解；若期望值比|A|要好或者和|A|結果一樣，即求解最大優化問題時得到的期望值比近似最優解A的長度要大或者和近似最優解A的長度一樣或求解最小優化問題時得到的期望值比近似最優解A的長度要小或者和近似最優解A的長度一樣，則在求解最大優化問題時，繼續將漢明權重k加1得到新的可行解演化空間，求解最小優化問題時，繼續在漢明權重k減1得到新的可行解演化空間，再帶入到量子近似優化算法框架中進行演化，直到求出的期望值優于近似最優解，即可得到問題的最優解。