|
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.
|