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:1001.1139 · Mathematical Structures in Computer Science

Spatial search on a honeycomb network

Gonzalo Abal, R. DONANGELO, Franklin de Lima Marquezino, R. PORTUGAL

Published Nov 8, 2010• 44 citations
arXivHTMLPDF

Abstract

The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is $O(\sqrt{N \log N})$ .

DOI
10.1017/s0960129510000332

Related papers

Spatial quantum search in a triangular network

Gonzalo Abal, R. Donangelo, Marcelo Forets +1 more

The spatial search problem consists of minimising the number of steps required to find a given site in a network, with the restriction that only an oracle query or a translation to a neighbouring site is allowed at each step. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algorithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh (AKR) in Ambainis et al. (2005) and Tulsi in Tulsi (2008) applied to a triangular network. The AKR–Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is $O(\sqrt{N \log N})$ .

arXiv:1009.1422•Mathematical Structures in Computer Science•Feb 9, 2012•20 citations

Scaling hypothesis of a spatial search on fractal lattices using a quantum walk

Rei Sato, Tetsuro Nikuni, Shohei Watabe

A quantum spatial search problem on fractal lattices, such as Sierpinski carpets and Menger sponges, is studied numerically. The results confirmed various conjectures on the relationship between the number of oracle calls needed for a search with respect to the number of sites and spatial dimensions.

arXiv:1908.11827•Physical Review A•Feb 10, 2020•9 citations

Faster quantum-walk algorithm for the two-dimensional spatial search

Avatar Tulsi

We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.

arXiv:0801.0497•Physical Review A•Jul 9, 2008•185 citations

Improving quantum spatial search in two dimensions

Abhijith Jayakumar, Apoorva D. Patel

The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.

Quantum Information and Computation•Jun 1, 2019•0 citations

Quantum walks on two-dimensional grids with multiple marked locations

Nikolajs Nahimovs, Alexander Rivosh

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of $k$ marked locations for which the number of steps of the algorithm differs by $Ω(\sqrt{k})$ factor. Second, we present two configurations of $k$ and $\sqrt{k}$ marked locations having the same number of steps and probability to find a marked location.

arXiv:1507.03788•Jul 14, 2015•3 citations

Spatial search on Johnson graphs by discrete-time quantum walk

Hajime Tanaka, Mohamed Sabri, Renato Portugal

Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.

arXiv:2112.03744•Journal of Physics A Mathematical and Theoretical•May 12, 2022•9 citations
The spatial search problem consists of minimising the number of steps required to find a given site in a network under the restriction that only oracle queries or translations to neighbouring sites are allowed. We propose a quantum algorithm for the spatial search problem on a honeycomb lattice withNsites and torus-like boundary conditions. The search algorithm is based on a modified quantum walk on an hexagonal lattice and the general framework proposed by Ambainis, Kempe and Rivosh (Ambainiset al. 2005) is employed to show that the time complexity of this quantum search algorithm is O(Nlog⁡N)O(\sqrt{N \log N})O(NlogN​) .
The spatial search problem consists of minimising the number of steps required to find a given site in a network, with the restriction that only an oracle query or a translation to a neighbouring site is allowed at each step. We propose a quantum algorithm for the spatial search problem on a triangular lattice with N sites and torus-like boundary conditions. The proposed algorithm is a special case of the general framework for abstract search proposed by Ambainis, Kempe and Rivosh (AKR) in Ambainis et al. (2005) and Tulsi in Tulsi (2008) applied to a triangular network. The AKR–Tulsi formalism was employed to show that the time complexity of the quantum search on the triangular lattice is O(Nlog⁡N)O(\sqrt{N \log N})O(NlogN​) .
We consider the problem of finding a desired item out of NNN items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take O(N ln N)O(\sqrt{N}\text{ }\text{ln}\text{ }N)O(N​ ln N) steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in O(N ln N)O(\sqrt{N\text{ }\text{ln}\text{ }N})O(N ln N​) steps, thus giving an O(ln N)O(\sqrt{\text{ln}\text{ }N})O(ln N​) improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.
The question of whether quantum spatial search in two dimensions can be made optimal has long been an open problem. We report progress towards its resolution by showing that the oracle complexity for target location can be made optimal, by increasing the number of calls to the walk operator that incorporates the graph structure by a logarithmic factor. Our algorithm does not require amplitude amplification. An important ingredient of our algorithm is the implementation of multi-step quantum walks by graph powering, using a coin space of walk-length dependent dimension, which may be of independent interest. Finally, we demonstrate how to implement quantum walks arising from powers of symmetric Markov chains using our methods.
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration of marked locations. While the first dependence have been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [AKR05]. The original paper analyses one and two marked location cases only. We move beyond two marked locations and study the behaviour of the algorithm for an arbitrary configuration of marked locations. In this paper we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of kkk marked locations for which the number of steps of the algorithm differs by Ω(k)Ω(\sqrt{k})Ω(k​) factor. Second, we present two configurations of kkk and k\sqrt{k}k​ marked locations having the same number of steps and probability to find a marked location.
Abstract The spatial search problem aims to find a marked vertex of a finite graph using a dynamic with two constraints: (1) the walker has no compass and (2) the walker can check whether a vertex is marked only after reaching it. This problem is a generalization of unsorted database search and has many applications to algorithms. Classical algorithms that solve the spatial search problem are based on random walks and the computational complexity is determined by the hitting time. On the other hand, quantum algorithms are based on quantum walks and the computational complexity is determined not only by the number of steps to reach a marked vertex, but also by the success probability, since we need to perform a measurement at the end of the algorithm to determine the walker’s position. In this work, we address the spatial search problem on Johnson graphs using the coined quantum walk model. Since Johnson graphs are vertex- and distance-transitive, we have found an invariant subspace of the Hilbert space, which aids in the calculation of the computational complexity. We have shown that, for every fixed diameter, the asymptotic success probability is 1/2 after taking π N / ( 2 2 ) steps, where N is the number of vertices of the Johnson graph.