量子計(jì)算作為一種新型的計(jì)算模式,在解決質(zhì)因子分解等計(jì)算難題時(shí),展現(xiàn)出了比經(jīng)典計(jì)算更高效的計(jì)算能力,因而引起人們的廣泛關(guān)注。近些年來(lái),隨著對(duì)量子計(jì)算領(lǐng)域研究的深入,研究者們?cè)诹孔与S機(jī)游走、解線性方程組等諸多方面取得了很多重要進(jìn)展。量子隨機(jī)游走作為隨機(jī)游走在量子領(lǐng)域的自然延伸,為人們發(fā)現(xiàn)更多更好的量子算法提供了一個(gè)新的研究思路。本文將介紹量子隨機(jī)游走的有關(guān)內(nèi)容。本文首先介紹了量子力學(xué)的一些基本概念及Grover算法,并給出了 Grover算法的一個(gè)應(yīng)用實(shí)例。接著介紹了量子隨機(jī)游走的兩種模型:硬幣量子隨機(jī)游走、散射量子隨機(jī)游走,將線上H硬幣量子隨機(jī)游走和經(jīng)典的一維隨機(jī)游走進(jìn)行比較,說(shuō)明了量子隨機(jī)游走有加速算法的潛能。然后介紹了第一個(gè)量子隨機(jī)游走算法,即SKW算法,該算法的時(shí)間復(fù)雜度雖然和Grover算法相同,但其作用空間維數(shù)低,易于實(shí)現(xiàn)。最后介紹了量子隨機(jī)游走的一個(gè)重要應(yīng)用,即目前在圖上查詢?nèi)切螁?wèn)題最好的一個(gè)算法,該算法結(jié)合了 Johnson圖上量子隨機(jī)游走、組合等思想,降低了算法復(fù)雜度。并對(duì)文中的一個(gè)重要引理給出了自己的證明。 

【文章來(lái)源】：中國(guó)科學(xué)技術(shù)大學(xué)安徽省 211工程院校 985工程院校

【文章頁(yè)數(shù)】：41 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

圖３．１經(jīng)典的一維隨機(jī)游走過(guò)程示意圖??


本文編號(hào)：3369730