An Efficient Quantum Algorithm for the Hidden Subgroup Problem over a Class of non-Abelian Groups

Date/Time: 14 April 2005 - ()

Speaker: Francois Legall (Technical Assistant, ERATO / doctoral course student, The University of Tokyo)

The Hidden Subgroup Problem (HSP) is the problem of finding a subgroup hidden in a group G. When the group G is Abelian, an efficient quantum algorithm solving the HSP over G is known. The case of G not Abelian is much more complicated and an algorithm solving HSP over any non-Abelian group would have significant consequences in computer science, enabling to solve the graph isomorphism problem or to break lattice-based cryptosystems for example. In this talk, I will present a polynomial-time quantum algorithm solving the HSP over a restricted class of non-Abelian groups: the groups that can be written as a semi-product of cyclic groups.