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:1005.3676 · Physical Review A

Quantum search algorithms on a regular lattice

Birgit Hein, Gregor Tanner

Published Jul 23, 2010• 40 citations
arXivHTMLPDF

Abstract

Quantum algorithms for searching for one or more marked items on a $d$-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For $d=2$ and $d=3$, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.

DOI
10.1103/physreva.82.012326

Related papers

Quantum search algorithms on the hypercube

Birgit Hein, Gregor Tanner

We investigate a set of discrete-time quantum search algorithms on the n -dimensional hypercube following a proposal by Shenvi et al (2003 Phys. Rev. A 67 052307). We show that there exists a whole class of quantum search algorithms in the symmetry-reduced space which perform a search of a marked vertex in time of order where N = 2 n , the number of vertices. In analogy to Grover's algorithm, the spatial search is effectively facilitated through a rotation in a two-level subspace of the full Hilbert space. In the hypercube, these two-level systems are introduced through avoided crossings. We give estimates on the quantum states forming the two-level subspaces at the avoided crossings and derive improved estimates on the search times.

arXiv:0906.3094•Journal of Physics A Mathematical and Theoretical•Jan 30, 2009•26 citations

Quantum search algorithms

Birgit Hein

In this thesis two quantum search algorithms on two different graphs, a hypercube and a d-dimensional square lattice, are analysed and some applications of the lattice search are discussed.\nThe approach in this thesis generalises a picture drawn by Shenvi, Kempe and Whaley, which was later adapted by Ambainis, Kempe and Rivosh. It defines a one parameter family of unitary operators U_λ with parameter λ. It will be shown that two eigenvalues of U_λ form an avoided crossing at the λ-value where U_λ is equal to the old search operator.\nThis generalised picture opens the way for a construction of two approximate eigen- vectors at the crossing and gives rise to a 2×2 model Hamiltonian that is used to approximate the operator U_λ near the crossing. The thus defined Hamiltonian can be used to calculate the leading order of search time and success probability for the search. To the best of my knowledge only the scaling of these quantities has been known.\nFor the algorithm searching the regular lattice, a generalisation of the model Hamiltonian for m target vertices is constructed. This algorithm can be used to send a signal from one vertex of the graph to a set of vertices. The signal is transmitted between these vertices exclusively and is localised only on the sender and the receiving vertices while the probability to measure the signal at one of the remaining vertices is significantly smaller.\nHowever, this effect can be used to introduce an additional sender to search settings and send a continuous signal to all target vertices where the signal will localise. This effect is an improvement compared to the original search algorithm as it does not need to know the number of target vertices.

•Oct 15, 2010•0 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

Generalized quantum walk search algorithm

Pulak Ranjan Giri

Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.

International Journal of Quantum Information•Jul 24, 2026•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

Spatial search by quantum walk

Andrew M. Childs, Jeffrey Goldstone

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of $N$ items laid out in $d$ spatial dimensions can be searched in time of order $\sqrt{N}$ for $d>2$, and in time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$ for $d=2$. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that $\sqrt{N}$ speedup can also be achieved on the hypercube. We show that full $\sqrt{N}$ speedup can be achieved on a $d$-dimensional periodic lattice for $d>4$. In $d=4$, the quantum walk search algorithm takes time of order $\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)$, and in $d<4$, the algorithm does not provide substantial speedup.

arXiv:quant-ph/0306054•Physical Review A•Aug 23, 2004•726 citations
Quantum algorithms for searching for one or more marked items on a ddd-dimensional lattice provide an extension of Grover's search algorithm including a spatial component. We demonstrate that these lattice search algorithms can be viewed in terms of the level dynamics near an avoided crossing of a one-parameter family of quantum random walks. We give approximations for both the level splitting at the avoided crossing and the effectively two-dimensional subspace of the full Hilbert space spanning the level crossing. This makes it possible to give the leading order behavior for the search time and the localization probability in the limit of large lattice size including the leading order coefficients. For d=2d=2d=2 and d=3d=3d=3, these coefficients are calculated explicitly. Closed form expressions are given for higher dimensions.
We investigate a set of discrete-time quantum search algorithms on the n -dimensional hypercube following a proposal by Shenvi et al (2003 Phys. Rev. A 67 052307). We show that there exists a whole class of quantum search algorithms in the symmetry-reduced space which perform a search of a marked vertex in time of order where N = 2 n , the number of vertices. In analogy to Grover's algorithm, the spatial search is effectively facilitated through a rotation in a two-level subspace of the full Hilbert space. In the hypercube, these two-level systems are introduced through avoided crossings. We give estimates on the quantum states forming the two-level subspaces at the avoided crossings and derive improved estimates on the search times.
In this thesis two quantum search algorithms on two different graphs, a hypercube and a d-dimensional square lattice, are analysed and some applications of the lattice search are discussed.\nThe approach in this thesis generalises a picture drawn by Shenvi, Kempe and Whaley, which was later adapted by Ambainis, Kempe and Rivosh. It defines a one parameter family of unitary operators U_λ with parameter λ. It will be shown that two eigenvalues of U_λ form an avoided crossing at the λ-value where U_λ is equal to the old search operator.\nThis generalised picture opens the way for a construction of two approximate eigen- vectors at the crossing and gives rise to a 2×2 model Hamiltonian that is used to approximate the operator U_λ near the crossing. The thus defined Hamiltonian can be used to calculate the leading order of search time and success probability for the search. To the best of my knowledge only the scaling of these quantities has been known.\nFor the algorithm searching the regular lattice, a generalisation of the model Hamiltonian for m target vertices is constructed. This algorithm can be used to send a signal from one vertex of the graph to a set of vertices. The signal is transmitted between these vertices exclusively and is localised only on the sender and the receiving vertices while the probability to measure the signal at one of the remaining vertices is significantly smaller.\nHowever, this effect can be used to introduce an additional sender to search settings and send a continuous signal to all target vertices where the signal will localise. This effect is an improvement compared to the original search algorithm as it does not need to know the number of target vertices.
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.
Quantum walk search on graphs is primarily limited to real evolution operators, although there is no restriction for using the complex unitary matrix as the evolution operator. In the context of quantum search, several studies on the Grover’s search utilize the complex unitary matrix as an evolution operator, which allows for efficient searching of marked elements. However, the generalization of the quantum walk search to complex space has largely been overlooked. In this paper, we extend existing discrete-time coined quantum walk search algorithms on one- and two-dimensional periodic lattices to complex space by introducing two phase parameters, [Formula: see text], and [Formula: see text], into the coin and oracle operators, respectively, for four different discrete-time coined quantum walk search algorithms. One of the advantages of this generalization is that it enables the Grover and SKW coins with specific values of the phase parameters [Formula: see text], and [Formula: see text] to search for the exceptional configurations on a two-dimensional periodic lattice with high success probability, which is otherwise impossible to search using the real Grover and SKW coins operators.
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.
Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of NNN items laid out in ddd spatial dimensions can be searched in time of order N\sqrt{N}N​ for d>2d>2d>2, and in time of order Npoly(logN)\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)N​poly(logN) for d=2d=2d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that N\sqrt{N}N​ speedup can also be achieved on the hypercube. We show that full N\sqrt{N}N​ speedup can be achieved on a ddd-dimensional periodic lattice for d>4d>4d>4. In d=4d=4d=4, the quantum walk search algorithm takes time of order Npoly(logN)\sqrt{N}\phantom{\rule{0.3em}{0ex}}\text{poly}(\mathrm{log}\phantom{\rule{0.3em}{0ex}}N)N​poly(logN), and in d<4d<4d<4, the algorithm does not provide substantial speedup.