Name
Abstract | ||
|---|---|---|
We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in Z(p)(n), whenever p is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group G is reducible to instances of Translating Coset in G/N and N, for appropriate normal subgroups N of G. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1137/130907203 | SIAM JOURNAL ON COMPUTING |
Keywords | Field | DocType |
quantum algorithms,hidden subgroup problem,solvable groups | Prime (order theory),Abelian group,Discrete mathematics,Combinatorics,Hidden subgroup problem,Quantum computer,Solvable group,Quantum algorithm,Coset,Mathematics,Normal subgroup | Journal |
Volume | Issue | ISSN |
43 | 1 | 0097-5397 |
Citations | PageRank | References |
4 | 0.40 | 19 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Katalin Friedl | 1 | 173 | 14.18 |
| Gábor Ivanyos | 2 | 257 | 28.02 |
| Frédéric Magniez | 3 | 570 | 44.33 |
| Miklos Santha | 4 | 728 | 92.42 |
| Pranab Sen | 5 | 394 | 26.65 |