Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1210.1148 · Quantum Information and Computation

Quantum algorithms for search with wildcards and combinatorial group testing

Andris Ambainis, Ashley Montanaro

Published May 1, 2014• 23 citations
arXivHTMLPDF

Abstract

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.

DOI
10.26421/qic14.5-6-4

Related papers

Quantum Search With Generalized Wildcards

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro +2 more

In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string $x \in \{-1,1\}^n$. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost $O(\sqrt{n} \log n)$ and a near-matching lower bound of $Ω(\sqrt{n})$. Belovs [Comput.~Comp.'15] subsequently showed a tight $O(\sqrt{n})$ upper bound. We consider a natural generalization of this problem, parametrized by a subset $\cal{Q} \subseteq 2^{[n]}$, where an algorithm may test whether $x_S = b$ for an arbitrary $S \in \cal{Q}$ and $b \in \{-1,1\}^S$ of its choice, at unit cost. We show near-tight bounds when $\cal{Q}$ is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning $x$ is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions $f : \{-1,1\}^n \to \mathbb{R}$ the ratio of the maximum value of $f$ to the maximum (over $T \in \cal{Q}$) standard deviation of $f$ on a subcube whose free variables are exactly $T$.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.

quant-pharXiv:2511.04669•Leibniz international proceedings in informatics•Nov 7, 2025•1 citation

Quantum algorithms for learning a hidden graph and beyond

Ashley Montanaro, Changpeng Shao

We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.

arXiv:2011.08611•Nov 17, 2020•9 citations

Quantum algorithms for subset finding

Andrew M. Childs, Eisenberg, J M

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.

•Nov 6, 2003•54 citations

Quantum search for multiple items using parallel queries

Lov K. Grover, Jaikumar Radhakrishnan

In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.

arXiv:quant-ph/0407217•Jul 27, 2004•17 citations

Improved Algorithm and Lower Bound for Variable Time Quantum Search

Andris Ambainis, Martins Kokainis, Jevgēnijs Vihrovs

We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity $O(\sqrt{T}\log n)$ where $T=\sum_{i=1}^n t_i^2$ with $t_i$ denoting the time to check the $i$-th item. Our second result is a quantum lower bound of $Ω(\sqrt{T\log T})$. Both the algorithm and the lower bound improve over previously known results by a factor of $\sqrt{\log T}$ but the algorithm is also substantially simpler than the previously known quantum algorithms.

arXiv:2302.06749•Leibniz international proceedings in informatics•Jan 1, 2023•11 citations

Quantum algorithms for the ordered search problem via semidefinite programming

Andrew M. Childs, Andrew J. Landahl, Pablo A. Parrilo

One of the most basic computational problems is the task of finding a desired item in an ordered list of $N$ items. While the best classical algorithm for this problem uses ${\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.

arXiv:quant-ph/0608161•Physical Review A•Mar 26, 2007•49 citations
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 SSS contain any special items?''\ for any subset SSS of the nnn items. We give a simple quantum algorithm which uses O(k)O(k)O(k) queries to solve this problem, as compared with the classical lower bound of Ω(klog⁡(n/k))\Omega(k \log(n/k))Ω(klog(n/k)) queries.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}nx \in \{-1,1\}^nx∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlog⁡n)O(\sqrt{n} \log n)O(n​logn) and a near-matching lower bound of Ω(n)Ω(\sqrt{n})Ω(n​). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n)O(\sqrt{n})O(n​) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n]\cal{Q} \subseteq 2^{[n]}Q⊆2[n], where an algorithm may test whether xS=bx_S = bxS​=b for an arbitrary S∈QS \in \cal{Q}S∈Q and b∈{−1,1}Sb \in \{-1,1\}^Sb∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q\cal{Q}Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set. All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning xxx is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→Rf : \{-1,1\}^n \to \mathbb{R}f:{−1,1}n→R the ratio of the maximum value of fff to the maximum (over T∈QT \in \cal{Q}T∈Q) standard deviation of fff on a subcube whose free variables are exactly TTT.' To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
We study the problem of learning an unknown graph provided via an oracle using a quantum algorithm. We consider three query models. In the first model ("OR queries"), the oracle returns whether a given subset of the vertices contains any edges. In the second ("parity queries"), the oracle returns the parity of the number of edges in a subset. In the third model, we are given copies of the graph state corresponding to the graph. We give quantum algorithms that achieve speedups over the best possible classical algorithms in the OR and parity query models, for some families of graphs, and give quantum algorithms in the graph state model whose complexity is similar to the parity query model. For some parameter regimes, the speedups can be exponential in the parity query model. On the other hand, without any promise on the graph, no speedup is possible in the OR query model. A main technique we use is the quantum algorithm for solving the combinatorial group testing problem, for which a query-efficient quantum algorithm was given by Belovs. Here we additionally give a time-efficient quantum algorithm for this problem, based on the algorithm of Ambainis et al.\ for a "gapped" version of the group testing problem. We also give simple time-efficient quantum algorithms based on Fourier sampling and amplitude amplification for learning the exact-half and majority functions, which almost match the optimal complexity of Belovs' algorithms.
Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.
In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a database each with N items which we can query in parallel. Then, given k items, we are required to determine the locations where these items are stored. We show that any quantum algorithm for this task must perform Omega(sqrt{Nk/d min{d,k}}) parallel queries. We also design an algorithm whose performance comes within a factor O(log d) of this lower bound.
We study variable time search, a form of quantum search where queries to different items take different time. Our first result is a new quantum algorithm that performs variable time search with complexity O(Tlog⁡n)O(\sqrt{T}\log n)O(T​logn) where T=∑i=1nti2T=\sum_{i=1}^n t_i^2T=∑i=1n​ti2​ with tit_iti​ denoting the time to check the iii-th item. Our second result is a quantum lower bound of Ω(Tlog⁡T)Ω(\sqrt{T\log T})Ω(TlogT​). Both the algorithm and the lower bound improve over previously known results by a factor of log⁡T\sqrt{\log T}logT​ but the algorithm is also substantially simpler than the previously known quantum algorithms.
One of the most basic computational problems is the task of finding a desired item in an ordered list of NNN items. While the best classical algorithm for this problem uses log2N{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}Nlog2​N queries to the list, a quantum computer can solve the problem using a constant factor fewer queries. However, the precise value of this constant is unknown. By characterizing a class of quantum query algorithms for the ordered search problem in terms of a semidefinite program, we find quantum algorithms for small instances of the ordered search problem. Extending these algorithms to arbitrarily large instances using recursion, we show that there is an exact quantum ordered search algorithm using $4\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{605}\phantom{\rule{0.2em}{0ex}}N\ensuremath{\approx}0.433\phantom{\rule{0.2em}{0ex}}{\mathrm{log}}_{2}\phantom{\rule{0.2em}{0ex}}N$ queries, which improves upon the previously best known exact algorithm.