Department of Mathematics, University of California, San Diego, La Jolla, California 92093-0112, USA.
Department of Physics, University of California, San Diego, La Jolla, California 92093-0354, USA.
Phys Rev Lett. 2015 Mar 20;114(11):110503. doi: 10.1103/PhysRevLett.114.110503. Epub 2015 Mar 18.
A randomly walking quantum particle evolving by Schrödinger's equation searches on d-dimensional cubic lattices in O(√N) time when d≥5, and with progressively slower runtime as d decreases. This suggests that graph connectivity (including vertex, edge, algebraic, and normalized algebraic connectivities) is an indicator of fast quantum search, a belief supported by fast quantum search on complete graphs, strongly regular graphs, and hypercubes, all of which are highly connected. In this Letter, we show this intuition to be false by giving two examples of graphs for which the opposite holds true: one with low connectivity but fast search, and one with high connectivity but slow search. The second example is a novel two-stage quantum walk algorithm in which the walking rate must be adjusted to yield high search probability.
当 d≥5 时，通过薛定谔方程演化的随机行走量子粒子在 O(√N)时间内在 d 维立方格子上进行搜索，随着 d 的减小，运行时间逐渐变慢。这表明图连通性（包括顶点、边、代数和归一化代数连通性）是快速量子搜索的指标，这一信念得到了完全图、强正则图和超立方体上快速量子搜索的支持，所有这些图都是高度连通的。在这封信中，我们通过给出两个相反情况的图的例子来证明这种直觉是错误的：一个连接度低但搜索速度快，另一个连接度高但搜索速度慢。第二个例子是一种新的两阶段量子游走算法，其中必须调整游走速度以产生高搜索概率。
