Abstract
The general adversary bound is a semi-definite program (SDP) that
lower-bounds the quantum query complexity of a function. We turn this lower
bound into an upper bound, by giving a quantum walk algorithm based on the dual
SDP that has query complexity at most the general adversary bound, up to a
logarithmic factor.
In more detail, the proof has two steps, each based on "span programs," a
certain linear-algebraic model of computation. First, we give an SDP that
outputs for any boolean function a span program computing it that has optimal
"witness size." The optimal witness size is shown to coincide with the general
adversary lower bound. Second, we give a quantum algorithm for evaluating span
programs with only a logarithmic query overhead on the witness size.
The first result is motivated by a quantum algorithm for evaluating composed
span programs. The algorithm is known to be optimal for evaluating a large
class of formulas. The allowed gates include all constant-size functions for
which there is an optimal span program. So far, good span programs have been
found in an ad hoc manner, and the SDP automates this procedure. Surprisingly,
the SDP's value equals the general adversary bound. A corollary is an optimal
quantum algorithm for evaluating "balanced" formulas over any finite boolean
gate set. The second result extends span programs' applicability beyond the
formula evaluation problem.
A strong universality result for span programs follows. A good quantum query
algorithm for a problem implies a good span program, and vice versa. Although
nearly tight, this equivalence is nontrivial. Span programs are a promising
model for developing more quantum algorithms.
Description
Span programs and quantum query complexity: The general adversary bound
is nearly tight for every boolean function
Links and resources
Tags
community