When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1333
URN: urn:nbn:de:0030-drops-13333
Go to the corresponding LIPIcs Volume Portal

Ambainis, Andris

Quantum search with variable times

Document 1.pdf (175 KB)


Since Grover's seminal work, quantum search has been studied in great detail. In the usual search problem, we have a collection of $n$ items $x_1, ldots, x_n$ and we would like to find $i: x_i=1$. We consider a new variant of this problem in which evaluating $x_i$ for different $i$ may take a different number of time steps. Let $t_i$ be the number of time steps required to evaluate $x_i$. If the numbers $t_i$ are known in advance, we give an algorithm that solves the problem in $O(sqrt{t_1^2+t_2^2+ldots+t_n^2)$ steps. This is optimal, as we also show a matching lower bound. The case, when $t_i$ are not known in advance, can be solved with a polylogarithmic overhead. We also give an application of our new search algorithm to computing read-once functions.

BibTeX - Entry

  author =	{Andris Ambainis},
  title =	{{Quantum search with variable times}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{49--61},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-13333},
  doi =		{},
  annote =	{Keywords: }

Seminar: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint Published by LZI