  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(sqrt(n) log n) quantum query algorithm for
search with wildcards, beating the classical lower bound of Omega(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 log k) queries to solve this problem, as compared with the
classical lower bound of Omega(k log(n/k)) queries.
