Adversary lower bounds for nonadaptive quantum algorithms
arXiv:0804.1440
Abstract
We present general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Our results are based on the adversary method of Ambainis.