Abstract
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}ⁿ. 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(√n log n) and a near-matching lower bound of Ω(√n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(√n) upper bound. We consider a natural generalization of this problem, parametrized by a subset Q ⊆ 2^[n], where an algorithm may test whether x_S = b for an arbitrary S ∈ Q and b ∈ {-1,1}^S of its choice, at unit cost. We show near-tight bounds when 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}ⁿ → R the ratio of the maximum value of f to the maximum (over T ∈ 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.