Connectivity is a Poor Indicator of Fast Quantum Search

A randomly walking quantum particle evolving by Schrödinger’s equation searches on $d$-dimensional cubic lattices in $O(\sqrt{N})$ time when $d\ge 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.

Figure 1

(a) The complete graph with 6 vertices. (b) A strongly regular graph (Paley graph) with parameters (9, 4, 1, 2). (c) The four-dimensional hypercube. Without loss of generality, a marked vertex is colored red, and identically evolving vertices are identically colored.

Figure 2

A graph with 12 vertices constructed by joining two complete graphs of six vertices by a single edge.

Figure 3

A five-simplex with each vertex replaced with a complete graph of five vertices.

Figure 4

Squared overlaps of $|s⟩$ and $|a⟩$ with eigenstates of $H$ for search on the complete graph with $N=1024$.

Figure 5

Squared overlaps of $|s⟩$ and $|a⟩$ with eigenstates of $H$ for search on joined complete graphs with 1024 total vertices.

Figure 6

Success probability as a function of time for search on joined complete graphs with 1024 total vertices.

Figure 7

Squared overlaps of $|s⟩$, $|a⟩$, and $|b⟩$ with eigenstates of $H$ for search on a simplex of complete graphs with $M=100$.

Figure 8

Probability at $|b⟩$ as a function of time for search on a simplex of complete graphs with $M=100$. Probability accumulates during the first stage of the algorithm from $t=0$ to $\pi {100}^{3/2}/4\approx 785.40$, and then it quickly leaves during the second stage, which takes $\pi \sqrt{100}/2\approx 15.71$ time.

Figure 9

Probability at $|a⟩$ (i.e., the success probability) as a function of time for search on a simplex of complete graphs with $M=100$. During the second stage of the algorithm starting at $t=\pi {100}^{3/2}/4\approx 785.40$ for a time of $\pi \sqrt{100}/2\approx 15.75$, the probability quickly accumulates.