Quantum algorithms for subset finding

TitleQuantum algorithms for subset finding
Publication TypeJournal Article
Year of Publication2003
AuthorsChilds, AM, Eisenberg, JM
Date Published2003/11/06

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for
element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for
finding L equal numbers. We point out that this algorithm actually solves a
much more general problem, the problem of finding a subset of size L that
satisfies any given property. We review the algorithm and give a considerably
simplified analysis of its query complexity. We present several applications,
including two algorithms for the problem of finding an L-clique in an N-vertex
graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other
uses \tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The
latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy,
who considered the case L=3 (finding a triangle). We also pose two open
problems regarding continuous time quantum walk and lower bounds.

Short TitleQuantum Information and Computation 5