量子搜索算法的研究.pdf

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

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