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.0065 · Physical Review A

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

Apoorva D. Patel, Md. Aminoor Rahaman

Published Sep 28, 2010• 35 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.82.032330

Related papers

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

Apoorva D. Patel, K. S. Raghunathan, 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(\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.

arXiv:1003.5564•Physical Review A•Sep 28, 2010•23 citations

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

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

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

Spatial search on a two-dimensional lattice with long-range interactions

Tomo Osada, Kaoru Sanaka, William J. Munro +1 more

Quantum-walk-based algorithms that search a marked location among $N$ locations on a $d$-dimensional lattice succeeds in time $O(\sqrt{N})$ for $d>2$, while this is not found to be possible when $d=2$. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points $i$ and $j$ apart by a distance $|i\ensuremath{-}j|$ is added by probability ${p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)$. Through numerical analysis, we found that the search succeeds in time $O(\sqrt{N})$ when $\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1$. For $\ensuremath{\alpha}>2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\ensuremath{\rightarrow}\ensuremath{\infty}$, which means that search time of $O(\sqrt{N})$ is achieved on a graph with average degree scaling as a constant.

Physical Review A•Jun 11, 2018•10 citations

Quantum search on the two-dimensional lattice using the staggered model with Hamiltonians

Renato Portugal, Tharso D. Fernandes

Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.

arXiv:1701.01468•Physical Review A•Apr 26, 2017•19 citations
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→\ensuremath∞d\ensuremath{\rightarrow}\ensuremath{\infty}d\ensuremath→\ensuremath∞ limit). In particular, the scaling behavior for d=3d=3d=3 is only about 2525%25 higher than the optimal d\ensuremath→\ensuremath∞d\ensuremath{\rightarrow}\ensuremath{\infty}d\ensuremath→\ensuremath∞ value.
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.
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.
Quantum-walk-based algorithms that search a marked location among NNN locations on a ddd-dimensional lattice succeeds in time O(N)O(\sqrt{N})O(N​) for d>2d>2d>2, while this is not found to be possible when d=2d=2d=2. In this paper, we consider a spatial search algorithm using continuous-time quantum walk on a two-dimensional square lattice with the existence of additional long-range edges. We examined such a search on a probabilistic graph model where an edge connecting non-nearest-neighbor lattice points iii and jjj apart by a distance $|i\ensuremath{-}j|$ is added by probability ${p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)$. Through numerical analysis, we found that the search succeeds in time O(N)O(\sqrt{N})O(N​) when $\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1$. For $\ensuremath{\alpha}>2$, the expectation value of the additional long-range edges on each node scales as a constant when $N\ensuremath{\rightarrow}\ensuremath{\infty}$, which means that search time of O(N)O(\sqrt{N})O(N​) is achieved on a graph with average degree scaling as a constant.
Quantum search on the two-dimensional lattice with one marked vertex and cyclic boundary conditions is an important problem in the context of quantum algorithms with an interesting unfolding. It avails to test the ability of quantum walk models to provide efficient algorithms from the theoretical side and means to implement quantum walks in laboratories from the practical side. In this paper, we rigorously prove that the recent-proposed staggered quantum walk model provides an efficient quantum search on the two-dimensional lattice, if the reflection operators associated with the graph tessellations are used as Hamiltonians, which is an important theoretical result for validating the staggered model with Hamiltonians. Numerical results show that on the two-dimensional lattice staggered models without Hamiltonians are not as efficient as the one described in this paper and are, in fact, as slow as classical random-walk-based algorithms.