量子隨機行走搜索算法研究.pdf

1、量子計算與量子信息的研究可以追溯到幾十年前，但真正引起廣泛關注是在20世紀90年代中期。這期間發(fā)現(xiàn)了Shor快速因子分解算法和Grover搜索算法，這兩類算法展示了量子計算機從根本上超越經(jīng)典計算機的計算能力。近年來，量子隨機行走正逐漸開始引起人們重視，這是因為一方面，量子隨機行走可以看作是經(jīng)典隨機行走在量子系統(tǒng)上的一種自然推廣，另一方面，量子隨機行走能夠應用于構造有效的量子算法。 本文首先介紹量子隨機行走和一種基于量子隨機行走的

2、搜索算法，即量子隨機行走搜索算法，它與Grover搜索算法有著相同的搜索速度。接著我們研究了兩種噪聲模型對該算法的影響。在第一種噪聲模型中我們假設算法執(zhí)行時，控制隨機行走方向的量子硬幣在算符作用下進行的相位翻轉操作含有一定的誤差，即相位噪聲，我們研究了這種相位噪聲對搜索算法產(chǎn)生的影響。早先人們已經(jīng)研究了這種相位噪聲對于Grover搜索算法的影響，我們通過比較發(fā)現(xiàn)，兩種搜索算法在對相位噪聲的響應上有著相同和不同之處。在第二種模型中我們主要

3、研究了白噪聲對于量子隨機行走搜索算法的影響。由于在真實環(huán)境中搜索算法執(zhí)行的每一步都會因為與周圍壞境相互作用而出現(xiàn)退相干效應，它會使存儲在量子計算機中的量子態(tài)幾率幅發(fā)生漲落，從而改變最后的輸出結果。我們將這種效應模型化為算法每一步執(zhí)行過程中量子態(tài)上出現(xiàn)的高斯白噪聲，我們通過計算機模擬研究了它對算法的影響，并與Grover搜索算法進行了比較。 本文的工作有助于進一步了解量子隨機行走搜索算法與Grover搜索算法之間的區(qū)別和差異，并對