Andris Ambainis, Ashley Montanaro
Combinatorial group testing is the problem of identifying a subset of k special items out of a set of n items, given the ability to make queries of the form "does the set S contain any special items?" for any subset S of the n items. We give a quantum algorithm which uses O(sqrt(k) log k) queries to solve this problem, as compared with the classical lower bound of Omega(k log(n/k)) queries. We use as a subroutine a new and optimal O(sqrt(n)) quantum query algorithm for the following "search with wildcards" problem: given an unknown n-bit string x, and the ability to check whether any subset of the bits of x is equal to a provided query string, output x. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem.
View original:
http://arxiv.org/abs/1210.1148
No comments:
Post a Comment