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

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

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

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

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

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