The Quantum Query Complexity of the Abelian Hidden Subgroup Problem.

DSpace/Manakin Repository

Show simple item record

dc.contributor.author Laboratoire de l'informatique du parallélisme fr
dc.contributor.author Koiran, Pascal fr
dc.contributor.author Nesme, Vincent fr
dc.contributor.author Portier, Natacha fr
dc.date.accessioned 2005-12-02T11:04:45Z
dc.date.available 2005-12-02T11:04:45Z
dc.date.issued 2005-04 en_US
dc.identifier.other LIP-RR - 2005-17 en_US
dc.identifier.uri http://hdl.handle.net/2332/523
dc.description.abstract (eng) 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. We also show how, as a consequence, this gives us the query complexity of the Abelian hidden subgroup problem, up to a constant factor. At last we expose some elementary facts about complexity in weaker query models. en_US
dc.format.extent 2+12p fr
dc.format.extent 634785 bytes
dc.format.mimetype application/pdf
dc.language.iso eng en_US
dc.source.uri http://www.ens-lyon.fr/LIP/Pub/Rapports/RR/RR2005/RR2005-17.ps.gz en_US
dc.subject quantum computation en_US
dc.subject query complexity en
dc.subject hidden subgroup en
dc.subject Simon's problem en
dc.subject lower bound en
dc.title The Quantum Query Complexity of the Abelian Hidden Subgroup Problem. en_US
dc.type Research report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account

Bookmark and Share