()


Abstract

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.