Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk

Abhijith J., Apoorva Patel

Published 2018-01-04Version 1

We analyze the eigenvalue and eigenvector structure of the flip-flop quantum walk on regular graphs, explicitly demonstrating how it is quadratically faster than the classical random walk. Then we use it in a spatial search algorithm with multiple target states, and determine the scaling behavior as a function of the spectral gap and the number of target states. The scaling behavior is optimal as a function of the graph size, when the spectral gap of the adjacency matrix is $\Theta(1)$.