Justin Thaler, Georgetown University
The quantum query complexity of a function f measures how many bits of the input a quantum computer must look at in order to compute f.
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)
I will describe consequences in (classical) circuit complexity and learning theory, and highlight several tantalizing open questions.
Joint work with Mark Bun and Robin Kothari.