量子隨機(jī)行走搜索算法研究.pdf

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

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

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