Span-program-based quantum algorithm for evaluating formulas
Ben W. Reichardt, Robert Špalek · 2008
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.