量子Grover算法及其在現(xiàn)代通信中的應(yīng)用.pdf

1、量子信息科學(xué)是一門新興的交叉學(xué)科，它在信息領(lǐng)域中有著獨(dú)特的性能，在提高運(yùn)算速度、確保信息安全、增大信息容量和提高檢測精度等方面可突破現(xiàn)有經(jīng)典信息系統(tǒng)的極限。特別是近年來，基于量子并行計(jì)算的量子算法有效地降低了一些經(jīng)典難解算法的計(jì)算復(fù)雜度。本文研究了基于量子并行計(jì)算的Grover算法在多用戶檢測和網(wǎng)絡(luò)路徑優(yōu)化中的應(yīng)用。 在CDMA多用戶檢測問題中，Verdu已經(jīng)證明最佳檢測算法與二次函數(shù)的最優(yōu)性相關(guān)，并且提出了基于信號估計(jì)的最大似

2、然檢測算法(MLSE)。這是一個(gè)搜索問題，其計(jì)算復(fù)雜度與用戶數(shù)成指數(shù)關(guān)系，這在常規(guī)計(jì)算中是一個(gè)NP難解問題，有效降低最佳檢測算法的計(jì)算復(fù)雜度，是當(dāng)前多用戶檢測的一個(gè)研究熱點(diǎn)。由于Grover算法可以以O(shè)(√N(yùn))的速度有效搜索長為N的未排序數(shù)據(jù)庫搜索問題，結(jié)合多用戶檢測的最大似然檢測算法，本文提出了一種基于量子并行計(jì)算特性和Grover算法的量子最佳檢測方案，分析了該方案下最佳檢測算法的計(jì)算復(fù)雜度。與經(jīng)典最佳檢測算法相比，量子最佳檢測算法

3、的復(fù)雜度下降為O(√2K)，其中K為多用戶通信系統(tǒng)的用戶數(shù)，并且在誤碼率與用戶數(shù)、誤碼率與用戶間相關(guān)系數(shù)和誤碼率與信噪比等性能與經(jīng)典最佳檢測算法基本相同。 最短路徑問題是網(wǎng)絡(luò)路徑優(yōu)化的基本問題之一。目前，尋找連通網(wǎng)絡(luò)的最小生成樹的算法主要是Prim算法和Kruskal算法。然而面對龐大的網(wǎng)絡(luò)體系，它們都存在運(yùn)算復(fù)雜度過高、搜索效率低下的缺陷。本文利用Grover算法構(gòu)造了六個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)最小生成樹，分析了基于Grover算法的最小