TY - JOUR
T1 - Quantum Adversary (Upper) Bound
JF - Chicago Journal of Theoretical Computer Science
Y1 - 2013
A1 - Shelby Kimmel
AB - 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.
VL - 19
U4 - 1 - 14
UR - http://arxiv.org/abs/1101.0797v5
CP - 1
J1 - Chicago J. of Theoretical Comp. Sci.
U5 - 10.4086/cjtcs.2013.004
ER -