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:1612.08958 · Leibniz international proceedings in informatics

Efficient Quantum Walk on the Grid with Multiple Marked Elements

Peter Høyer, Mojtaba Komeili

Published Dec 28, 2016• 6 citations
arXivHTMLPDF

Abstract

We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.

DOI
10.4230/lipics.stacs.2017.42

Related papers

Quantum walk on two-dimensional torus and grid

Mojtaba Komeili

Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.

•May 28, 2018•1 citation

Quadratic speedup for finding marked vertices by Quantum walks

Andris Ambainis, András Gilyén, Stacey Jeffery +1 more

A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.

arXiv:1903.07493•ACM Symposium on Theory of Computing (STOC)•Jun 7, 2020•45 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

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•3 citations

The hitting time of quantum walk on 2D lattice

Qi Han, Ning Bai, Huan Wang +2 more

The hitting time, which refers to the time required to find the marked element in the search algorithm, is one of the most interesting properties of quantum walk. In this paper we briefly analyze the hitting time on a finite 2D lattice in the classical case, focusing on the quantum version of the hitting time and give specific expressions for each. It is well known that the quantum hitting time has the same order as the square of the classical case, and our work also happens to verify this particular property.

International Journal of Quantum Information•Nov 3, 2023•1 citation

Quantum-walk-based search algorithms with multiple marked vertices

Gustavo Alves Bezerra, Pedro H. G. Lugão, Renato Portugal

The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.

arXiv:2103.12878•Physical Review A•Jun 1, 2021•22 citations
We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.
Let χ be a function that maps the vertices of a graph to zero or one. We want to find a vertex m, called a marked vertex, such that χ(m) = 1. Random walk is an algorithm for finding such a vertex. The measure of complexity for random walk is hitting time. There is a quantum algorithm that finds a marked vertex, and runs in the square root of the extended hitting time. For some configurations of marked vertices on certain graphs, the extended hitting time is asymptotically larger than the hitting time. This might cause the quantum algorithm for finding to be less efficient than a random walk. Two-dimensional torus and grid are canonical examples of such graphs. This thesis is about efficient quantum algorithms for finding a marked vertex on a two-dimensional torus. We prove the convexity of the extended hitting time, and provide a new upper bound on it. We show that, with a probability that is more than a constant, random walk on a torus is localized, and it is restricted to a sub-graph of the torus. From these observations, we introduce two algorithms that find a marked vertex on a torus. The complexity of these algorithms is in the order of the square root of the hitting time, up to logarithmic factors. They both start by finding an estimate to the hitting time. Using that, they estimate the size of a sub-graph that contains a marked vertex with more than a constant probability, and sample such a sub-graph. Our first algorithm finds a marked vertex on this sub-graph by using a quantum algorithm that runs in extended hitting time, and finds a marked vertex with probability at least a constant. Our second algorithm recursively runs the detection algorithm on cuts of the sub-graph, until reaching a constant sized sub-graph that contains a marked vertex. These algorithms are the first quantum algorithms that achieve close-to-quadratic speed-up in quantum walk on a two-dimensional torus, for all configurations of marked vertices.
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
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 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 hitting time, which refers to the time required to find the marked element in the search algorithm, is one of the most interesting properties of quantum walk. In this paper we briefly analyze the hitting time on a finite 2D lattice in the classical case, focusing on the quantum version of the hitting time and give specific expressions for each. It is well known that the quantum hitting time has the same order as the square of the classical case, and our work also happens to verify this particular property.
The quantum walk is a powerful tool to develop quantum algorithms, which usually are based on searching for a vertex in a graph with multiple marked vertices, with Ambainis's quantum algorithm for solving the element distinctness problem being the most shining example. In this work, we address the problem of calculating analytical expressions of the time complexity of finding a marked vertex using quantum-walk-based search algorithms with multiple marked vertices on arbitrary graphs, extending previous analytical methods based on Szegedy's quantum walk, which can be applied only to bipartite graphs. Two examples based on the coined quantum walk on two-dimensional lattices and hypercubes show the details of our method.