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

Abstract

Random walks describe diffusion processes, where movement at every time step is restricted to only the neighbouring locations. We construct a quantum random walk algorithm, based on discretisation of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, i.e. finding a marked vertex on a $d$-dimensional hypercubic lattice. The restriction on movement hardly matters for $d>2$, and scaling behaviour close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimise the proportionality constants of the scaling behaviour, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean field theory or the $d\to \infty$ limit). In particular, the scaling behaviour for $d=3$ is only about 25% higher than the optimal $d\to \infty$ value.

11 pages, Revtex (v2) Introduction and references expanded. Published version

References in corpus (4)

• Faster quantum walk algorithm for the two dimensional spatial search
• Spatial search and the Dirac equation
• Quantum search algorithms on the hypercube
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2

Cited by in corpus (20)

• Quantum walks: a comprehensive review
• 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
• Quantum transport in d-dimensional lattices
• Search on a Fractal Lattice using a Quantum Random Walk
• The Grover search as a naturally occurring phenomenon
• Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2
• High-dimensional quantum state transfer in a noisy network environment
• The quantum walk search algorithm: Factors affecting efficiency
• Non-Markovian quantum interference in multilevel quantum systems: Exact master equation approach
• Scaling Hypothesis of Spatial Search on Fractal Lattice Using Quantum Walk
• Spatial Search on Graphs with Multiple Targets using Flip-flop Quantum Walk
• Spatial Search on Sierpinski Carpet Using Quantum Walk
• A Complete Characterization of Pretty Good State Transfer on Paths
• Improving the query complexity of quantum spatial search in two dimensions
• Quantum Algorithms: Database Search and its Variations
• Spatial search using the discrete time quantum walk
• Quantum Computation: Particle and Wave Aspects of Algorithms
• Universal scaling hypothesis of quantum spatial search in complex networks