集合運(yùn)算在量子計(jì)算機(jī)上的實(shí)現(xiàn).pdf

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

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

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

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