基于量子算法優(yōu)化的迭代多用戶接收機(jī)研究

梁文橋， 周小林

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

基于量子算法優(yōu)化的迭代多用戶接收機(jī)研究

梁文橋， 周小林

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

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

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

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

1 研究?jī)?nèi)容

1.1 量子計(jì)算和量子搜尋算法

和傳統(tǒng)的電子比特不同，通常在一個(gè)量子系統(tǒng)中都含有多個(gè)量子比特。

對(duì)于n量子比特的系統(tǒng)，其某一個(gè)狀態(tài)表示為式(1)。

(1)

通過(guò)這種方式，我們可以把量子計(jì)算的過(guò)程用一系列矩陣計(jì)算表示。通常一個(gè)量子算法，可以表示為多個(gè)量子邏輯門(mén)的順序集合，可以把一個(gè)量子態(tài)輸入通過(guò)計(jì)算，轉(zhuǎn)換為一個(gè)量子態(tài)的輸出，通過(guò)觀測(cè)來(lái)獲得結(jié)果。Grover算法主要用來(lái)解決這樣的問(wèn)題[4]。

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

圖1 Grover搜索基本門(mén)電路

(2)

圖2 Grover搜索態(tài)的變化過(guò)程

(3)

1.2 量子多用戶接收機(jī)

IDMA框圖，如圖4所示。

IDMA發(fā)送端有K個(gè)用戶，每個(gè)用戶的發(fā)射機(jī)中交織器是唯一的，通過(guò)交織器{πk}交織后，通過(guò)調(diào)制器編碼，發(fā)射數(shù)據(jù)比特流。用戶數(shù)據(jù)在自由空間信道到達(dá)接收端，經(jīng)過(guò)了信道矩陣H被接收端接收。矩陣根據(jù)不同的信道情況，給出合適的模型。在接收端，通過(guò)并行的迭代檢測(cè)算法實(shí)現(xiàn)多用戶信息的檢測(cè)和解調(diào)，主要包括三大模塊，ESE，交織器，解交織器，DEC。ESE模塊會(huì)實(shí)現(xiàn)多用戶檢測(cè)和用于信息的軟解，DEC用于軟信息的解碼。

圖3 Grover搜索得到各搜索態(tài)的概率

圖4 K個(gè)多用戶的IDMA框架

輸入序列為{x0,x1,…,xK-1} ，經(jīng)過(guò)相互獨(dú)立信道矩陣{h0,…,hK-1} ，接收端{(lán)y0,…,yK-1} ，接收序列為：y=Hx。經(jīng)典的多用戶檢測(cè)器接收軟入軟出，計(jì)算了每用戶每符號(hào)的似然值，對(duì)于一個(gè)K個(gè)用戶的M階調(diào)制的系統(tǒng)，接收信號(hào)后驗(yàn)信息比特似然值，為式(4)。

(4)

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

(5)

P(y|x)為系統(tǒng)的代價(jià)函數(shù)，代表收到符號(hào)y，發(fā)送的符號(hào)是x的概率。這個(gè)概率通常和信道模型有關(guān)，空間光中常見(jiàn)的散彈噪聲信道，其代價(jià)函數(shù)為式(6)，其中nb為背景光子噪聲

(6)

如果每符號(hào)的各個(gè)比特?cái)?shù)都是相互獨(dú)立的，那么我們可以得到符號(hào)x的先驗(yàn)概率和符號(hào)的外信息，為式(7)—(9)。

(7)

(8)

(9)

有了這些概率值，我們可以用于OIDMA的迭代譯碼結(jié)構(gòu)中。可以看出對(duì)公式(5)的求解是OIDMA迭代結(jié)構(gòu)中的關(guān)鍵部分所在和主要的復(fù)雜度所在。我們接著對(duì)Grover搜尋算法進(jìn)行改進(jìn)用來(lái)求解系統(tǒng)的后驗(yàn)概率。在實(shí)踐中知道Grover搜尋只是理想的搜尋方法，在實(shí)際中我們并不知道偏轉(zhuǎn)Lopt的次數(shù)，可能出現(xiàn)操作數(shù)過(guò)多的問(wèn)題，我們需要用到BBHT算法去隨機(jī)去取操作次數(shù)，BBHT算法[5]，如表1所示。

表1 BBHT量子搜尋算法流程

BBHT采用隨機(jī)取值，同時(shí)擴(kuò)展解集的方法確定操作次數(shù)。

同時(shí)對(duì)Oracle門(mén)修改，有用于搜尋解集的最小值的算法DHA算法[6]。我們要采用DHA算法來(lái)求解多用戶問(wèn)題中的式(5)，如表2所示。

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

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

表3 求解多用戶問(wèn)題的量子算法

2 仿真和分析

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

(12)

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

圖5 6用戶下各個(gè)算法的性能

3 總結(jié)

本文利用量子計(jì)算實(shí)現(xiàn)了空間光交織多址多用戶檢測(cè)

圖6 算法復(fù)雜度

的算法，給出了一種對(duì)于未來(lái)高速增長(zhǎng)的多用戶問(wèn)題的優(yōu)化算法，這種優(yōu)化解法可以把原有的多用戶多址問(wèn)題復(fù)雜度減少到開(kāi)方級(jí)，是一種未來(lái)大數(shù)據(jù)時(shí)代具有前瞻性的算法。

[1] 王慶楊，張青，韋崗. CDMA移動(dòng)通信系統(tǒng)中的多用戶

檢測(cè)技術(shù)[J]. 移動(dòng)通信,2000(4):40-45.

[2] 王書(shū)浩，龍桂魯.大數(shù)據(jù)與量子計(jì)算[J]，科學(xué)通報(bào)，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

國(guó)家自然科學(xué)基金(61571135)

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

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

TP311

A

2016.10.12)