Optimized quantum random-walk search algorithms on the hypercube

Shenvi, Kempe, and Whaley’s quantum random-walk search (SKW) algorithm [Phys. Rev. A 67, 052307 (2003)] is known to require $O\left(\sqrt{N}\right)$ number of oracle queries to find the marked element, where $N$ is the size of the search space. The overall time complexity of the SKW algorithm differs from the best achievable on a quantum computer only by a constant factor. We present improvements to the SKW algorithm which yield a significant increase in success probability, and an improvement on query complexity such that the theoretical limit of a search algorithm succeeding with probability close to one is reached. We point out which improvement can be applied if there is more than one marked element to find.

Figure 1

The plot shows the numerically calculated probability distribution for the position of the walker after the optimal number of iterations of the SKW quantum walk in $n=5$ dimensions. In accordance with the analytic results, the probability distribution has its maximum for the marked vertex ${\vec{x}}_{\mathrm{tg}}=0$ reaching a value close to $1∕2$. Moreover, we observe that the nearest neighbors are also presented with high probability, and the sum of these probabilities is comparable to that of the marked vertex.

Figure 2

Extension of the search in $n=3$ dimensions to a hypercube in $n^{\prime }=4$ dimensions without distinguishing even and odd parity vertices. The operator $X$ denotes the application of the Pauli ${\sigma }_X$ operation to the last qubit. The effect of operator $X$ is switching between the image and the anti-image of a vertex.