10.4230/LIPICS.STACS.2008.1333
Ambainis, Andris
Andris
Ambainis
Quantum search with variable times
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13333
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
6
49
60
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
178902 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 49-60