Adversary Lower Bounds for Nonadaptive Quantum Algorithms

Koiran, Pascal; Portier, Natacha; Landes, Jürgen und Yao, Penghui (2010): Adversary Lower Bounds for Nonadaptive Quantum Algorithms. In: Journal of Computer and System Sciences, Bd. 76, Nr. 5: 347 -355

Abstract

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.

• Dokumententyp: Zeitschriftenartikel
• Publikationsform: Postprint
• Keywords: Query complexity; Quantum algorithms; Lower bounds; Adversary method; Nonadaptive algorithms
• Fakultät: Philosophie, Wissenschaftstheorie und Religionswissenschaft > Munich Center for Mathematical Philosophy (MCMP) ; Philosophie, Wissenschaftstheorie und Religionswissenschaft > Munich Center for Mathematical Philosophy (MCMP) > Logic
• Themengebiete: 100 Philosophie und Psychologie > 160 Logik
• ISSN: 0022-0000
• Sprache: Englisch