Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2

Abstract

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretised according to the staggered lattice fermion formalism. $d=2$ is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behaviour. As a result, the construction used in our accompanying article \cite{dgt2search} provides an $O(\sqrt{N}\log N)$ algorithm, which is not optimal. The scaling behaviour can be improved to $O(\sqrt{N\log N})$ by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi \cite{tulsi}. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimise the proportionality constants of the scaling behaviour of the algorithm by numerically tuning the parameters.

Revtex4, 5 pages (v2) Introduction and references expanded. Published version

References in corpus (6)

• Quantum random walks - an introductory overview
• A Quantum Random Walk Search Algorithm
• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• From Schrödinger's Equation to the Quantum Search Algorithm
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2

Cited by in corpus (15)

• Quantum walks: a comprehensive review
• The Staggered Quantum Walk Model
• Staggered Quantum Walks on Graphs
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Spatial search by continuous-time quantum walks on crystal lattices
• Search on a Hypercubic Lattice using a Quantum Random Walk: I. d>2
• Search on a Fractal Lattice using a Quantum Random Walk
• The Grover search as a naturally occurring phenomenon
• One-Dimensional Coinless Quantum Walks
• Moments of Coinless Quantum Walks on Lattices
• High-dimensional quantum state transfer in a noisy network environment
• The quantum walk search algorithm: Factors affecting efficiency
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Spatial Search on Sierpinski Carpet Using Quantum Walk
• Universal scaling hypothesis of quantum spatial search in complex networks