Nothing Special   »   [go: up one dir, main page]

 

 
   

 

Editorial Board
Guidelines for Authors
QIC Online

Subscribers: to view the full text of a paper, click on the title of the paper. If you have any problem to access the full text, please check with your librarian or contact qic@rintonpress.com   To subscribe to QIC, please click Here.

Quantum Information and Computation     ISSN: 1533-7146      published since 2001
Vol.14 No.5&6  April 2014

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

ˇˇ