License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2010.2484
URN: urn:nbn:de:0030-drops-24843
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2484/
Go to the corresponding LIPIcs Volume Portal

Le Gall, François

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

pdf-format:
1001.LeGallFrancois.2484.pdf (0.3 MB)

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 $\Int_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 \emph{quantum} algorithm solving the same problem in time polynomial in the \emph{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.

BibTeX - Entry

@InProceedings{legall:LIPIcs:2010:2484,
  author =	{Fran{\c{c}}ois Le Gall},
  title =	{{An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{549--560},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2484},
  URN =		{urn:nbn:de:0030-drops-24843},
  doi =		{10.4230/LIPIcs.STACS.2010.2484},
  annote =	{Keywords: Quantum algorithms, group isomorphism problem, black-box groups}
}

Keywords: Quantum algorithms, group isomorphism problem, black-box groups
Collection: 27th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2010
Date of publication: 09.03.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI