Mixing times in quantum walks on two-dimensional grids

Mixing properties of discrete-time quantum walks on two-dimensional grids with toruslike boundary conditions are analyzed, focusing on their connection to the complexity of the corresponding abstract search algorithm. In particular, an exact expression for the stationary distribution of the coherent walk over odd-sided lattices is obtained after solving the eigenproblem for the evolution operator for this particular graph. The limiting distribution and mixing time of a quantum walk with a coin operator modified as in the abstract search algorithm are obtained numerically. On the basis of these results, the relation between the mixing time of the modified walk and the running time of the corresponding abstract search algorithm is discussed.

Figure 1

Left panel: Limiting distribution for quantum walk in two-dimensional grid with $\sqrt{N}=41$, obtained from Eq. (18) with the initial condition (12). Right panel: Contour plot for the same distribution.

Figure 2

Left panel: Total variation distance to both the uniform and the stationary distributions of the quantum walk on the two-dimensional grid with flip-flop shift as a function of the time step. Right panel: Mixing time to the stationary distribution as a function of the input size.

Figure 3

Quantum walk in two-dimensional grid with $\sqrt{N}=41$ and a modified coin used to search for a marked node. Left panel: Probability distribution after $t=80$ steps, corresponding to the instant of maximum probability at the marked node. Right panel: Stationary distribution approximated with $T={10}^4$ simulation steps.

Figure 4

Left panel: Total variation distance to both the uniform and the stationary distributions of the quantum walk in two-dimensional grid with modified coin used to search for a marked node. Right panel: Mixing time to the stationary distribution as a function of the input size.