| Autor: |
Ambainis, Andris, Kokainis, Martins, Vihrovs, Jevgēnijs |
| Rok vydání: |
2023 |
| Předmět: |
|
| Zdroj: |
18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023) |
| Druh dokumentu: |
Working Paper |
| DOI: |
10.4230/LIPIcs.TQC.2023.7 |
| Popis: |
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$-th item. Our second result is a quantum lower bound of $\Omega(\sqrt{T\log T})$. Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
