量子游走

来源

量子游走是经典随机游走在设计随机化的运算法则时的一种延伸，是几种量子运算法则中的一种。对于一些难解的问题，量子游走提供了一种比任何经典计算快指数倍的运算法则。在很多实际问题中，量子游走相比经典计算有更快的多项式分解速度，比如元素区分问题，寻找三角形问题和数值评价“与非树”。著名的Grover搜索算法也可以认为是一种量子游走算法。

和经典随机游走的关联

量子游走表现出和经典随机游走非常不同的特点。特别的是，它们不会汇集于一个限制的分布状态，并且由于量子干涉效应的影响，相比于它们的经典等效而言，要传播的明显快一点或者慢一点。

连续时间

在特殊的条件下，连续时间下的量子游走能够作为一般量子计算的一种模型。但这并不意味着它的局限性。

分离时间

分离时间下的量子游走的特性是由一个量子硬币（比如量子自旋的上下）和变换算符决定的，是一种一直被重复的行为。

考虑当我们使一个有质量的狄拉克算子离散分布在一维空间中会发生什么。在不存在质量这一项时，我们得到向左移动者和向右移动者。它们可以被一个内秉自由度所描述，“自旋”或者一个“量子硬币”。当我们考虑质量项时，量子游走和它内在的“量子硬币”空间中的一个自旋相一致。一个量子游走相当于是量子转换和“量子硬币”算子的不断重复。

这和一维空间和一维时间下电子的费曼模型特别像。他用这种方式总结这些曲折的路径：向左移动的部分等同于其中一个自旋方向（或者一个“量子硬币”的一面），向右移动的部分等同于另一个。