Quantum algorithms for search with wildcards and combinatorial group
testing (pp0439-0453)
Andris
Ambainis and Ashley Montanaro
doi:
https://doi.org/10.26421/QIC14.5-6-4
Abstracts:
We consider two combinatorial problems. The first we call “search with
wildcards”: 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,
the goal is to output x. We give a nearly optimal O( √ n log n) quantum
query algorithm for search with wildcards, beating the classical lower
bound of Ω(n) queries. Rather than using amplitude amplification or a
quantum walk, our algorithm is ultimately based on the solution to a
state discrimination problem. The second problem we consider is
combinatorial group testing, which is the task of identifying a subset
of at most 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 simple quantum algorithm which
uses O(k) queries to solve this problem, as compared with the classical
lower bound of Ω(k log(n/k)) queries.
Key words:
Quantum query complexity, oracle interrogation,
combinatorial group testing |