An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups

Details An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups

2007-07-09

arxiv.org/abs/0707.1260v1

Physics

Quantum Physics

12 pages

Scientific paper

In this paper we extend the algorithm for extraspecial groups in \cite{iss07}, and show that the hidden subgroup problem in nil-2 groups, that is in groups of nilpotency class at most 2, can be solved efficiently by a quantum procedure. The algorithm presented here has several additional features. It contains a powerful classical reduction for the hidden subgroup problem in nilpotent groups of constant nilpotency class to the specific case where the group is a $p$-group of exponent $p$ and the subgroup is either trivial or cyclic. This reduction might also be useful for dealing with groups of higher nilpotency class. The quantum part of the algorithm uses well chosen group actions based on some automorphisms of nil-2 groups. The right choice of the actions requires the solution of a system of quadratic and linear equations. The existence of a solution is guaranteed by the Chevalley-Warning theorem, and we prove that it can also be found efficiently.

Affiliated with

Also associated with

No associations

Rating

An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups 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 the hidden subgroup problem in nil-2 groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-159271