2006/09/21 by Andris Ambainis, Ambainis, Andris · 3 citations
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0609168
19 pages
arxiv created 2006/09/21 · openalex publication_date 2006/09/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ti be the number of time steps required to evaluate the i-th item. If the numbers ti are known in advance, we give an algorithm that solves the problem in O(√(t12+t22+...+tn2)) steps. This is optimal, as we also show a matching lower bound. The case, when ti 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.