Arjan Cornelissen

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.

We introduce the graph composition framework, a generalization of the st-connectivity framework for constructing quantum algorithms. Our framework constructs algorithms that solve a connectivity problem on an undirected graph, where the availability of each edge is computed by a span program. The key novelty of our framework is that the construction allows for amortization of the span programs’ costs, while at the same time avoiding build-up of errors due to composition. We give generic time-efficient implementations of algorithms generated through the graph composition framework in the quantum read-only memory model, which is a weaker assumption than the more common quantum random-access model. Along the way, we also simplify the span program algorithm by converting it to a transducer, and remove the dependence of its analysis on the effective spectral gap lemma. We use graph composition to unify existing quantum algorithmic frameworks. Surprisingly, we show that any randomized algorithm can be converted into an instance of the st-connectivity framework. Furthermore, we show that the st-connectivity framework subsumes the learning graph framework, and the weighted-decision-tree framework. We show that the graph composition framework subsumes part of the quantum divide-and-conquer framework, and that it is itself subsumed by the multidimensional quantum walk framework. Moreover, we show polynomial relations and separations between the optimal query complexities that can be achieved with several of these frameworks. Finally, we apply our techniques to give improved algorithms for various string-search problems, namely the Dyck-language recognition problem of depth 3, the 3-increasing subsequence problem, and the OR ◦ pSEARCH-problem. We also simplify existing quantum algorithms for the space-efficient directed st-connectivity problem, the pattern matching problem and the Σ∗ 20∗ 2Σ∗ -problem.

The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers randomized algorithms, which return an approximate solution in faster time. In this work, we adopt a unifying perspective that frames these randomized algorithms in terms of mean estimation. Using it, we first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (`99), and based on sketching by Sarlós (`06) and Drineas-Kannan-Mahoney (`06). We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches, if we assume no use of (exact) fast matrix multiplication as a subroutine. Second, we demonstrate a quantum speedup on top of these algorithms by using the recent quantum multivariate mean estimation algorithm by Cornelissen-Hamoudi-Jerbi (`22).