Span Programs and Quantum Query Algorithms

Video of this lecture

COMPUTER SCIENCE/DISCRETE MATH II
Topic:Span Programs and Quantum Query Algorithms
Speaker:Ben Reichardt
Affiliation:University of Waterloo, Canada
Date:Tuesday, September 29
Time/Room:10:30am - 12:30pm/S-101

The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor. The proof is based on span programs. It implies that span programs are an (almost) equivalent computational model to quantum query algorithms. One of the consequences is that almost-optimal quantum algorithms can always be designed based on span programs. This is worthwhile because span programs have useful properties, such as composing easily. We apply this to the formula-evaluation problem. For example, evaluating an AND-OR formula is similar to the question of whether white or black has a winning strategy in chess. We give an optimal quantum algorithm for evaluating almost-balanced formulas over any finite boolean gate set. For example, the formula's gate set may be taken to be all functions {0,1}^k --> {0,1} with k <== 1000. Another consequence is a simpler semi-definite program for quantum query complexity.