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

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

2010-03-29

arxiv.org/abs/1003.5564v2

Phys. Rev.A82:032331, 2010

Physics

Quantum Physics

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

Scientific paper

10.1103/PhysRevA.82.032331

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.

Affiliated with

Also associated with

No associations

Rating

Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Search on a Hypercubic Lattice through a Quantum Random Walk: II. d=2 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499962