# Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2 - Quantum Physics

Abstract: Random walks describe diffusion processes, where movement at every time stepis restricted to only the neighbouring locations. We construct a quantum randomwalk algorithm, based on discretisation of the Dirac evolution operatorinspired by staggered lattice fermions. We use it to investigate the spatialsearch problem, i.e. finding a marked vertex on a $d$-dimensional hypercubiclattice. The restriction on movement hardly matters for $d>2$, and scalingbehaviour close to Grover-s optimal algorithm which has no restriction onmovement can be achieved. Using numerical simulations, we optimise theproportionality constants of the scaling behaviour, and demonstrate theapproach to that for Grover-s algorithm equivalent to the mean field theory orthe $d\to\infty$ limit. In particular, the scaling behaviour for $d=3$ is onlyabout 25% higher than the optimal $d\to\infty$ value.

Author: Apoorva Patel, Md. Aminoor Rahaman

Source: https://arxiv.org/