Ben Reichardt

California Institute of Technology
Pasadena, CA 91125

Span program-based quantum algorithm for evaluating formulas

We present a time-efficient and query-optimal quantum algorithm for evaluating ``adversary-balanced" formulas on an extended gate set. The allowed gates include arbitrary two- and three-bit gates, as well as bounded fan-in AND, OR, PARITY and EQUAL gates. The technique behind the formula evaluation algorithm is a new framework for quantum algorithms based on span programs. For example, the classical complexity of evaluating the balanced ternary majority formula is unknown, and the natural generalization
of the standard balanced AND-OR formula evaluation algorithm is known to be suboptimal. In contrast, a generalization of the optimal quantum {AND, OR, NOT} formula evaluation algorithm is optimal for evaluating the balanced ternary majority formula.

Seminar schedule: http://www.physics.rutgers.edu/qcg/Seminars.html