論文精讀：大規模MIMO波束選擇問題的量子計算解決方案

概要： 隨著大規模多輸入多輸出系統（MIMO）在5G及未來通信技術中的應用，波束選擇問題（MBS）成為提升系統性能的關鍵。傳統的波束選擇方法面臨計算復雜度高和計算資源不足的問題。本文提出了一種基于量子計算的解決方案，利用相干伊辛機（CIM）求解MIMO波束選擇問題。通過將波束選擇問題轉化為QUBO模型，并映射到CIM物理設備，本文展示了量子計算在處理大規模組合優化問題中的潛力。
實驗結果表明，CIM在精度和計算速度方面均顯著優于如模擬退火、禁忌搜索等傳統算法，，其計算速度提高了261.23倍和20.6倍。本文的研究為量子計算在通信領域中波束選擇和稀疏優化問題的求解提供了一個實用的解決方案，展示了量子硬件在優化問題中的巨大潛力。

1. 文章背景

隨著5G通信系統的不斷發展，大規模MIMO（Massive MIMO） 技術作為一種革命性的無線傳輸技術，正在成為提升網絡吞吐量和信號質量的關鍵技術。通過使用大量天線并利用波束賦形（beamforming），大規模MIMO可以同時提供多個數據流，從而顯著提升數據傳輸速率和信號質量，進而改善蜂窩網絡的覆蓋范圍和容量。然而，隨著天線數量的增多，RF鏈路的數量也隨之增加，導致硬件成本和功耗大幅上升。

為了解決這一問題，文章提出了波束選擇（MIMO Beam Selection, MBS） 方法，通過在波束空間（beamspace）中進行波束選擇，可以在不明顯影響系統性能的情況下顯著減少RF鏈路的數量，從而降低硬件成本和功耗。波束選擇的核心任務是從所有可能的波束中選擇一組波束，最大化網絡的整體性能。然而，波束選擇問題本質上是一個組合優化問題，尤其在5G系統中，存在大量的單元和天線組合，尋找最佳解非常困難。盡管有很多優化方法，如貪婪算法（Greedy Algorithm）、分支限界法（Branch-and-Bound）、模擬退火（Simulated Annealing, SA）等，但這些經典算法在處理大規模問題時常常面臨計算成本過高、難以保證全局最優等問題。

量子計算被認為有潛力通過并行計算為大規模組合優化問題提供更快、更高效的解決方案。作者將波束選擇問題轉化為QUBO（Quadratic Unconstrained Binary Optimization） 模型，并利用CIM求解該模型，具體包括：

1. 提出有效的MBS求解方法：本文通過構建數學模型來解決MBS問題，該模型能有效利用大規模MIMO系統的性能潛力。與傳統方法相比，所提出的模型不僅簡潔優雅，而且能夠顯著降低QUBO模型所需的比特數，同時確保生成的解是最優的。
2. CIM實驗驗證：為了驗證CIM在實際環境中的性能，文章通過在物理CIM系統上進行實驗，展示了CIM能夠在毫秒級的時間內生成最優解，體現了CIM在求解現實環境中的優化問題時的高效性和有效性。

相比經典算法，CIM通過并行化處理能力能夠在較短的時間內尋找最優解，并且效率和求解質量上均顯著優于經典的啟發式算法。

2. MIMO波束選擇問題

2.1 問題描述

在大規模MIMO系統中，波束選擇問題（MBS） 的核心任務是通過選擇最佳的波束集合來優化信號質量，從而提升網絡的整體性能。MBS問題的目標是從多個小區中選擇一定數量的波束，確保覆蓋區域內的多個網格滿足特定的信號強度要求。

圖1 MBS問題的示意圖

如圖1所示，目標覆蓋區域被劃分為多個網格(grids)。每個網格代表一個小的地理區域，由一個或多個小區（即基站, cell）進行覆蓋。每個小區發射多個MIMO波束(beams)，這些波束指的是由天線陣列發射的信號，通常每個波束代表一個特定方向的信號傳輸。

在MBS問題中，我們的任務是從每個小區的波束集合中選擇若干個波束，以最大化滿足特定約束條件的網格數量。一個網格被認為是“合格的”，如果該網格的最大接收信號強度（RSS） 超過設定的閾值，并且該最大RSS與第二大RSS之間的差值超過預設的值。那么，波束選擇問題的優化目標就可以表述為：通過選擇適當的波束組合，使得盡可能多的網格能夠滿足上述條件，即保證網格內的最大信號強度達到要求，同時避免不同波束之間的干擾。通過選擇合適的波束，可以減少硬件消耗和功率消耗，同時提升網絡的覆蓋和容量。

主要變量設定如下：

• $n$ 為波束的數量
• $m$ 為網格的數量
• $v$ 為小區的數量，${\mathcal{V}}_i$ 為與第 $i$ 個網格相關的小區集合
• $s_{ijk}$ 為第 $i$ 個網格、第 $j$ 個小區、第 $k$ 個波束的RSS值

2.2 識別最大RSS ($c_{ij}$) 和 第二大RSS ($b_i$)

首先，定義最大接收信號強度（RSS），即在網格$i$和小區$j$中，所有波束的最大RSS值。這個最大值是由所有波束信號的強度決定的。公式如下：
$$M=\underset{1\le i\le m,j\in {\mathcal{V}}_i,1\le k\le n}{\max }{s}_{ijk}$$
接下來，決策變量為 $x_{jk}$，表示在第 $j$ 個小區是否選擇第 $k$ 個波束：
$$x_{jk}=\{\begin{array}{ll}1,& \text{如果第?j?個小區選擇了第?k?個波束}\\ 0,& \text{否則}\end{array}$$
對于網格$i$和小區$j$的最大RSS（記作$c_{ij}$），它由所選擇的波束來決定。選擇的波束的接收信號強度$s_{ijk}$與決策變量$x_{jk}$的乘積表示該波束的貢獻。最終的最大RSS值$c_{ij}$就是所有波束中最大值的結果，即：
$$c_{ij}=\underset{1\le k\le n}{\max }{s}_{ijk}{x}_{jk}$$
對于網格$i$、小區$j$的最大RSS值$c_{ij}$，可以使用以下約束來確保其正確性：
$$\begin{array}{rlr}& c_{ij}\ge s_{ijk}{x}_{jk},& ?j\in {\mathcal{V}}_i,1\le k\le n\\ & c_{ij}\le s_{ijk}{x}_{jk}+(1?d_{ijk})M,& ?1\le k\le n\\ & \sum _{k=1}^n{d}_{ijk}=1,& ?j\in {\mathcal{V}}_i\end{array}$$
第一個約束確保$c_{ij}$至少等于所有波束信號強度$s_{ijk}$與決策變量$x_{jk}$的乘積中的最大值。也就是說，$c_{ij}$必須大于等于任何波束的貢獻。第二個約束確保$c_{ij}$的值不會超過波束貢獻的最大值加上一項由$d_{ijk}$決定的懲罰項。當$d_{ijk}=1$時，表示該波束被選擇，從而確保最大RSS值$c_{ij}$被正確地選定。若$d_{ijk}=0$，則該波束不影響最大RSS以此確保$c_{ij}$是正確的最大RSS值。第三個約束確保對于每個網格$i$和小區$j$，僅有一個波束會影響最大RSS值，因此對每個$d_{ijk}$進行求和，確保只有一個波束的$d_{ijk}$等于 1。

最大RSS值$a_i$是網格$i$中所有小區的最大RSS值：

$$a_i=\underset{j\in {\mathcal{V}}_i}{\max }{c}_{ij}$$

第二大RSS值$b_i$是網格$i$中所有小區的第二大RSS值，引入以下約束：
b i ≥ c i j ? p i j M , ? j ∈ V i b i ≤ c i j + ( 1 ? q i j ) M , ? j ∈ V i ∑ j ∈ V i q i j = 2 , q i j ∈ { 0 , 1 } \begin{aligned} &b_i \geq c_{ij} - p_{ij} M, \quad &\forall j \in \mathcal{V}_i \\ &b_i \leq c_{ij} + (1 - q_{ij}) M, \quad &\forall j \in \mathcal{V}_i \\ &\sum_{j \in \mathcal{V}_i} q_{ij} = 2, \quad &q_{ij} \in \{0, 1\} \end{aligned} ?bi?≥cij??pij?M,bi?≤cij?+(1?qij?)M,j∈Vi?∑?qij?=2,??j∈Vi??j∈Vi?qij?∈{0,1}?
第一個約束確保第二大RSS值$b_i$不小于$c_{ij}$減去$p_{ij}$的懲罰項，這里的$p_{ij}$表示是否為最大RSS的值。如果$p_{ij}=1$，則$b_i$應該是第二大RSS。第二個約束確保$b_i$不大于$c_{ij}$加上一項由$q_{ij}$控制的懲罰項，$q_{ij}$控制是否為第二大RSS。第三個約束確保在網格$i$中有兩個小區對應最大RSS和第二大RSS的選擇，意味著$q_{ij}$的總和為2。

接下來，定義變量$z_i$來表示網格$i$是否滿足以下兩個條件：

1. 最大RSS大于或等于閾值${\delta }_1$，即$a_i\ge {\delta }_1$。
2. 最大RSS與第二大RSS之間的差值大于或等于閾值${\delta }_2$，即$a_i?b_i\ge {\delta }_2$。

2.3 構建優化問題

識別出最大和第二大的波束之后，回到MBS要解決的核心問題。MBS的最終目標是最大化網格$i$滿足上述條件的數量，即最大化所有網格的$z_i$之和，即：
$$\max \sum _{i=1}^m{z}_i$$
相應的約束條件為：
$$\begin{array}{rl}& {\delta }_1?a_i\le M(1?z_i)\\ & {\delta }_2?(a_i?b_i)\le M(1?z_i)\end{array}$$
以此確保當網格不滿足條件時，$z_i$被強制設置為0，否則$z_i$為1。最后，選擇的波束數目不能超過預定義的上限：
$$\sum _{k=1}^n{x}_{jk}\le r,?1\le j\le v$$
由于波束選擇問題是一個組合優化問題，且變量數量隨著天線和小區的增加呈指數增長，因此，MBS問題是NP-hard的。

2.4 原優化問題轉化為QUBO/Ising

為了解決包含約束的不等式問題，本文引入了松弛變量，將約束條件轉化為等式，從而使得原問題可以表示為無約束的最小化問題。每個松弛變量可以表示為一個二進制展開的形式，定義為：
$$\text{slack}=\sum _{t=0}^{?}{2}^t?{\text{slack}}_t\text{\hspace{1em}(13)}$$
其中，${\text{slack}}_t$取值為0或1，$?$與松弛變量的范圍有關。這里，$?=?{\log }_{2}M?$，因為所有的松弛變量都不超過$M$。通過引入這些松弛變量，原來的約束最大化問題被轉化為了無約束最小化問題。最優解與原始約束最大化問題的最優解是相同的。

進一步，為求解無約束問題，文章使用了罰函數法，將約束違反程度的平方作為罰項加到目標函數中，從而轉化為一個無約束的優化問題。具體的罰函數為：
$$\text{Penalty}=\lambda ?\sum _{\text{violations}}(\text{violation}{)}^2$$
其中，$\lambda$是控制罰項強度的參數，確保約束的違反程度最小。為了轉換為QUBO模型，文章表示變量$a_i$、$b_i$和$c_{ij}$為整數變量，并使用二進制表示法表示它們：
$$a_i=\sum _{t=1}^{?}{2}^t?a_{it},b_i=\sum _{t=1}^{?}{2}^t?b_{it},c_{ij}=\sum _{t=1}^{?}{2}^t?c_{ijt}$$
此時，問題已經轉化為QUBO形式$\min f_Q(x)=\min x^{T}Qx$。其中，$Q\in {\mathbb{R}}^{n\times n}$是一個實值上三角矩陣， f Q : { 0 , 1 } n → R f_Q : \{0, 1\}^n \to \mathbb{R} fQ?:{0,1}n→R是一個二進制向量到實數的映射。

利用量子計算中的相干伊辛機（CIM），我們可以通過伊辛模型，以及調節參數來求解QUBO問題。伊辛模型與QUBO問題有著密切的關系。在伊辛模型中，系統的哈密頓量函數（Hamiltonian）表示為：
$$H(\sigma )=?\sum _{i,j}{J}_{ij}{\sigma }_i{\sigma }_j?\sum _i{h}_i{\sigma }_i$$
其中，${\sigma }_i$是取值為$?1$或$+1$的自旋變量，$J_{ij}$和$h_i$分別是二次和線性系數。通過替換${\sigma }_i\to 2x_i?1$，可以得到等效的QUBO問題。CIM利用可調的量子相變過程，從而在物理層面上實現優化，最終得到問題的最優解。

3. 簡化模型與后處理

為了減少QUBO模型中比特的數量，文章提出了一種簡化模型，僅考慮最大RSS值大于或等于閾值${\delta }_1$的約束條件，即$a_i\ge {\delta }_1$。與原始模型相比，簡化模型簡化了約束條件，目的是減少QUBO模型中的比特數，并降低計算復雜度。為了評估模型的有效性，文章利用CIM（相干伊辛機）返回的最佳100個解，從中選出符合原始模型約束的最佳可行解。在簡化模型中，我們定義了一個新的RSS標記變量 ${\bar{s}}_{ijk}$，當 $s_{ijk}\ge {\delta }_1$ 時，${\bar{s}}_{ijk}=1$，否則 ${\bar{s}}_{ijk}=0$。簡化模型可以通過以下形式來表示：
$$\max \sum _{i=1}^m{z}_i\text{\hspace{1em}(14)}$$
其中$z_i$表示網格$i$是否滿足要求。約束條件為：
$$\begin{array}{rlr}& z_i\le \sum _{j\in {\mathcal{V}}_i}\sum _{k=1}^n{x}_{jks}{\bar{s}}_{ijk},& ?1\le i\le m\\ & \sum _{k=1}^n{x}_{jk}\le r,& ?1\le j\le v\end{array}$$
其中第一個約束確保了$z_i=1$當且僅當網格$i$滿足最大RSS大于或等于閾值${\delta }_1$。當所有$x_{jks}{\bar{s}}_{ijk}=0$時，表示沒有選擇滿足閾值的RSS，$z_i$必須為0；如果存在某些$j$和$k$使得$x_{jks}{\bar{s}}_{ijk}=1$，則$z_i$為1。

接下來，我們將簡化模型的目標函數轉化為QUBO形式，方法是將上面兩個約束引入松弛變量。簡化模型的優化問題如下所示：
$$\begin{array}{rl}\min ?\sum _{i=1}^m{z}_i& +\lambda ?\sum _{i=1}^m{\left(z_i+{\text{slack}}_{1,i}?\sum _{j\in {\mathcal{V}}_i}\sum _{k=1}^n{x}_{jks}{\bar{s}}_{ijk}\right)}^2\\ & +\lambda ?\sum _{j=1}^v{\left(\sum _{k=1}^n{x}_{jk}+{\text{slack}}_{2,j}?r\right)}^2\end{array}$$
這里，${\text{slack}}_{1,i}$和${\text{slack}}_{2,j}$是松弛變量，用于解決約束條件中的不等式，QUBO問題的規模被縮減，同時仍然保持了原始問題的解的最優性。這個簡化模型相比于原始模型減少了比特數，使得QUBO模型的求解更加高效。該簡化模型的變量數量為$m+nv+m??{\log }_2(nv)?+v??{\log }_{2}r?$，相較于原始模型，這種簡化顯著降低了計算復雜度，尤其是在大規模網絡情況下具有明顯優勢。

4. 實驗結果

在這一部分中，作者通過一系列實驗評估了CIM在MIMO波束選擇問題（MBS）中的可行性，重點比較了CIM物理機、模擬退火（SA）算法和禁忌搜索（Tabu Search）算法的性能。實驗數據來自中國吉安市，通過測量4857個網格、217個小區和148個波束的信號強度，包含了1048575條數據記錄。

實驗假設波束數和小區數固定為5，而網格大小從5到10不等。所有六種設置的比特數都小于100，并選擇這些設置來研究CIM物理機在不同網格大小下的性能，同時控制其他變量，進而轉換成了一個著名的NP難問題——最大割（Max-Cut）問題。根據已知理論，伊辛模型在沒有外加磁場的情況下找到最低能量態的問題可以重新表述為最大割問題。

圖2 求解割值的演化過程

圖2繪制了CIM在計算過程中得到的割值隨時間變化的曲線。數據點顯示了在CIM的中間階段評估的割值。每兩個數據點之間的時間間隔為2.11微秒。事實上，光纖環路中有211個振蕩脈沖，脈沖之間的時間間隔為10納秒，因此，光脈沖在環路中的傳輸時間為2.11微秒。從圖中可以看出，隨著時間的推移，割值逐漸增加，隨著泵浦光功率逐漸增加并達到臨界閾值，發生了相變。作者期望在最低能量附近找到最優解，圖3中的紅點標示了找到的最優解。在六種不同的設置中，CIM物理機分別進行了1940、361、1084、1057、1276和1377次循環，以找到最優解。相應的運行時間分別為4.096毫秒、0.764毫秒、2.289毫秒、2.232毫秒、2.694毫秒和2.908毫秒。

圖3 CIM 物理機在m = 5時得到的結果

圖3展示了CIM物理機在5個網格下的解。圖中，藍色節點代表自旋值為 +1，綠色節點代表自旋值為 -1。我們可以觀察到，圖中節點之間有許多連接邊，幾乎是全連接的，表明MBS問題具有高度復雜性。

表格I展示了CIM物理機與模擬退火（SA）算法和禁忌搜索（Tabu Search）算法的綜合性能比較。在目標值方面，CIM物理機在所有案例中都取得了最好的目標函數值。對于每種算法，作者還進行了一百次重復實驗，計算了找到可行解的平均時間，以及對應可行解的目標函數值。

表格I：CIM物理機、SA和Tabu Search在目標值和運行時間上的比較

網格數量	比特數量	CIM物理機時間	CIM目標值	哈密頓值	SA時間	SA目標值	Tabu時間	Tabu目標值
m = 5	61	4.096ms	-1636500253	-1636753751.5	134ms	2.07	13.7ms	1.8
m = 6	68	0.764ms	-1961998250	-1962503752	147ms	1.55	14.3ms	2.6
m = 7	75	2.289ms	-2286992748	-2288253752.5	131ms	1.87	17.3ms	2.94
m = 8	82	2.232ms	-2619998246	-2621753753	133ms	2.28	16.7ms	3.15
m = 9	89	2.694ms	-2899621246	-2963128752.5	139ms	2	20.2ms	3.04
m = 10	96	2.908ms	-3310865745	-3312378751	146ms	2.12	22ms	2.7

表格I顯示了六種不同設置下，CIM物理機、SA和Tabu算法在運行時間和目標值方面的性能對比。可以看到，CIM在所有場景中都實現了最優的目標值，并且在計算時間上明顯優于經典算法。為了評估CIM的性能，文章定義了效率比，即：
$${\gamma }_{\text{CIM,sa/tabu}}=\frac{f_{\text{CIM}}/t_{\text{CIM}}}{f_{\text{sa/tabu}}/t_{\text{sa/tabu}}}\text{\hspace{1em}(18)}$$
效率比由兩個部分組成：節省的時間和提高的精度。節省時間衡量了使用CIM相比傳統方法節省的時間量，精度提高衡量了算法輸出與正確解匹配的程度。較大的效率比意味著CIM的表現更好。從圖4中可以看出，CIM相較于Tabu和SA，效率比提高了數十倍到數百倍。具體來說，CIM與Tabu的平均效率比為261.23，與SA的平均效率比為20.66。

圖4 效率比隨比特數的變化

5. 總結

本文提出了一種基于QUBO模型的新方法來解決MIMO波束選擇問題（MBS），這一問題是5G系統中的關鍵問題之一。除了精心設計的模型，本文的貢獻還包括成功應用CIM模擬器和物理機來求解MBS問題。實驗結果表明，CIM求解器在準確性和速度方面超越了經典啟發式算法，提供了數十到數百倍的性能提升。作者認為，所提出的解決方案在實際5G網絡運營中具有巨大的潛力。

論文鏈接：

[1]ArXiv Version

[2]IEEE Published Version

[3]此外歡迎點擊鏈接，在開物量子開發者社區閱讀原文：