Search on a hypercubic lattice using a quantum random walk. II. d=2

DOI10.1103/PHYSREVA.82.032331zbMATH Open1255.81114arXiv1003.5564MaRDI QIDQ4903074FDOQ4903074

Authors: Apoorva Patel, K. S. Raghunathan, M.D. Aminoor Rahaman 

Publication date: 19 January 2013

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

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(sqrtNlogN)$ algorithm, which is not optimal. The scaling behaviour can be improved to $O(sqrtNlogN)$ 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.

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

Recommendations

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

zbMATH Keywords

hypercubic lattice

Mathematics Subject Classification ID

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

Cites Work

• Faster quantum-walk algorithm for the two-dimensional spatial search
• Spatial search and the Dirac equation
• Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)

Cited In (12)

• The staggered quantum walk model
• Moments of coinless quantum walks on lattices
• Quantum walk search on a two-dimensional grid with extra edges
• Spatial search using the discrete time quantum walk
• Quantum walks: a comprehensive review
• Robust quantum spatial search
• The quantum walk search algorithm: factors affecting efficiency
• Spatial search and the Dirac equation
• Perfect state transfer by means of discrete-time quantum walk on complete bipartite graphs
• Search on a hypercubic lattice using a quantum random walk. I. \(d>2\)
• 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. II. \(d=2\)

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