Quantum algorithms for search with wildcards and combinatorial group testing
Quantum algorithms for search with wildcards and combinatorial group testing
复制标题
用于使用通配符和组合组测试进行搜索的量子算法
DOI：
--
复制
发表时间：
2012
影响因子：
1
通讯作者：
A. Montanaro
中科院分区：
文献类型：
--
作者：
A. Ambainis;A. Montanaro
我们考虑两个组合问题。第一个我们称之为“带通配符的搜索”：给定一个未知的n位字符串x，并且能够检查x的任何位子集是否等于提供的查询字符串，目标是输出x。我们给出了一个接近最优的O（n × log n）量子查询算法，用于搜索通配符，击败了经典的Ω（n）查询的下限。而不是使用振幅放大或量子行走，我们的算法最终是基于状态歧视问题的解决方案。我们考虑的第二个问题是组合组测试，这是一个任务，确定一个子集的最多k个特殊项目的一组n个项目，给定的能力，使查询的形式“集合S包含任何特殊项目？对于n个项目的任何子集S。我们给出了一个简单的量子算法，该算法使用O（k）个查询来解决这个问题，并与经典的Ω（klog（n/k））个查询的下界进行了比较.
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.