Span-program-based quantum algorithm for evaluating formulas

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.

Authors

• Ben Reichardt
• Robert Spalek

Keywords

• quantum phase estimation
• quantum adversary bound
• span programs
• formula evaluation
• quantum computing
• gadget graphs
• balanced ternary majority formula
• quantum walks
• quantum algorithms
• spectral analysis