text: We study the power of nonadaptive quantum query algorithms, which are algorithms whose queries to the input do not depend on the result of previous queries. First, we show that any bounded-error nonadaptive quantum query algorithm that computes some total boolean function depending on n variables must make Omega(n) queries to the input in total. Second, we show that, if there exists a quantum algorithm that uses k nonadaptive oracle queries to learn which one of a set of m boolean functions it has been given, there exists a nonadaptive classical algorithm using O(k log m) queries to solve the same problem. Thus, in the nonadaptive setting, quantum algorithms can achieve at most a very limited speed-up over classical query algorithms.
  @cite_14: We present two general methods for proving lower bounds on the query complexity of nonadaptive quantum algorithms. Both methods are based on the adversary method of Ambainis. We show that they yield optimal lower bounds for several natural problems, and we challenge the reader to determine the nonadaptive quantum query complexity of the ''1-to-1 versus 2-to-1'' problem and of Hidden Translation. In addition to the results presented at Wollic 2008 in the conference version of this paper, we show that the lower bound given by the second method is always at least as good (and sometimes better) as the lower bound given by the first method. We also compare these two quantum lower bounds to probabilistic lower bounds.
  @cite_13: This paper employs a powerful argument, called an algorithmic argument, to prove lower bounds of the quantum query complexity of a multiple-block ordered search problem, which is a natural generalization of the ordered search problem. Apart from much studied polynomial and adversary methods for quantum query complexity lower bounds, our argument shows that the multiple-block ordered search needs a large number of nonadaptive oracle queries on a black-box model of quantum computation that is also supplemented with advice. Our argument is also applied to the notions of computational complexity theory: quantum truth-table reducibility and quantum truth-table autoreducibility.
  @cite_12: The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. We exhibit a function with polynomial degree M and quantum query complexity @W(M^1^.^3^2^1^...). This is the first superlinear separation between polynomial degree and quantum query complexity. The lower bound is shown by a generalized version of the quantum adversary method.
  @cite_2: I show that for any number of oracle lookups up to about pi 4thinsp radical (N) , Grover close_quote s quantum searching algorithm gives the maximal possible probability of finding the desired element. I explain why this is also true for quantum algorithms which use measurements during the computation. I also show that unfortunately quantum searching cannot be parallelized better than by assigning different parts of the search space to independent quantum computers. copyright ital 1999 ital The American Physical Society
summary: We note that the question of putting lower bounds on nonadaptive quantum query algorithms has been studied previously. First, Zalka has obtained a tight lower bound on the nonadaptive quantum query complexity of the unordered search problem, which is a particular learning problem @cite_2 . Second, in @cite_13 , Nishimura and Yamakami give lower bounds on the nonadaptive quantum query complexity of a multiple-block variant of the ordered search problem. Finally, @cite_14 develop the weighted adversary argument of Ambainis @cite_12 to obtain lower bounds that are specific to the nonadaptive setting. Unlike the situation considered here, their bounds also apply to quantum algorithms for computing partial functions.