集合運(yùn)算的量子算法設(shè)計(jì)及其應(yīng)用.pdf

1、量子計(jì)算與量子信息是涉及物理學(xué)、計(jì)算機(jī)科學(xué)、數(shù)學(xué)以及信息科學(xué)等多個(gè)學(xué)科的新興綜合性交叉研究領(lǐng)域。量子計(jì)算和量子計(jì)算機(jī)的思想最早由著名的物理學(xué)家Feynman提出，它是量子力學(xué)理論和經(jīng)典計(jì)算理論完美結(jié)合的產(chǎn)物。由于其強(qiáng)大的計(jì)算能力及廣闊的應(yīng)用前景，使得其在國(guó)際學(xué)術(shù)界以及政府科研機(jī)構(gòu)中引起巨大的興趣，得到快速發(fā)展。量子信息技術(shù)是量子特性如：量子相干性、非局域性、糾纏性、不可克隆性等在信息科學(xué)領(lǐng)域的應(yīng)用，它能有效突破現(xiàn)有信息技術(shù)面臨的困難，具

2、有很多新的性能。例如：1994年P(guān)eterWShor提出的因子分解算法可以在量子計(jì)算機(jī)上有效求解大數(shù)質(zhì)因子分解問題，而這個(gè)問題對(duì)于經(jīng)典計(jì)算機(jī)卻是非常困難的以至于成為現(xiàn)在廣泛使用的RSA密碼系統(tǒng)的基礎(chǔ)。這直接證明了量子計(jì)算機(jī)具有經(jīng)典計(jì)算機(jī)無(wú)法比擬的計(jì)算優(yōu)勢(shì)。 在量子計(jì)算的研究中，計(jì)算性能的優(yōu)越性主要體現(xiàn)在算法的有效性上。目前為止，被公認(rèn)的最具代表性的量子算法有Shor的大數(shù)質(zhì)因子分解算法以及Grover提出的數(shù)據(jù)庫(kù)搜索量子算法。由

3、于Grover搜索算法只能進(jìn)行簡(jiǎn)單問題搜索，不能完成復(fù)雜的計(jì)算，使得其在實(shí)際應(yīng)用中具有很大的局限性。此外，任何數(shù)據(jù)信息在進(jìn)行處理之前都必須先將其裝載到計(jì)算機(jī)寄存器中，從而進(jìn)一步完成計(jì)算。但是，在經(jīng)典計(jì)算機(jī)中I/O設(shè)備的運(yùn)行速度對(duì)于任意一個(gè)經(jīng)典算法都是一個(gè)效率瓶頸。經(jīng)典的計(jì)算過程是經(jīng)由I/O設(shè)備把數(shù)據(jù)一個(gè)一個(gè)的裝載到寄存器中，再將計(jì)算結(jié)果一個(gè)一個(gè)的輸出。如果是處理海量的數(shù)據(jù)，這種輸入輸出方法的效率是極其低的，但這在經(jīng)典計(jì)算理論中卻又是無(wú)法

4、克服的。 另外，量子計(jì)算機(jī)只能處理量子態(tài)而不能直接處理經(jīng)典數(shù)據(jù)，所以必須有一個(gè)針對(duì)量子計(jì)算機(jī)的數(shù)據(jù)存儲(chǔ)方案。本文將介紹數(shù)據(jù)存儲(chǔ)的量子方案(QLS方案)，它可以有效解決這一效率瓶頸問題。集合運(yùn)算是科學(xué)技術(shù)很多領(lǐng)域的基礎(chǔ)，像數(shù)據(jù)庫(kù)操作、信號(hào)處理、圖象壓縮等等都可最終歸結(jié)為對(duì)集合的操作。但是對(duì)于像包含了高維無(wú)序向量的集合，要對(duì)其進(jìn)行有效快速的集合運(yùn)算，在經(jīng)典電子計(jì)算機(jī)上是困難的。因此，我們就需要新的原理和新的算法來(lái)有效操作集合。在本文

5、中我們針對(duì)上面的困難提出了一個(gè)新的算法一量子集合算法并且給出了該算法在信號(hào)處理問題中的一個(gè)有效應(yīng)用。 本文主要包括三個(gè)部分： 第一部分回顧了量子計(jì)算的起源及研究進(jìn)展，研究和分析了量子計(jì)算的基本原理和相關(guān)概念。重點(diǎn)研究和分析了Shor算法、Grover算法，Boyer算法等已知的重要量子算法。 第二部分介紹了旋轉(zhuǎn)子空間方法以及經(jīng)典數(shù)據(jù)與量子存儲(chǔ)器關(guān)聯(lián)方案，并且在此基礎(chǔ)上結(jié)合Grover搜索算法設(shè)計(jì)出了量子集合算法，