Grover量子搜索算法理論研究.pdf

1、量子計算是利用量子力學(xué)原理進(jìn)行信息處理的新近發(fā)展起來的前沿學(xué)科，近20年來的量子計算理論研究表明，量子計算在很多方面比經(jīng)典計算優(yōu)越得多，特別是在量子系統(tǒng)的模擬、大數(shù)因子分解和無序數(shù)據(jù)庫搜索等問題上尤為突出。對于在無序數(shù)據(jù)庫中搜索若干特定目標(biāo)時，Grover量子搜索算法可以對許多(雖不是全部)啟發(fā)式搜索的經(jīng)典算法起到實(shí)質(zhì)性的二次加速作用。Grover量子搜索算法在搜索時忽略搜索元素的性質(zhì)，而把注意力放在那些元素的指標(biāo)上，因此具有很強(qiáng)的通用

2、性。同時，它可以有效地破譯DES密碼體系，具有加速搜索密碼系統(tǒng)密鑰的潛在用途。
　　本文主要圍繞Grover量子搜索算法中的相位匹配問題、算法的物理實(shí)現(xiàn)以及應(yīng)用等方面進(jìn)行了研究，具體內(nèi)容如下：
　　量子糾纏是量子計算和量子信息處理中的重要資源，是產(chǎn)生量子加速的根本原因。基于線性光學(xué)和腔QED技術(shù)，分別提出制備量子多體糾纏態(tài)的物理方案。實(shí)驗(yàn)裝置由簡單的線性光學(xué)元件、原子-腔相互作用系統(tǒng)、單光子態(tài)、最大和非最大的雙光子糾纏態(tài)、以

3、及常規(guī)光子探測器所組成。在探測過程中，常規(guī)光子探測器的使用極大地降低了實(shí)驗(yàn)上對高質(zhì)量探測器探測效率的需求，簡化了實(shí)驗(yàn)的實(shí)現(xiàn)。
　　利用數(shù)學(xué)計算方法，研究和討論了Grover量子搜索算法中的相位匹配問題，并提出π/3.61相位搜索算法。在這個算法中，搜索成功的概率至少為94.11％。π/3.61相位搜索算法克服了Grover量子搜索算法中成功概率隨目標(biāo)項(xiàng)數(shù)目增多而急劇下降的弱點(diǎn)，同時也證明了Grover量子搜索算法能夠魯棒的反對噪聲

4、和一定的擾動。利用原子間偶極相互作用和原子-腔相互作用，提出在腔QED中實(shí)現(xiàn)兩量子比特Grover量子搜索算法。在這個方案中，實(shí)現(xiàn)Grover量子搜索算法所需要的兩量子比特條件相位門操作可以很容易地被實(shí)現(xiàn)，且不需要執(zhí)行輔助的單量子比特操作；同時，由于使用了強(qiáng)經(jīng)典場，這個方案對于腔場衰減和熱場效應(yīng)不敏感。
　　基于Grover量子搜索算法，提出宇稱(奇偶)確定算法和二次剩余算法。在宇稱確定算法中，通過對滿足條件f(x)=-1的元素進(jìn)

5、行計數(shù)，函數(shù)f(x)的宇稱可以被確定。同時，討論了不同情況下這個算法計算復(fù)雜度的上界和下界。在二次剩余算法中，算法的計算消耗主要集中在計算模M的二次剩余以及所需的迭代次數(shù)上。經(jīng)典計算機(jī)上，求解二次剩余方程需要進(jìn)行M/2次計算，利用量子算法則可以在O(√M/2)步內(nèi)以接近100%的成功概率求出二次剩余方程的解，實(shí)現(xiàn)了相對經(jīng)典計算的二次加速。
　　基于廣義Grover量子搜索算法，提出應(yīng)用量子計算機(jī)算法直接測量任意一個未知的兩量子比特

6、純態(tài)系統(tǒng)的糾纏度。我們具體地構(gòu)建了廣義Grover迭代算子，通過對兩體純態(tài)系統(tǒng)的兩個拷貝應(yīng)用量子算法以及對輔助工作量子比特進(jìn)行測量，可以得到系統(tǒng)糾纏度的一個較好的、近似的估計值。這個方案在實(shí)驗(yàn)上的實(shí)現(xiàn)對于更加復(fù)雜的、任意量子比特數(shù)目的、有限維數(shù)量子系統(tǒng)的糾纏測量將是一個重大的推進(jìn)，同時能夠展現(xiàn)出量子計算機(jī)強(qiáng)大的計算能力。
　　基于腔QED技術(shù)，提出實(shí)現(xiàn)量子離散Fourier變換的有效的量子線路和物理方案。利用單原子-腔相互作用，提

7、出物理方案實(shí)現(xiàn)-比特量子離散Fourier變換。在這個方案中，通過發(fā)送原子通過一系列的經(jīng)典場和腔場以及適當(dāng)改變腔場的頻率，得到一個可調(diào)的兩量子比特條件相位門。在消相干時間范圍內(nèi)，所有的單比特和兩比特量子門操作都能夠被完成，有利于實(shí)現(xiàn)多比特量子Fourier變換。利用雙原子-腔相互作用，提出物理方案實(shí)現(xiàn)-比特量子離散Fourier變換。在這個方案中，基于CNOT門和SWCZ門操作(取代了原量子Fourier變換線路中復(fù)雜的受控-門和SWA