量子遊走

在量子計算中，量子遊走是經典隨機遊走（如布朗運動）的量子模擬。和經典隨機遊走相似，量子遊走中遊走單位的瞬時狀態由所處位置的機率分布描述，在量子遊走中遊走單位是處在很多位置的重合態中。類比經典隨機遊走，有兩種形式的量子遊走，分離時間下的量子遊走和連續時間下的量子遊走。

來源

量子遊走是經典隨機遊走在設計隨機化的運算法則時的一種延伸，是幾種量子運算法則中的一種。對於一些難解的問題，量子遊走提供了一種比任何經典計算快指數倍的運算法則。在很多實際問題中，量子遊走相比經典計算有更快的多項式分解速度，比如元素區分問題，尋找三角形問題和數值評價“與非樹”。著名的Grover搜尋算法也可以認為是一種量子遊走算法。

和經典隨機遊走的關聯

量子遊走表現出和經典隨機遊走非常不同的特點。特別的是，它們不會匯集於一個限制的分布狀態，並且由於量子干涉效應的影響，相比於它們的經典等效而言，要傳播的明顯快一點或者慢一點。

連續時間

在特殊的條件下，連續時間下的量子遊走能夠作為一般量子計算的一種模型。但這並不意味著它的局限性。

分離時間

分離時間下的量子遊走的特性是由一個量子硬幣（比如量子自旋的上下）和變換算符決定的，是一種一直被重複的行為。

考慮當我們使一個有質量的狄拉克運算元離散分布在一維空間中會發生什麼。在不存在質量這一項時，我們得到向左移動者和向右移動者。它們可以被一個內秉自由度所描述，“自旋”或者一個“量子硬幣”。當我們考慮質量項時，量子遊走和它內在的“量子硬幣”空間中的一個自旋相一致。一個量子遊走相當於是量子轉換和“量子硬幣”運算元的不斷重複。

這和一維空間和一維時間下電子的費曼模型特別像。他用這種方式總結這些曲折的路徑：向左移動的部分等同於其中一個自旋方向（或者一個“量子硬幣”的一面），向右移動的部分等同於另一個。