6533b7d4fe1ef96bd1263309
RESEARCH PRODUCT
Quantum algorithms for search with wildcards and combinatorial group testing
Ashley MontanaroAndris Ambainissubject
Nuclear and High Energy PhysicsFOS: Physical sciencesGeneral Physics and Astronomy0102 computer and information sciences01 natural sciencesUpper and lower boundsTheoretical Computer ScienceCombinatoricsSet (abstract data type)Amplitude amplification0103 physical sciencesQuantum walk010306 general physicsMathematical PhysicsMathematicsQuantum PhysicsQuery stringComputer Science::Information RetrievalString (computer science)Statistical and Nonlinear PhysicsWildcard charactercomputer.file_formatComputational Theory and Mathematics010201 computation theory & mathematicsQuantum algorithmQuantum Physics (quant-ph)computerdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2012-10-03 | Quantum Information and Computation |