Quantum walks on two-dimensional grids with multiple marked locations

DOI10.1007/978-3-662-49192-8_31MaRDI QIDQ5890528zbMATHOpenAlexFDO

Authors Nikolajs Nahimovs, Alexander Rivosh

Publication date 10 March 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.03788

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: 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 $Omega(sqrtk)$ factor. Second, we present two configurations of $k$ and $sqrtk$ marked locations having the same number of steps and probability to find a marked location.

Recommendations

• Quantum walks on two-dimensional grids with multiple marked locations
• Adjacent vertices can be hard to find by quantum walks
• Adjacent vertices can be hard to find by quantum walks
• Quantum Walks with Multiple or Moving Marked Locations
• Efficient quantum walk on the grid with multiple marked elements

Cited in

(15)

• Quantum walk search on a two-dimensional grid with extra edges
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Efficient quantum walk on the grid with multiple marked elements
• 有限偶圈图上的 2-嵌入交错量子游荡
• Quantum Walks with Multiple or Moving Marked Locations
• Upperbounds on the probability of finding marked connected components using quantum walks
• Equivalence of Szegedy's and coined quantum walks
• Quantum walks on two-dimensional grids with multiple marked locations
• Exceptional quantum walk search on the cycle
• Lackadaisical quantum walks with multiple marked vertices
• Faster search of clustered marked states with lackadaisical quantum walks
• Adjacent vertices can be hard to find by quantum walks
• scientific article; zbMATH DE number 7453158 (Why is no real title available?)
• Quantum walk search for exceptional configurations
• Search by quantum walks on two-dimensional grid without amplitude amplification

This page was built for publication: Quantum walks on two-dimensional grids with multiple marked locations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5890528)