| Presentation | 2005-04-18 Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups of Cyclic Groups Yoshifumi INUI, GALL Francois LE, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | It is known that for some problems such as a factorization, there exist quantum algorithms exponentially or subexponentially faster than any already known classical algorithms. Most of such problems can be recognized as the hidden subgroup problems (HSP) over Abelian groups, which are solved by polynomial-time quantum algorithms. Some HSP over non-Abelian groups are connected to important problems, but there is no known polynomial-time algorithm for the HSP over general groups. In this paper, we consider semidirect product groups of two cyclic groups which contain dihedral groups relate to the problem of finding the shortest vector in a lattice, and give polynomial-time algorithms for the HSP over some classes of such groups. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Quantum Algorithms / Hidden Subgroup Problem / Semi-direct Product |
| Paper # | COMP2005-5 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/4/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups of Cyclic Groups |
| Sub Title (in English) | |
| Keyword(1) | Quantum Algorithms |
| Keyword(2) | Hidden Subgroup Problem |
| Keyword(3) | Semi-direct Product |
| 1st Author's Name | Yoshifumi INUI |
| 1st Author's Affiliation | Department of Computer Science Graduate School of Information Science and Technology, University of Tokyo:ERATO Quantum Computation and Information Project, JST() |
| 2nd Author's Name | GALL Francois LE |
| 2nd Author's Affiliation | Department of Computer Science Graduate School of Information Science and Technology, University of Tokyo:ERATO Quantum Computation and Information Project, JST |
| Date | 2005-04-18 |
| Paper # | COMP2005-5 |
| Volume (vol) | vol.105 |
| Number (no) | 7 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |