Quantum Walks on Two-Dimensional Grids with Multiple Marked Locations

DOI10.1007/978-3-662-49192-8_31zbMATH Open1397.68080arXiv1507.03788OpenAlexW926816759MaRDI QIDQ5890528FDOQ5890528

Nikolajs Nahimovs, Alexander Rivosh

Publication date: 10 March 2016

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

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.

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)

Cited In (11)

• Faster search of clustered marked states with lackadaisical quantum walks
• Lackadaisical quantum walks with multiple marked vertices
• Upperbounds on the probability of finding marked connected components using quantum walks
• Quantum walk search on a two-dimensional grid with extra edges
• Spatial search by continuous-time quantum walk with multiple marked vertices
• Title not available (Why is that?)
• Quantum walk search for exceptional configurations
• Equivalence of Szegedy's and coined quantum walks
• Exceptional quantum walk search on the cycle
• Adjacent Vertices Can Be Hard to Find by Quantum Walks
• 有限偶圈图上的 2-嵌入交错量子游荡

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)