Search on a hypercubic lattice using a quantum random walk. I. d>2

DOI10.1103/PHYSREVA.82.032330zbMATH Open1255.81115arXiv1003.0065MaRDI QIDQ4903073FDOQ4903073

Authors: Apoorva Patel, M.D. Aminoor Rahaman 

Publication date: 19 January 2013

Published in: Physical Review A (Search for Journal in Brave)

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 $doinfty$ limit). In particular, the scaling behaviour for $d=3$ is only about 25% higher than the optimal $doinfty$ value.

Full work available at URL: https://arxiv.org/abs/1003.0065

Recommendations

• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Spatial search and the Dirac equation
• Quantum search algorithms on the hypercube
• Spatial search using the discrete time quantum walk
• Faster quantum-walk algorithm for the two-dimensional spatial search

zbMATH Keywords

diffusion process

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum stochastic calculus (81S25)

Cites Work

• Faster quantum-walk algorithm for the two-dimensional spatial search
• Quantum random walks do not need a coin toss
• Spatial search and the Dirac equation
• Strengths and Weaknesses of Quantum Computing
• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Quantum search algorithms on the hypercube

Cited In (11)

• Quantum walk search on a two-dimensional grid with extra edges
• Spatial search using the discrete time quantum walk
• Quantum walks: a comprehensive review
• Random walk quantum clustering algorithm based on space
• Search on a hypercubic lattice using a quantum random walk. II. \(d=2\)
• Quantum transport in \(d\)-dimensional lattices
• Robust quantum spatial search
• The quantum walk search algorithm: factors affecting efficiency
• Spatial search and the Dirac equation
• Quantum search algorithms on the hypercube
• Faster quantum-walk algorithm for the two-dimensional spatial search

This page was built for publication: Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4903073)