2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/92642Simon 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 nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon's problem. Our bound is optimal up to a constant factor.8 pages, 1 figureQuantum PhysicsComputational Complexitytext