Quantum search with variable times

Author Andris Ambainis



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1333.pdf
  • Filesize: 174 kB
  • 12 pages

Document Identifiers

Author Details

Andris Ambainis

Cite AsGet BibTex

Andris Ambainis. Quantum search with variable times. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 49-60, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1333

Abstract

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.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail