Southwest Quantum Information and Technology

Faster search by lackadaisical quantum walk

Presenting Author: Thomas Wong, Creighton University

Quantum walks, the quantum analogues of random walks, are the basis for several quantum algorithms. Contrary to some intuition, making a discrete-time quantum walk lazy by adding self-loops to each vertex, called a lackadaisical quantum walk, can actually speed up the quantum walk. In particular, the ballistic dispersion can be made faster, search on the complete graph (i.e., Grover's algorithm formulated as a quantum walk) can be improved by a constant factor, and search on the two-dimensional grid improves by a factor of the square root of the number of vertices.

Read this article online: https://arxiv.org/abs/1706.06939, http://arxiv.org/abs/1703.10134, http://arxiv.org/abs/1502.04567

(Session 5 : Thursday from 5:00pm - 7:00 pm)