Adversary lower bounds for nonadaptive quantum algorithms

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

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

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.

Mots clés: query complexity; lower bound; quantum computing; nonadaptive algorithm; adversary mathod

Domaines: Complexité [cs.CC]

Pacal Koiran, Natacha Portier, Penghui Yao, Jürgen Landes. Adversary lower bounds for nonadaptive quantum algorithms. 2008. ⟨ensl-00260279v1⟩