集合運算在量子計算機上的實現(xiàn).pdf

1、量子計算與量子信息是涉及物理學(xué)、計算機科學(xué)、數(shù)學(xué)以及信息科學(xué)等多個學(xué)科的新興綜合性交叉研究領(lǐng)域。在處理眾多特殊問題上,量子計算機展示了它比傳統(tǒng)計算機,更加優(yōu)越的巨大潛力。例如:1994年,petershor提出的算法能在量子計算機上有效的解決兩個非常重要的問題:整數(shù)質(zhì)因數(shù)分解、離散對數(shù)問題,這些問題在傳統(tǒng)計算機上都是不能有效的被解決的。在量子計算的研究中,計算性能的優(yōu)越性主要體現(xiàn)在算法的有效性上。目前為止,被公認(rèn)的最具代表性的量子算法有

2、Shot的大數(shù)質(zhì)因子分解算法以及Grover提出的數(shù)據(jù)庫搜索量子算法。然而,Grover搜索算法在搜索復(fù)雜的數(shù)據(jù)庫時存在著很大的足限性,因為Grover搜索算法只能處理在全空間中的量子比特,而不能處理在子空間中的量子比特。例如,它在處理部分量子比特時不可能保持另一部分量子比特不變。此外,數(shù)據(jù)在被處理之前,必須先加載到寄存器中,才能完成處理任務(wù)。但由于經(jīng)典的數(shù)據(jù)是通過輸入輸出設(shè)備,被逐個的加載到寄存器中去的。輸入輸出設(shè)備由于其逐個加載數(shù)據(jù)

3、的方式,嚴(yán)重地拖慢了計算機的運算速度,從而成為經(jīng)典計算機的效率瓶頸。量子計算機又不能直接處理經(jīng)典的數(shù)據(jù)信息,只能對量子態(tài)進(jìn)行處理。要對量子態(tài)進(jìn)行處理必須把經(jīng)典數(shù)據(jù)加載到量子態(tài)上,因此必須有一個針對量子計算機的數(shù)據(jù)存儲方案。這正是本文將研究的量子數(shù)據(jù)加載方案(QLS)。數(shù)據(jù)庫操作、信號處理、圖像壓縮等領(lǐng)域,由于其數(shù)據(jù)庫的龐大性,在經(jīng)典計算機上處理這類問題是非常困難的。而這些問題最終又可以歸結(jié)為對集合的操作。因此在量子計算機上有效地處理集合

4、問題,就成了解決上述問題的關(guān)鍵?；谝陨蠁栴},在這篇文章中,提出了基于量子裝載方案(OLS)和旋轉(zhuǎn)子空間理論的量子集合算法,能夠在量子計算機上有效地解決集合運算類問題。
　　 本文分為以下三個部分:
　　 第一部分對量子計算的歷史概況進(jìn)行了簡述,以及量子計算的準(zhǔn)備知識。對歷史上比較重要的量子算法進(jìn)行了重點分析,如Shor因子分解算法、G-rover搜索算法等已被提出的算法。
　　 第二部分這部分介紹了旋轉(zhuǎn)子空間理