離散的量子隨機行走算法研究.pdf

1、在20世紀90年代中期，Shor量子因子分解算法和Grover量子搜索算法被相繼發(fā)現(xiàn)，由于這兩個算法展示了在經(jīng)典計算機中無法比擬的計算能力，從而引起了人們對量子計算與量子信息的極大興趣。近年來，量子隨機行走正逐漸引起人們關(guān)注，這主要原因是經(jīng)典隨機行走在許多領(lǐng)域中有著廣泛的應(yīng)用，而量子隨機行走可看成是經(jīng)典隨機行走在量子系統(tǒng)中的自然推廣，因此人們希望借助于量子隨機行走發(fā)現(xiàn)更多高效的量子算法。
　　本文在介紹了量子算法基礎(chǔ)理論和Grov

2、er算法的基礎(chǔ)上，分別討論了一維和n維的量子隨機行走模型，并把它們與經(jīng)典隨機行走進行了分析對比；然后我們討論了第一個基于量子隨機行走的搜索算法-SKW算法，該算法與Grover算法時間復(fù)雜度是一樣，但其Oracle算子作用的空間維數(shù)小于Grover搜索算法，這表明SKW算法比Grover算法更易于實現(xiàn)。
　　最后本文提出了一種求解K-團問題的量子隨機行走算法，該算法主要結(jié)合了量子隨機行走特性和Grover算法思想。K-團問題是圖論