A quantum lower bound for the query complexity of Simon's problem

Simple item page
dc.creatorKoiran, Pascal
dc.creatorNesme, Vincent
dc.creatorPortier, Natacha
dc.date2005-01-12
dc.date.accessioned2026-07-07T06:11:56Z
dc.date.available2026-07-07T06:11:56Z
dc.descriptionSimon 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.
dc.description8 pages, 1 figure
dc.identifierhttps://arxiv.org/abs/quant-ph/0501060
dc.identifierhttp://arxiv.org/abs/quant-ph/0501060
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/92642
dc.subjectQuantum Physics
dc.subjectComputational Complexity
dc.titleA quantum lower bound for the query complexity of Simon's problem
dc.typetext

Files

Collections

arXiv