DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2017.42

Efficient Quantum Walk on the Grid with Multiple Marked Elements

Authors: Peter Hoyer and Mojtaba Komeili

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

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.

Cite as

Peter Hoyer and Mojtaba Komeili. Efficient Quantum Walk on the Grid with Multiple Marked Elements. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{hoyer_et_al:LIPIcs.STACS.2017.42,
  author =	{Hoyer, Peter and Komeili, Mojtaba},
  title =	{{Efficient Quantum Walk on the Grid with Multiple Marked Elements}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.42},
  URN =		{urn:nbn:de:0030-drops-69902},
  doi =		{10.4230/LIPIcs.STACS.2017.42},
  annote =	{Keywords: Quantum walks, random walks, query complexity, spatial search}
}

Search Results

Documents authored by Hoyer, Peter

Efficient Quantum Walk on the Grid with Multiple Marked Elements

Abstract

Cite as

Thanks for your feedback!

Could not send message