Paper Info
Title
Adjacent Vertices Can Be Hard to Find by Quantum Walks.
Abstract
Quantum walks have been useful for designing quantum algorithms that outperform their classical versions for a variety of search problems. Most of the papers, however, consider a search space containing a single marked element only. We show that if the search space contains more than one marked element, their placement may drastically affect the performance of the search. More specifically, we study search by quantum walks on general graphs and show a wide class of configurations of marked vertices, for which search by quantum walk needs Omega(N) steps, that is, it has no speed-up over the classical exhaustive search. The demonstrated configurations occur for certain placements of two or more adjacent marked vertices. The analysis is done for the two-dimensional grid and hypercube, and then is generalized for any graph.
Year
DOI
Venue
2017
10.1007/978-3-319-51963-0_20
Lecture Notes in Computer Science
Keywords
Field
DocType
Quantum walks,Stationary states,Multiple marked vertices,Quantum search,Exceptional configurations,General graphs,Hypercube,Two-dimensional grid
Graph theory,Discrete mathematics,Combinatorics,Brute-force search,Vertex (geometry),Computer science,Quantum sort,Quantum walk,Quantum algorithm,Search problem,Hypercube
Conference
Volume
ISSN
Citations 
10139
0302-9743
2
PageRank 
References 
Authors
0.44
6
2
Name
Order
Citations
PageRank
Nikolajs Nahimovs1364.95
raqueline a m santos2172.67