01268nas a2200121 4500008004100000245004200041210004200083260001500125520091400140100002301054700002501077856004401102 2003 eng d00aQuantum algorithms for subset finding0 aQuantum algorithms for subset finding c2003/11/063 a 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.
1 aChilds, Andrew, M.1 aEisenberg, Jason, M. uhttp://arxiv.org/abs/quant-ph/0311038v2