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

Physical Review A

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

Tomo Osada, Kaoru Sanaka, William J. Munro, Kae Nemoto

Published Jun 11, 2018• 10 citations
Publisher

Abstract

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.

DOI
10.1103/physreva.97.062319

Related papers

Optimal spatial searches with long-range tunneling

Emma C. King, Moritz Linnebacher, Peter P. Orth +2 more

A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of d > 4 dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.

arXiv:2501.08148•Physical Review Research•Jul 8, 2025•4 citations

Spatial search via non-linear quantum walk

Mahdi Ebrahimi Kahou

One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.

•Jan 1, 2013•1 citation

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

Optimal Quantum Spatial Search with One-Dimensional Long-Range Interactions

Dylan Lewis, Asmae Benhemou, Natasha Feinstein +2 more

Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(sqrt[n]) time for n entries. However, the capability of models found in nature is largely unexplored-e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(sqrt[n]) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/r^{α} with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.

arXiv:2010.04299•Physical Review Letters•Jun 17, 2021•0 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

Optimal Quantum Spatial Search with One-Dimensional Long-Range Interactions

Dylan Lewis, Asmae Benhemou, Natasha Feinstein +2 more

Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(n) time for n entries. However, the capability of models found in nature is largely unexplored - e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(n) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/rα with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.

•Jan 1, 2021•16 citations
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∣|i\ensuremath{-}j|∣i\ensuremath−j∣ is added by probability pij=∣i\ensuremath−j∣\ensuremath−\ensuremathα(\ensuremathα\ensuremath≥0){p}_{ij}={|i\ensuremath{-}j|}^{\ensuremath{-}\ensuremath{\alpha}}\phantom{\rule{1em}{0ex}}(\ensuremath{\alpha}\ensuremath{\ge}0)pij​=∣i\ensuremath−j∣\ensuremath−\ensuremathα(\ensuremathα\ensuremath≥0). Through numerical analysis, we found that the search succeeds in time O(N)O(\sqrt{N})O(N​) when \ensuremathα\ensuremath≤\ensuremathαc=2.4\ifmmode±\else\textpm\fi0.1\ensuremath{\alpha}\ensuremath{\le}{\ensuremath{\alpha}}_{c}=2.4\ifmmode\pm\else\textpm\fi{}0.1\ensuremathα\ensuremath≤\ensuremathαc​=2.4\ifmmode±\else\textpm\fi0.1. For \ensuremathα>2\ensuremath{\alpha}>2\ensuremathα>2, the expectation value of the additional long-range edges on each node scales as a constant when N\ensuremath→\ensuremath∞N\ensuremath{\rightarrow}\ensuremath{\infty}N\ensuremath→\ensuremath∞, 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.
A quantum walk on a lattice is a paradigm of a quantum search in a database. The database qubit strings are the lattice sites, qubit rotations are tunneling events, and the target site is tagged by an energy shift. For quantum walks on a continuous time, the walker diffuses across the lattice and the search ends when it localizes at the target site. The search time T can exhibit Grover's optimal scaling with the lattice size N , namely, T ∼ N , on an all-connected, complete lattice. For finite-range tunneling between sites, instead, Grover's optimal scaling is warranted when the lattice is a hypercube of d > 4 dimensions. Here, we show that Grover's optimum can be reached in lower dimensions on lattices of long-range interacting particles, when the interaction strength scales algebraically with the distance r as 1 / r α and 0 < α < 3 d / 2 . For α < d the dynamics mimics the one of a globally connected graph. For d < α < d + 2 , the quantum search on the graph can be mapped to a short-range model on a hypercube with spatial dimension d s = 2 d / ( α − d ) , indicating that the search is optimal for d s > 4 . Our work identifies an exact relation between criticality of long-range and short-range systems, it provides a quantitative demonstration of the resources that long-range interactions provide for quantum technologies, and indicates when existing experimental platforms can implement efficient analog quantum search algorithms.
One approach to the development of quantum search algorithms is the quantum walk. A spatial search can be effected by the continuous-time evolution of a single quantum particle on a lattice or graph containing a marked site. In most conceivable physical applications, however, one would rather expect to have multiple interacting particles. In bosonic systems at zero temperature, the dynamics would be well-described by a discrete non-linear Schrodinger equation. In this thesis we investigate the role of non-linearity in determining the efficiency of the spatial search algorithm within the quantum walk model, for the complete graph. Our analytical results indicate that the search time for this non-linear quantum search scales with size of the database N like square root of N, equivalent to linear spatial search time. The analytical results will be compared with numerical calculations of multiple interacting quantum walkers.
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.
Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(sqrt[n]) time for n entries. However, the capability of models found in nature is largely unexplored-e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(sqrt[n]) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/r^{α} with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.
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.
Continuous-time quantum walks can be used to solve the spatial search problem, which is an essential component for many quantum algorithms that run quadratically faster than their classical counterpart, in O(n) time for n entries. However, the capability of models found in nature is largely unexplored - e.g., in one dimension only nearest-neighbor Hamiltonians have been considered so far, for which the quadratic speedup does not exist. Here, we prove that optimal spatial search, namely with O(n) run time and high fidelity, is possible in one-dimensional spin chains with long-range interactions that decay as 1/rα with distance r. In particular, near unit fidelity is achieved for α≈1 and, in the limit n→∞, we find a continuous transition from a region where optimal spatial search does exist (α<1.5) to where it does not (α>1.5). Numerically, we show that spatial search is robust to dephasing noise and that, for reasonable chain lengths, α≲1.2 should be sufficient to demonstrate optimal spatial search experimentally with near unit fidelity.