Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Abelian Group
Cyclic Group
Finite Group
Isomorphism Problem
Quantum Algorithm
Subscribe
Academic
Publications
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem,10.4230/LIPIcs.STACS.2010.2484,François Le Gall
Edit
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
François Le Gall
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 blackbox setting and is the first
quantum algorithm
solving instances of the nonabelian group
isomorphism problem
exponentially faster than the best known classical algorithms.
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 549560, 2010
DOI:
10.4230/LIPIcs.STACS.2010.2484
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
www.informatik.unitrier.de
)
(
arxiv.org
)
(
dx.doi.org
)
References
(32)
Solvable Group Isomorphism
(
Citations: 2
)
Vikraman Arvind
,
Jacobo Torán
Conference:
Structure in Complexity Theory Conference  CoCo
, pp. 91103, 2004
Trading group theory for randomness
(
Citations: 334
)
László Babai
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 421429, 1985
Local expansion of vertextransitive graphs and random generation in finite groups
(
Citations: 91
)
László Babai
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 164174, 1991
Fast Monte Carlo Algorithms for Permutation Groups
(
Citations: 34
)
László Babai
,
Gene Cooperman
,
Larry Finkelstein
,
Eugene M. Luks
,
Ákos Seress
Journal:
Journal of Computer and System Sciences  JCSS
, vol. 50, no. 2, pp. 296308, 1995
On the Complexity of Matrix Group Problems I
(
Citations: 72
)
László Babai
,
Endre Szemerédi
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 229240, 1984
Sort by:
Citations
(1)
An Efficient Quantum Algorithm for Some Instances of the Group Isomorphism Problem
(
Citations: 1
)
François Le Gall
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 549560, 2010