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

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

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