Adversary Lower Bounds for Nonadaptive Quantum Algorithms

Koiran, Pascal; Landes, Jürgen; Portier, Natacha and Yao, Penghui (2008): Adversary Lower Bounds for Nonadaptive Quantum Algorithms. In: Hodges, Wilfrid and de Queiroz, Ruy (eds.) : Logic, Language, Information and Computation ; 15th international workshop, WoLLIC 2008, Edinburgh, UK, July 1 - 4, 2008 ; proceedings. Lecture notes in computer science, Vol. 5110. Berlin, Heidelberg: Springer. pp. 226-237

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.

• Item Type: Book Section
• 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
• ISBN: 978-3-540-69936-1
• ISSN: 0302-9743
• Place of Publication: Berlin, Heidelberg
• Language: English