Kendon Vivien M
School of Physics and Astronomy, University of Leeds, Leeds LS2 9JT, UK.
Philos Trans A Math Phys Eng Sci. 2006 Dec 15;364(1849):3407-22. doi: 10.1098/rsta.2006.1901.
The development of quantum algorithms based on quantum versions of random walks is placed in the context of the emerging field of quantum computing. Constructing a suitable quantum version of a random walk is not trivial; pure quantum dynamics is deterministic, so randomness only enters during the measurement phase, i.e. when converting the quantum information into classical information. The outcome of a quantum random walk is very different from the corresponding classical random walk owing to the interference between the different possible paths. The upshot is that quantum walkers find themselves further from their starting point than a classical walker on average, and this forms the basis of a quantum speed up, which can be exploited to solve problems faster. Surprisingly, the effect of making the walk slightly less than perfectly quantum can optimize the properties of the quantum walk for algorithmic applications. Looking to the future, even with a small quantum computer available, the development of quantum walk algorithms might proceed more rapidly than it has, especially for solving real problems.
基于随机游走量子版本的量子算法的发展处于新兴的量子计算领域背景之下。构建合适的随机游走量子版本并非易事；纯量子动力学是确定性的，所以随机性仅在测量阶段进入，即在将量子信息转换为经典信息时。由于不同可能路径之间的干涉，量子随机游走的结果与相应的经典随机游走非常不同。结果是，量子游走者平均而言比经典游走者离其起点更远，这构成了量子加速的基础，可用于更快地解决问题。令人惊讶的是，使游走略低于完美量子状态的效果可以优化量子游走在算法应用中的特性。展望未来，即使有一台小型量子计算机可用，量子游走算法的发展可能会比以往更快，特别是在解决实际问题方面。
