@inproceedings{380cec54b4f445b98ded8363b713f65a,
title = "Improved algorithm and lower bound for variable time quantum search",
abstract = "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(√ T log n) where T = σni=1t2iwith tidenoting the time to check the ith item. Our second result is a quantum lower bound of Ω(√ T log T). Both the algorithm and the lower bound improve over previously known results by a factor of √log T but the algorithm is also substantially simpler than the previously known quantum algorithms.",
keywords = "Amplitude amplification, Quantum search",
author = "Andris Ambainis and Martins Kokainis and Jevgēnijs Vihrovs",
note = "Publisher Copyright: {\textcopyright} 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.; 18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023 ; Conference date: 24-07-2023 Through 28-07-2023",
year = "2023",
month = jul,
doi = "10.4230/LIPIcs.TQC.2023.7",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Omar Fawzi and Michael Walter",
booktitle = "18th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2023",
address = "Germany",
}