單向量子隨機行走及其算法研究.pdf

1、隨機行走(random walk)理論產(chǎn)生于19世紀(jì)，經(jīng)過近2個世紀(jì)的發(fā)展，在化學(xué)、地理、仿真學(xué)以及經(jīng)濟學(xué)等領(lǐng)域都有著廣泛的應(yīng)用。20世紀(jì)末，Aharonov等人將隨機行走理論擴展到了量子力學(xué)領(lǐng)域，提出了量子隨機行走概念，由于融合了量子并行計算等量子力學(xué)特有性質(zhì)，量子隨機行走具有更快的擴散速度，在解決某些算法問題時，有可能獲得比經(jīng)典行走更少的時間復(fù)雜度。第一個基于量子隨機行走的搜索算法——SKW算法的提出，從理論上證實了量子隨機行走在算

2、法上的優(yōu)越性。近年來，隨著量子隨機行走理論研究的不斷深入，取得了很多成果，為研究新的量子算法提供了參考。
　　本文首先介紹了量子計算基本理論，在此基礎(chǔ)引出了量子隨機行走的概念，對兩種量子隨機行走模型進行了描述，并對直線上離散量子隨機行走進行了仿真，獲得了不同初始條件下的概率分布圖。然后討論了SKW算法，并對算法的實現(xiàn)步驟進行了詳細(xì)描述。
　　接著本文構(gòu)造了一種凱萊圖，采用離散量子隨機行走計算模型，通過理論分析獲得了該圖上Gr