Quantum query complexity measures the number of input bits that must be read by a quantum algorithm in order to evaluate a function. Hoyer et al. (2007) have generalized the adversary semi-definite program that lower-bounds quantum query complexity. By giving a matching algorithm, we show that the general adversary lower bound is tight for every boolean function.

The proof is based on span programs, a linear-algebraic computational model without inherent dynamics. Span programs correspond to solutions to the dual semi-definite program, and to bipartite graphs. The analysis shows that properties of eigenvalue-zero eigenvectors of the graphs imply an "effective" spectral gap around zero. We thus develop a quantum algorithm for evaluating span programs. It follows that span programs, measured by witness size, and quantum algorithms, measured by query complexity, are equivalent computational models, up to a constant factor.

The result efficiently characterizes the quantum query complexity of a read-once formula over any finite gate set. It also implies that the quantum query complexity of the composition f(g, ..., g) of two boolean functions matches the product of the query complexities of f and g, without a logarithmic factor for error reduction. The algorithm alternates a fixed reflection with input queries. Originally introduced for solving the unstructured search problem, this structure is therefore a universal feature of quantum query algorithms.

We give a second procedure for evaluating span programs that has the further potential to be time-efficient. Subsequent applications have derived nearly time-optimal quantum algorithms for evaluating many read-once formulas. Span programs may have promise for developing more quantum algorithms.