# Span-program-based quantum algorithm for evaluating formulas

### Venue

Theory of Computing, vol. 8(13) (2012), pp. 291-319

### Publication Year

2012

### Authors

Ben Reichardt, Robert Spalek

### BibTeX

## Abstract

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.