Lower Bounds on Quantum Query Complexity

Abstract

Quantum complexity is a young research area of increasing importance. In spite of the scepticism of part of the research community regarding the possibility of constructing quantum machines, there is nowadays at least one session devoted to this topic in every complexity conference. Two experts in the area, Peter Ho/yer and Robert S^palek write in this column a beautiful survey on quantum query complexity, focusing on the methods for proving lower bounds.