Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

Details Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function

2009-04-17

arxiv.org/abs/0904.2759v1

Extended abstract in Proc. 50th IEEE Symp. on Foundations of Computer Science (FOCS), 2009, pages 544-551

Physics

Quantum Physics

70 pages, 2 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-141917