基于量子算法優化的迭代多用戶接收機研究

梁文橋， 周小林

(復旦大學 信息科學與工程學院通信系， 上海 200433)

基于量子算法優化的迭代多用戶接收機研究

梁文橋， 周小林

(復旦大學 信息科學與工程學院通信系， 上海 200433)

量子計算是21世紀熱點研究的方向。在傳統經典通信框架中，最優的多用戶接收機(最大似然多用戶接收機)通常由于其算法的高復雜性導致很難用在大量多用戶的場景中。分析了量子計算中常用的算法，提出利用Grover搜索算法的并行性來優化多用戶接收機的復雜度。經過分析，研究的搜索算法可以把復雜度降到原有算法的開方級。把提出的改進算法用于自由空間光IDMA的通信系統中，提出了一種利用量子計算的軟入軟出(SISO)量子多用戶接收機，并且和傳統空間光IDMA散彈噪聲下的性能做了對比。數值仿真的結果顯示，所提出的量子計算方法優于次優軟干擾消除算法，和最優貝葉斯算法性能一致，并且復雜度顯著降低，僅為最優貝葉斯算法復雜度的開方級。

多用戶接收機； 量子計算； Grover搜尋算法； 空間光交織多址通信

在無線通信系統中，各個用戶信號通過復雜多變的無線信道后存在一定的相互影響，這就是系統存在的多址干擾(MAI)的來源。MAI通常會成為通信多用戶系統中的一個主要干擾源。最優多用戶檢測方法采用最大似然序列檢測(MLSD)，可以逼近單用戶的接收性能。但是，其復雜度通常是用戶數的指數冪，當用戶數增多時，由于復雜度太高給實際工業實現帶來巨大困難[1]。我們知道由于量子系統的獨特性質，量子計算具有經典計算不具備的超并行計算能力，能夠對某些重要的經典算法進行加速，比如大數分解的算法[2]。利用量子計算的并行性來優化多用戶檢測是一種有效的發展方向。在理論研究上，量子計算已經有一些成熟的算法，比如Shor算法求解整數分解問題，Simon算法求解黑盒問題，量子相位檢測算法用于求解一個量子態的特征相位值，Grover搜尋算法用于搜尋在一定集合里的特定數據等。實驗上，量子搜索算法在一些小規模的量子產品中已經得到演示，比如D-Wave公司出品的超導計算裝置用于數據搜索中[3]。在本文中，首先分析了量子搜尋算法，并把這種算法用于多用戶問題求解；同時設計了改進算法，應用到光交織分多址OIDMA通信系統中。數值仿真顯示，本文所提出算法和最優的多用戶檢測算法性能一致，且復雜度顯著降低。

1 研究內容

1.1 量子計算和量子搜尋算法

和傳統的電子比特不同，通常在一個量子系統中都含有多個量子比特。

對于n量子比特的系統，其某一個狀態表示為式(1)。

(1)

通過這種方式，我們可以把量子計算的過程用一系列矩陣計算表示。通常一個量子算法，可以表示為多個量子邏輯門的順序集合，可以把一個量子態輸入通過計算，轉換為一個量子態的輸出，通過觀測來獲得結果。Grover算法主要用來解決這樣的問題[4]。

對于一個映射f:{x0,x1,…,xn}→{f(x0),f(x1),…,f(xn)}，在索引 {x0,x1,…,xn} 中，找到讓f(xδ)=δ的特定的x值。Grover搜尋算法的基本門電路，如圖1所示。

圖1 Grover搜索基本門電路

(2)

圖2 Grover搜索態的變化過程

(3)

1.2 量子多用戶接收機

IDMA框圖，如圖4所示。

IDMA發送端有K個用戶，每個用戶的發射機中交織器是唯一的，通過交織器{πk}交織后，通過調制器編碼，發射數據比特流。用戶數據在自由空間信道到達接收端，經過了信道矩陣H被接收端接收。矩陣根據不同的信道情況，給出合適的模型。在接收端，通過并行的迭代檢測算法實現多用戶信息的檢測和解調，主要包括三大模塊，ESE，交織器，解交織器，DEC。ESE模塊會實現多用戶檢測和用于信息的軟解，DEC用于軟信息的解碼。

圖3 Grover搜索得到各搜索態的概率

圖4 K個多用戶的IDMA框架

輸入序列為{x0,x1,…,xK-1} ，經過相互獨立信道矩陣{h0,…,hK-1} ，接收端{y0,…,yK-1} ，接收序列為：y=Hx。經典的多用戶檢測器接收軟入軟出，計算了每用戶每符號的似然值，對于一個K個用戶的M階調制的系統，接收信號后驗信息比特似然值，為式(4)。

(4)

P(x)是x的先驗概率，χ(k,m,0) 代表的是，第k個用戶,m位為0的所有取值情形的集合。我們多用戶檢測中采用了最大似然準則，把后驗概率似然值簡化為式(5)。

(5)

P(y|x)為系統的代價函數，代表收到符號y，發送的符號是x的概率。這個概率通常和信道模型有關，空間光中常見的散彈噪聲信道，其代價函數為式(6)，其中nb為背景光子噪聲

(6)

如果每符號的各個比特數都是相互獨立的，那么我們可以得到符號x的先驗概率和符號的外信息，為式(7)—(9)。

(7)

(8)

(9)

有了這些概率值，我們可以用于OIDMA的迭代譯碼結構中?？梢钥闯鰧?5)的求解是OIDMA迭代結構中的關鍵部分所在和主要的復雜度所在。我們接著對Grover搜尋算法進行改進用來求解系統的后驗概率。在實踐中知道Grover搜尋只是理想的搜尋方法，在實際中我們并不知道偏轉Lopt的次數，可能出現操作數過多的問題，我們需要用到BBHT算法去隨機去取操作次數，BBHT算法[5]，如表1所示。

表1 BBHT量子搜尋算法流程

BBHT采用隨機取值，同時擴展解集的方法確定操作次數。

同時對Oracle門修改，有用于搜尋解集的最小值的算法DHA算法[6]。我們要采用DHA算法來求解多用戶問題中的式(5)，如表2所示。

表2 DHA量子搜尋最小值算法流程

利用DHA做輔助，我們求解多用戶問題的算法，如表3所示。

表3 求解多用戶問題的量子算法

2 仿真和分析

在通信框架中，在卷積碼率為5的情況下采用OOK調制，對比量子算法和軟干擾消除算法以及最優貝葉斯算法下性能，如圖5所示。從圖5中可以看出，在原理上量子改進算法和最優的多用戶檢測算法是一致的，相比如簡化的軟干擾消除方法，誤碼率降低。對比量子多用戶檢測和最優貝葉斯算法復雜度。對于量子算法，主要復雜度來源于式(7)求解的DHA算法，其復雜度上下限，為式(12)[7]。

(12)

而傳統的復雜度為O(C)=2llog2(MK)+MK。對比復雜度在K>5，大量用戶存在的情況下，迭代次數顯著性降低，利用量子算法優化了原有算法的復雜度，如圖6所示。

圖5 6用戶下各個算法的性能

3 總結

本文利用量子計算實現了空間光交織多址多用戶檢測

圖6 算法復雜度

的算法，給出了一種對于未來高速增長的多用戶問題的優化算法，這種優化解法可以把原有的多用戶多址問題復雜度減少到開方級，是一種未來大數據時代具有前瞻性的算法。

[1] 王慶楊，張青，韋崗. CDMA移動通信系統中的多用戶

檢測技術[J]. 移動通信,2000(4):40-45.

[2] 王書浩，龍桂魯.大數據與量子計算[J]，科學通報，2015(60)：499-508.

[3] Grant A, Quantum computer fails challenge: D-Wave two shows no speed gain over traditional machine[J]. Sci News, 2014(6): 186.

[4] Nielsen M A, Chuang I L. Quantum Computation and Quantum Information[M]. Cambridge:Cambridge University Press,2010.

[5] Boyer M, Brassard G, Hoeyer P, et al. Tight bounds on quantum searching[J]. Fortschritte Der Phys., 1998(4-5)：493-506.

[6] Durr C, Hoeyer P. A Quantum Algorithm for Finding the Minimum[M]. Cambridge: Cambridge Univ. Press, 1996.

[7] Imre S, Balazs F. Performace evaluation of quantum based multi-user detector[C]. In proc. IEEE 7thInt. Symp. Spread Spectr. Tech. Appl. Vol.3 Zurich. Switzerland. sep. 2002, pp：722-725.

Research on Multi-User Detector Based on Quantum Algorithms

Liang Wenqiao,Zhou Xiaolin

(School of Electronic and Information Engineering, Fudan University, Shanghai 200433, China)

Quantum computation is a hot researching spot in the 21 century. In classic communication schemes, the optimal multi-user detection(such as maximum likelihood multiuser detector) often has a high complexity so that can not be applied in the numerous users situation. In this paper, we analyze the common algorithm in Quantum computation firstly, then we apply the Grover searching algorithm to optimize the performance of classical multi-user detector. Through analyzing,the algorithm proposed can achieve a quadratic reduction in the computational complexity. At last we apply the new algorithm to the traditional IDMA(interval-division multiple access), propose a soft-input soft-output multi-user detector based on the Quantum algorithm. We compare it with the traditional IDMA in the Gaussian and Poisson cases. According to the simulation results, the algorithm proposed has performance better than SOIC(soft), equals to the OB(optimal Bayes) algorithm, and it can achieve a quadratic reduction as we analyze before.

Multi-user detector; Quantum computation; Grover searching algorithm; Optical interleaver-division multiple access

國家自然科學基金(61571135)

梁文橋(1992-)，男，天門，碩士研究生，研究方向：無線通信，量子通信 周小林(1978-)，男，上海，副教授，博士，研究方向：無線通信，量子通信

1007-757X(2017)03-0001-03

TP311

A

2016.10.12)