@inproceedings{0bc9fc98e5d2474b8aad4f00c62dd976,
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 Ω(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.",
keywords = "Exceptional configurations, General graphs, Hypercube, Multiple marked vertices, Quantum search, Quantum walks, Stationary states, Two-dimensional grid",
author = "Nikolajs Nahimovs and Santos, \{Raqueline A.M.\}",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 43rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2017 ; Conference date: 16-01-2017 Through 20-01-2017",
year = "2017",
doi = "10.1007/978-3-319-51963-0\_20",
language = "English",
isbn = "9783319519623",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "256--267",
editor = "Christel Baier and \{van den Brand\}, Mark and Johann Eder and Mike Hinchey and Tiziana Margaria and Bernhard Steffen",
booktitle = "SOFSEM 2017",
address = "Germany",
}