Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.tcs.2007.02.057 | Theor. Comput. Sci. |
Keywords | Field | DocType |
constant factor,Polynomial method,query complexity,abelian group,quantum query complexity,Hidden subgroup problems,well-studied class,simon's problem,quantum computation,Query complexity,Quantum computing,Lower bounds,abelian hidden subgroup problem,hidden subgroup,exponential gap,lower bound.,Simon’s problem,hidden subgroup problem | Quantum,Discrete mathematics,Abelian group,Combinatorics,Exponential function,Polynomial,Upper and lower bounds,Hidden subgroup problem,Quantum computer,Simon's problem,Mathematics | Journal |
Volume | Issue | ISSN |
380 | 1-2 | Theoretical Computer Science |
Citations | PageRank | References |
2 | 0.37 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pascal Koiran | 1 | 919 | 113.85 |
| Vincent Nesme | 2 | 70 | 8.84 |
| Natacha Portier | 3 | 96 | 11.49 |