1、在20世紀(jì)90年代中期，Shor量子因子分解算法和Grover量子搜索算法的相繼提出，引起了人們對量子計算與量子信息的極大興趣，這是因為這兩個算法充分展示了量子計算機(jī)在某些方面能夠從根本上超越經(jīng)典計算機(jī)的計算能力。近年來，量子行走引起了理論研究者的關(guān)注，主要是因為經(jīng)典隨機(jī)行走在計算機(jī)科學(xué)、生物學(xué)、物理學(xué)等多個學(xué)科有著廣泛的應(yīng)用，而量子行走可看成經(jīng)典隨機(jī)行走在量子系統(tǒng)中的自然推廣，因此人們希望能夠借助于量子行走發(fā)現(xiàn)更多高效的量子算法。

2、r>　　本文在介紹量子算法基礎(chǔ)知識和Grover算法的基礎(chǔ)上，分別描述了兩種離散量子行走模型:硬幣量子行走和散射量子行走，并將硬幣量子行走與經(jīng)典隨機(jī)行走進(jìn)行了分析對比;然后討論了第一個基于量子行走的搜索算法—SKW算法，該算法與Grover算法搜索速度一樣，但其Oracle算子作用的空間維數(shù)小于Grover搜索算法，這表明SKW算法相對于Grover算法來說在物理上更易于實現(xiàn)。
　　本文最后集中討論了在星圖上的散射量子行走。首先證