An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem

François Le Gall 1, *
* Auteur correspondant
Abstract : In this paper we consider the problem of testing whether two finite groups are isomorphic. Whereas the case where both groups are abelian is well understood and can be solved efficiently, very little is known about the complexity of isomorphism testing for nonabelian groups. Le Gall has constructed an efficient classical algorithm for a class of groups corresponding to one of the most natural ways of constructing nonabelian groups from abelian groups: the groups that are extensions of an abelian group $A$ by a cyclic group $Z_m$ with the order of $A$ coprime with $m$. More precisely, the running time of that algorithm is almost linear in the order of the input groups. In this paper we present a quantum algorithm solving the same problem in time polynomial in the logarithm of the order of the input groups. This algorithm works in the black-box setting and is the first quantum algorithm solving instances of the nonabelian group isomorphism problem exponentially faster than the best known classical algorithms.
Type de document :
Communication dans un congrès
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.549-560, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00455763
Contributeur : Publications Loria <>
Soumis le : jeudi 11 février 2010 - 10:24:53
Dernière modification le : jeudi 11 février 2010 - 11:18:00
Document(s) archivé(s) le : vendredi 18 juin 2010 - 20:10:05

Fichier

LeGallSTACS10CR.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455763, version 1

Collections

Citation

François Le Gall. An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.549-560, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. 〈inria-00455763〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

105