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

【文章來源】：中國科學技術大學安徽省 211工程院校 985工程院校

【文章頁數】：41 頁

【學位級別】：碩士

【部分圖文】：

圖３．１經典的一維隨機游走過程示意圖??


本文編號：3369730