Abstract
Quantum query complexity is known to behave multiplicatively under block composition: for any two functions f, g with quantum query complexities Q(f) and Q(g), the block composition F obtained by applying f to the results of g on disjoint sets of variables satisfies Q(F)=Theta(Q(f) * Q(g)). Meanwhile, "shared-input" compositions, where the copies of the inner functions g may share n inputs in an arbitrary fashion, are not well understood. I will describe a general setting in which the overlapping structure of the inputs to copies of g can be exploited algorithmically. Specifically, for any function f, I will give an algorithm for evaluating any shared-input composition of f and g=AND using ~O((Q(f) * n)^{1/2}) quantum queries. As long as Q(f)<<n, this improves on the bound of O(Q(f) * n^{1/2}) that follows by treating each conjunction independently, and is tight for worst-case choices of f. I will describe consequences in circuit complexity and learning theory, and highlight several tantalizing open questions. Joint work with Mark Bun and Robin Kothari.