Tutte seminar - Ben Reichardt
Span programs and quantum query complexity
Speaker: | Ben Reichardt |
---|---|
Affiliation: | University of Waterloo |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.