Nikhil Mande

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 \Omega(\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.

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).