00905nas a2200133 4500008004100000245003600041210003400077260001500111300001100126490000700137520057100144100001900715856003700734 2013 eng d00aQuantum Adversary (Upper) Bound0 aQuantum Adversary Upper Bound c2013/04/05 a1 - 140 v193 a We describe a method to upper bound the quantum query complexity of Boolean
formula evaluation problems, using fundamental theorems about the general
adversary bound. This nonconstructive method can give an upper bound on query
complexity without producing an algorithm. For example, we describe an oracle
problem which we prove (non-constructively) can be solved in $O(1)$ queries,
where the previous best quantum algorithm uses a polylogarithmic number of
queries. We then give an explicit $O(1)$-query algorithm for this problem based
on span programs.
1 aKimmel, Shelby uhttp://arxiv.org/abs/1101.0797v5