Span programs and optimal quantum query algorithms

We show that the general adversary lower bound on quantum query complexity is nearly tight, by giving a matching quantum walk algorithm. The result gives a new semi-definite program for quantum query complexity, and shows an equivalence to the span program model of computation. Span programs compose easily, and this yields a quantum recursion method. Classical algorithms cannot compose in this way. Applying the technique to solve problems defined recursively with independent inputs, i.e., to evaluating formulas, gives an optimal quantum formula-evaluation algorithm. Span programs are a promising model for developing more quantum algorithms.