Quantum search with variable times
| dc.creator | Ambainis, Andris | |
| dc.date | 2006-09-21 | |
| dc.date.accessioned | 2026-07-07T07:30:15Z | |
| dc.date.available | 2026-07-07T07:30:15Z | |
| dc.description | 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 and we would like to find a marked item. We consider a new variant of this problem in which evaluating the i-th item may take a different number of time steps for different i. Let t_i be the number of time steps required to evaluate the i-th item. 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+...+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. | |
| dc.description | 19 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0609168 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0609168 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/118397 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum search with variable times | |
| dc.type | text |