Theory of Computing
-------------------
Title     : Span-Program-Based Quantum Algorithm for Evaluating Formulas
Authors   : Ben Reichardt and Robert Spalek
Volume    : 8
Number    : 13
Pages     : 291-319
URL       : https://theoryofcomputing.org/articles/v008a013

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.