A quantum lower bound for the query complexity of Simon's problem
<|reference_start|>A quantum lower bound for the query complexity of Simon's 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 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.<|reference_end|>
@article{koiran2005a,
    title={A quantum lower bound for the query complexity of Simon's problem},
    author={Pascal Koiran, Vincent Nesme, Natacha Portier},
    journal={arXiv preprint arXiv:quant-ph/0501060},
    year={2005},
    archivePrefix={arXiv},
    eprint={quant-ph/0501060},
    primaryClass={quant-ph cs.CC}
}