Physics – Quantum Physics
Scientific paper
2010-01-05
Physics
Quantum Physics
20 pages; this is the full version of a paper that will appear in the Proceedings of the 27th International Symposium on Theor
Scientific paper
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.
No associations
LandOfFree
An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Quantum Algorithm for some Instances of the Group Isomorphism Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-539751