Quantum Search With Generalized Wildcards

13^th May 2026, 13:00 GH223
Nikhil Mande
University of Liverpool

Abstract

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 (call this a "guess"). Ambainis and Montanaro showed a quantum algorithm of cost O(sqrt{n} log n) and a near-matching lower bound of Omega(sqrt{n}). Belovs [Comput. Comp.'15] subsequently showed a tight O(sqrt{n}) upper bound.

We consider a natural generalization of this problem, where an algorithm is restricted in the subsets it may make guesses on. We show tight bounds for various choices of subset collections, such as sets of bounded size, contiguous blocks, prefixes, and only the full set. In particular, our results recover the above-mentioned bounds.

All of these results are derived using a framework that we develop. We show, using the primal adversary bound, that the quantum query complexity of learning x is characterized, up to a constant factor, by a particular abstract analytic optimization program.

I will assume no prior knowledge about quantum computing, and will spend a few minutes towards the end of the talk discussing generative AI's contribution in developing key conceptual ideas in this work.

Based on joint work with Arjan Cornelissen, Subhasree Patro, Nithish Raja, and Swagato Sanyal.

Additional Materials

• https://arxiv.org/abs/2511.04669