The general adversary bound is a lower bound on quantum query complexity. We turn this lower bound into an upper bound, by giving a quantum walk algorithm that has query complexity at most the general adversary bound, up to a logarithmic factor.
The proof has two steps, each based on "span programs," a certain linear-algebraic model of computation. First, we give a semi-definite program that outputs for any boolean function an optimal span program. Second, we give a quantum algorithm for evaluating span programs with only a small overhead.
The result has several consequences. For example, it gives an optimal quantum algorithm for evaluating layered formulas over any finite boolean gate set, e.g., all functions {0,1}^k -> {0,1} with k <= 1000. A strong universality result for span programs also 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.
Location:
Room 184, Physics & Astronomy
Refreshments will be available before the seminar at 3:00 pm, in the PandA lobby.
Individuals with disabilities who need an auxiliary aid or service to attend or participate in P&A events should contact Daniel Sandoval (phone: 505-277-2616, email: daswerto@unm.edu) well in advance to ensure your needs are accommodated. Event handouts can be provided in alternative accessible formats upon request. Please contact Mr. Sandoval if you need written information in an alternative format.
University of New Mexico Department of Physics and Astronomy -
MSC07 4220 -
800 Yale Blvd NE
Albuquerque, New Mexico 87131-0001
Phone: (505) 277-2616
Fax: (505) 277-1520
Comments/questions about this web page? Email webmaster@phys.unm.edu
Spring 2010
Individuals with disabilities who need an auxiliary aid or service to attend or participate in P&A events should contact Daniel Sandoval (phone: 505-277-2616, email: 
People
Faculty