集合運算的量子算法設計及其應用.pdf

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

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

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

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

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