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:1312.0172 · Quantum Information and Computation

Spatial search on grids with minimum memory

Andris Ambainis, Renato Portugal, Nikolay Nahimov

Published Oct 1, 2015• 26 citations
arXivHTMLPDF

Abstract

We study quantum algorithms for spatial search on finite dimensional grids. Patel \textit{et al.}~and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.

DOI
10.26421/qic15.13-14-9

Related papers

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

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•5 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 Analogs of Markov Chains

Ashwin Nayak, Peter C. Richter

Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:

•Jan 1, 2015•1 citation

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 (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple 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 [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.

International Journal of Foundations of Computer Science•Jun 1, 2018•4 citations

Multimarked Spatial Search by Continuous-Time Quantum Walk

Pedro H. G. Lugão, Renato Portugal, Mohamed Sabri +1 more

The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is \(O(\sqrt {N})\) with an asymptotic probability of 1+ o (1), where N is the number of vertices.

arXiv:2203.14384•ACM Transactions on Quantum Computing•Nov 27, 2024•8 citations
We study quantum algorithms for spatial search on finite dimensional grids. Patel \textit{et al.}~and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is O(Nlog⁡N)O(\sqrt{N\log N})O(NlogN​) and the success probability is O(1/log⁡N)O(1/\log N)O(1/logN), where NNN is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.
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.
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.
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.
Spatial search and walk processes. Spatial search by quantum walk is database search with the additional constraint that one is required to move through the search space that obeys some locality structure. For example, the data items may be stored at the vertices of a two-dimensional grid. The requirement of moves along the edges of the grid captures the cost of accessing different items starting from some fixed position in the database. One of possible ways of carrying out spatial search is by performing a random walk on the search space or its quantum analog, a quantum walk. The complexity of spatial search by quantum walk is strongly tied to the quantum hitting time [19] of the walk. Let S , with jS j D n, be a finite set of states. Assume that a subset M S of states are marked. We are given a procedure C that, on input x 2 S and an associated data structure d.x/, checks whether the state x is marked. The goal is either to find a marked state when promised that M ¤ ; (search version) or to determine whether M is nonempty (decision version). The algorithm progresses in stages. In the setup stage, we access some state of S (usually a random state). In the walk stage we move from state to state, performing a spatial walk as described below. The moves are called updates. In addition, in the walk stage we perform checks to see if the current state is marked at steps selected by the algorithm. In the classical setting, the transition probabilities of the spatial walk are described by a stochastic matrix P D .px;y/x;y2S . This makes the walk a Markov chain. In every move the algorithm must perform a random transition according to P . The possible x ! y moves, i.e., those with px;y ¤ 0, form the edges of a (directed) graph G, and we say that the Markov chain P has locality structure G. We define the search problem in the classical setting, which carries over to the quantum case with little modification:
The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple 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 [Formula: see text] marked locations for which the number of steps of the algorithm differs by a factor of [Formula: see text]. Second, we present two configurations of [Formula: see text] and [Formula: see text] marked locations having the same number of steps and probability of finding a marked location.
The quantum-walk-based spatial search problem aims to find a marked vertex using a quantum walk on a graph with marked vertices. We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs by providing a recipe for finding the optimal running time and the success probability of the algorithm. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices. The success of our framework depends on the knowledge of the eigenvalues and eigenvectors of the adjacency matrix. The spectrum of the Hamiltonian is subsequently obtained from the roots of the determinant of a real symmetric matrix M , the dimensions of which depend on the number of marked vertices. The eigenvectors are determined from a basis of the kernel of M . We show each step of the framework by solving the spatial searching problem on the Johnson graphs with a fixed diameter and with two marked vertices. Our calculations show that the optimal running time is O(N)O(\sqrt {N})O(N​) with an asymptotic probability of 1+ o (1), where N is the number of vertices.