Adversary lower bounds for nonadaptive quantum algorithms

Pascal Koiran (1) , Jürgen Landes (2) , Natacha Portier (1) , Penghui Yao (3)

1 LIP - Laboratoire de l'Informatique du Parallélisme
2 The University of Manchester School of Mathematics
3 LCS - State Key Laboratory of Computer Science [Beijing]

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.

Keywords: query complexity; lower bound; quantum computing; nonadaptive algorithm; adversary mathod

Domains: Computer Science [cs]; Computational Complexity [cs.CC]; Physics [physics]; Quantum Physics [quant-ph]

Pascal Koiran, Jürgen Landes, Natacha Portier, Penghui Yao. Adversary lower bounds for nonadaptive quantum algorithms. WoLLIC 2008 15th Workshop on Logic, Language, Information and Computation, Jul 2008, Edinburgh, United Kingdom. ⟨ensl-00260279v2⟩