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

Quantum walks and quantum search on graphene lattices

Iain Foulger, Sven Gnutzmann∥, Gregor Tanner

Published Jun 18, 2015• 28 citations
arXivHTMLPDF

Abstract

Quantum walks have been very useful in developing search algorithms in quantum information, in particular for devising of spatial search algorithms. However, the construction of continuous-time quantum search algorithms in two-dimensional lattices has proved difficult, requiring additional degrees of freedom. Here, we demonstrate that a continuous-time quantum walk search is possible in two dimensions by changing the search topology to a graphene lattice, utilizing the Dirac point in the energy spectrum. This is made possible by making a change to standard methods of marking a particular site in the lattice. Various ways of marking a site are shown to result in successful search protocols. We further establish that the search can be adapted to transfer probability amplitude across the lattice between specific lattice sites thus establishing a line of communication between these sites.

DOI
10.1103/physreva.91.062323

Related papers

Quantum Search on Graphene Lattices

Iain Foulger, Sven Gnutzmann∥, Gregor Tanner

We present a continuous-time quantum search algorithm on a graphene lattice. This provides the sought-after implementation of an efficient continuous-time quantum search on a two-dimensional lattice. The search uses the linearity of the dispersion relation near the Dirac point and can find a marked site on a graphene lattice faster than the corresponding classical search. The algorithm can also be used for state transfer and communication.

arXiv:1312.3852•Physical Review Letters•Feb 21, 2014•33 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 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

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 Spatial Search in Two-Dimensional Waveguide Arrays

Claudia Benedetti, Dario Tamascelli, Matteo G. A. Paris +1 more

Continuous-time quantum walks (CTQWs) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using two-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.

arXiv:2106.03867•Physical Review Applied•Nov 18, 2021•22 citations

Microwave Experiments Simulating Quantum Search and Directed Transport in Artificial Graphene

Julian Böhm, Matthieu Bellec, Fabrice Mortessagne +7 more

A series of quantum search algorithms have been proposed recently providing an algebraic speedup compared to classical search algorithms from N to √N, where N is the number of items in the search space. In particular, devising searches on regular lattices has become popular in extending Grover's original algorithm to spatial searching. Working in a tight-binding setup, it could be demonstrated, theoretically, that a search is possible in the physically relevant dimensions 2 and 3 if the lattice spectrum possesses Dirac points. We present here a proof of principle experiment implementing wave search algorithms and directed wave transport in a graphene lattice arrangement. The idea is based on bringing localized search states into resonance with an extended lattice state in an energy region of low spectral density-namely, at or near the Dirac point. The experiment is implemented using classical waves in a microwave setup containing weakly coupled dielectric resonators placed in a honeycomb arrangement, i.e., artificial graphene. Furthermore, we investigate the scaling behavior experimentally using linear chains.

arXiv:1409.2382•Physical Review Letters•Mar 17, 2015•30 citations
Quantum walks have been very useful in developing search algorithms in quantum information, in particular for devising of spatial search algorithms. However, the construction of continuous-time quantum search algorithms in two-dimensional lattices has proved difficult, requiring additional degrees of freedom. Here, we demonstrate that a continuous-time quantum walk search is possible in two dimensions by changing the search topology to a graphene lattice, utilizing the Dirac point in the energy spectrum. This is made possible by making a change to standard methods of marking a particular site in the lattice. Various ways of marking a site are shown to result in successful search protocols. We further establish that the search can be adapted to transfer probability amplitude across the lattice between specific lattice sites thus establishing a line of communication between these sites.
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.
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.
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.
Continuous-time quantum walks (CTQWs) have shown the capability to perform efficiently the spatial search of a marked site on many kinds of graphs. However, most of such graphs are hard to realize in an experimental setting. Here we study CTQW spatial search on a planar triangular lattice by means of both numerical simulations and experiments. The experiments are performed using two-dimensional waveguide arrays fabricated by femtosecond laser pulses, illuminated by coherent light. We show that the retrieval of the marked site by the quantum walker is accomplished with higher probability than the classical counterpart, in a convenient time window placed early in the evolution.
A series of quantum search algorithms have been proposed recently providing an algebraic speedup compared to classical search algorithms from N to √N, where N is the number of items in the search space. In particular, devising searches on regular lattices has become popular in extending Grover's original algorithm to spatial searching. Working in a tight-binding setup, it could be demonstrated, theoretically, that a search is possible in the physically relevant dimensions 2 and 3 if the lattice spectrum possesses Dirac points. We present here a proof of principle experiment implementing wave search algorithms and directed wave transport in a graphene lattice arrangement. The idea is based on bringing localized search states into resonance with an extended lattice state in an energy region of low spectral density-namely, at or near the Dirac point. The experiment is implemented using classical waves in a microwave setup containing weakly coupled dielectric resonators placed in a honeycomb arrangement, i.e., artificial graphene. Furthermore, we investigate the scaling behavior experimentally using linear chains.