The quantum query complexity of the abelian hidden subgroup problem

Simon, in his FOCS’94 paper, was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon’s problem from the point of view of quantum query complexity and give here a first non-trivial lower bound on the query complexity of a hidden subgroup problem, namely Simon’s problem. More generally, we give a lower bound which is optimal up to a constant factor for any abelian group.