|Koiran, Pascal; Portier, Natacha; Landes, Jürgen; Yao, Penghui (2010): Adversary Lower Bounds for Nonadaptive Quantum Algorithms. In: Journal of Computer and System Sciences, Vol. 76, No. 5: 347 -355|
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.
|Keywords:||Query complexity; Quantum algorithms; Lower bounds; Adversary method; Nonadaptive algorithms|
|Faculties:||Philosophy, Philosophy of Science and Religious Science > Munich Center for Mathematical Philosophy (MCMP)|
Philosophy, Philosophy of Science and Religious Science > Munich Center for Mathematical Philosophy (MCMP) > Logic
|Subjects:||100 Philosophy and Psychology > 160 Logic|
|Deposited On:||30. Jun 2016 08:11|
|Last Modified:||30. Jun 2016 08:11|