Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians

Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.

Figure 1

Running time (crosses, red line) and the inverse of the success probability (diamonds, blue dashed line) as a function of $N$ in the loglog scale when $\theta =\pi /4$ for the alternative model. The points are obtained from numerical simulations and the fitting lines using the least square method.

Figure 2

$\lambda$ (crosses, red line) and ${\varphi }_{\min }$ (diamonds, blue dashed line) as a function of $N$ when $\theta =\pi /3$. The points are obtained from numerical calculations of the eigenvalues of ${\mathcal{U}}_0$ and $U$, respectively.