Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1003.5564 · Physical Review A

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

Apoorva D. Patel, K. S. Raghunathan, Md. Aminoor Rahaman

Published Sep 28, 2010• 23 citations
arXivHTMLPDF

Abstract

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized 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 behavior. As a result, the construction used in our accompanying article [A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an $O(\sqrt{N}\mathrm{ln}N)$ algorithm, which is not optimal. The scaling behavior can be improved to $O(\sqrt{N\mathrm{ln}N})$ by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi [Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

DOI
10.1103/physreva.82.032331

Related papers

Search on a Hypercubic Lattice using Quantum Random Walk

Apoorva Patel, Md. Aminoor Rahaman

We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized 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 behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.

•Jun 5, 2009•2 citations

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

Apoorva D. Patel, Md. Aminoor Rahaman

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

arXiv:1003.0065•Physical Review A•Sep 28, 2010•35 citations

Spatial search and the Dirac equation

Andrew M. Childs, Jeffrey Goldstone

We consider the problem of searching a $d$-dimensional lattice of $N$ sites for a single marked location. We present a Hamiltonian that solves this problem in time of order $\sqrt{N}$ for $d>2$ and of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}N$ in the critical dimension $d=2$. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of $d=4$), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.

arXiv:quant-ph/0405120•Physical Review A•Oct 19, 2004•145 citations

Search on a fractal lattice using a quantum random walk

Apoorva D. Patel, K. S. Raghunathan

The spatial search problem on regular lattice structures in integer number of dimensions $d\ensuremath{\ge}2$ has been studied extensively, using both coined and coinless quantum walks. The relativistic Dirac operator has been a crucial ingredient in these studies. Here, we investigate the spatial search problem on fractals of noninteger dimensions. Although the Dirac operator cannot be defined on a fractal, we construct the quantum walk on a fractal using the flip-flop operator that incorporates a Klein-Gordon mode. We find that the scaling behavior of the spatial search is determined by the spectral (and not the fractal) dimension. Our numerical results have been obtained on the well-known Sierpinski gaskets in two and three dimensions.

arXiv:1203.3950•Physical Review A•Jul 27, 2012•31 citations

Spatial search by continuous-time quantum walks on crystal lattices

Andrew M. Childs, Yimin Ge

We consider the problem of searching a general $d$-dimensional lattice of $N$ vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of $O(\sqrt{N})$ for $d>2$ and $O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)$ in $d=2$. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.

arXiv:1403.2676•Physical Review A•May 30, 2014•46 citations

Quantum Random Walks without a Coin Toss

Apoorva D. Patel, K. S. Raghunathan, Pranaw Rungta

We construct a quantum random walk algorithm, based on the Dirac operator instead of the Laplacian. The algorithm explores multiple evolutionary branches by superposition of states, and does not require the coin toss instruction of classical randomised algorithms. We use this algorithm to search for a marked vertex on a hypercubic lattice in arbitrary dimensions. Our numerical and analytical results match the scaling behaviour of earlier algorithms that use a coin toss instruction.

arXiv:quant-ph/0506221•Jun 27, 2005•1 citation
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized according to the staggered lattice fermion formalism. d=2d=2d=2 is the critical dimension for the spatial search problem, where infrared divergence of the evolution operator leads to logarithmic factors in the scaling behavior. As a result, the construction used in our accompanying article [A. Patel and M. A. Rahaman, Phys. Rev. A 82, 032330 (2010)] provides an O(NlnN)O(\sqrt{N}\mathrm{ln}N)O(N​lnN) algorithm, which is not optimal. The scaling behavior can be improved to O(NlnN)O(\sqrt{N\mathrm{ln}N})O(NlnN​) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi [Phys. Rev. A 78, 012310 (2008)]. We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.
We investigate the spatial search problem on the two-dimensional square lattice, using the Dirac evolution operator discretized 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 behavior. As a result, the construction used in our accompanying article [ A. Patel and M. A. Rahaman Phys. Rev. A 82 032330 (2010)] provides an O(√NlnN) algorithm, which is not optimal. The scaling behavior can be improved to O(√NlnN) by cleverly controlling the massless Dirac evolution operator by an ancilla qubit, as proposed by Tulsi Phys. Rev. A 78 012310 (2008). We reinterpret the ancilla control as introduction of an effective mass at the marked vertex, and optimize the proportionality constants of the scaling behavior of the algorithm by numerically tuning the parameters.
Random walks describe diffusion processes, where movement at every time step is restricted to only the neighboring locations. We construct a quantum random walk algorithm, based on discretization of the Dirac evolution operator inspired by staggered lattice fermions. We use it to investigate the spatial search problem, that is, to find a marked vertex on a ddd-dimensional hypercubic lattice. The restriction on movement hardly matters for d>2d>2d>2, and scaling behavior close to Grover's optimal algorithm (which has no restriction on movement) can be achieved. Using numerical simulations, we optimize the proportionality constants of the scaling behavior, and demonstrate the approach to that for Grover's algorithm (equivalent to the mean-field theory or the $d\ensuremath{\rightarrow}\ensuremath{\infty}$ limit). In particular, the scaling behavior for d=3d=3d=3 is only about 2525%25 higher than the optimal $d\ensuremath{\rightarrow}\ensuremath{\infty}$ value.
We consider the problem of searching a ddd-dimensional lattice of NNN sites for a single marked location. We present a Hamiltonian that solves this problem in time of order N\sqrt{N}N​ for d>2d>2d>2 and of order NlogN\sqrt{N}\phantom{\rule{0.3em}{0ex}}\mathrm{log}\phantom{\rule{0.3em}{0ex}}NN​logN in the critical dimension d=2d=2d=2. This improves upon the performance of our previous quantum walk search algorithm (which has a critical dimension of d=4d=4d=4), and matches the performance of a corresponding discrete-time quantum walk algorithm. The improvement uses a lattice version of the Dirac Hamiltonian, and thus requires the introduction of spin (or coin) degrees of freedom.
The spatial search problem on regular lattice structures in integer number of dimensions $d\ensuremath{\ge}2$ has been studied extensively, using both coined and coinless quantum walks. The relativistic Dirac operator has been a crucial ingredient in these studies. Here, we investigate the spatial search problem on fractals of noninteger dimensions. Although the Dirac operator cannot be defined on a fractal, we construct the quantum walk on a fractal using the flip-flop operator that incorporates a Klein-Gordon mode. We find that the scaling behavior of the spatial search is determined by the spectral (and not the fractal) dimension. Our numerical results have been obtained on the well-known Sierpinski gaskets in two and three dimensions.
We consider the problem of searching a general ddd-dimensional lattice of NNN vertices for a single marked item using a continuous-time quantum walk. We demand locality, but allow the walk to vary periodically on a small scale. By constructing lattice Hamiltonians exhibiting Dirac points in their dispersion relations and exploiting the linear behavior near a Dirac point, we develop algorithms that solve the problem in a time of O(N)O(\sqrt{N})O(N​) for d>2d>2d>2 and O(NlogN)O(\sqrt{N}\phantom{\rule{0.16em}{0ex}}logN)O(N​logN) in d=2d=2d=2. In particular, we show that such algorithms exist even for hypercubic lattices in any dimension. Unlike previous continuous-time quantum walk algorithms on hypercubic lattices in low dimensions, our approach does not use external memory.