Quantum algorithms for search with wildcards and combinatorial group testing
Quantum Information and Computation · 2014-05 · 14 (5&6) · 439-453
DOI: 10.26421/qic14.5-6-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Quantum Information and Computation, 2014-05. Verfasst von Andris Ambainis und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).
Abstract (Originalsprache)
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)$ queries to solve this problem, as compared with the classical lower bound of $\Omega(k \log(n/k))$ queries.
Zitieren
APA
Ambainis, A., & Montanaro, A. (2014). Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation, 14(5&6), 439-453. https://doi.org/10.26421/qic14.5-6-4
Vancouver
Ambainis A, Montanaro A. Quantum algorithms for search with wildcards and combinatorial group testing. Quantum Information and Computation. 2014;14(5&6):439-453. doi:10.26421/qic14.5-6-4
BibTeX
@article{Ambainis2014,
author = {Ambainis, Andris and Montanaro, Ashley},
title = {Quantum algorithms for search with wildcards and combinatorial group testing},
journal = {Quantum Information and Computation},
year = {2014},
volume = {14},
number = {5&6},
pages = {439--453},
doi = {10.26421/qic14.5-6-4}
}
EUVIMED