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

DOI10.1103/PHYSREVA.82.032331MaRDI QIDQ4903074zbMATH OpenFDO

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)

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

zbMATH Keywords

hypercubic lattice

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(12)

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

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)