  We give a quantum algorithm for evaluating formulas over an extended gate
set, including all two- and three-bit binary gates (e.g., NAND, 3-majority).
The algorithm is optimal on read-once formulas for which each gate's inputs are
balanced in a certain sense.
  The main new tool is a correspondence between a classical linear-algebraic
model of computation, "span programs," and weighted bipartite graphs. A span
program's evaluation corresponds to an eigenvalue-zero eigenvector of the
associated graph. A quantum computer can therefore evaluate the span program by
applying spectral estimation to the graph.
  For example, the classical complexity of evaluating the balanced ternary
majority formula is unknown, and the natural generalization of randomized
alpha-beta pruning is known to be suboptimal. In contrast, our algorithm
generalizes the optimal quantum AND-OR formula evaluation algorithm and is
optimal for evaluating the balanced ternary majority formula.
