Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups

Details Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups

2004-12-04

arxiv.org/abs/quant-ph/0412033v3

Quantum Information and Computation, Vol. 7, No. 5&6 (2007), 559-570

Physics

Quantum Physics

10 pages, final version. Algorithms modified to work with black-box groups too

Scientific paper

In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_q$, for p and q prime. We first present a classification of these groups in five classes. Then, we describe a polynomial-time quantum algorithm solving the HSP over all the groups of one of these classes: the groups of the form $\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_p$, where p is an odd prime. Our algorithm works even in the most general case where the group is presented as a black-box group with not necessarily unique encoding. Finally, we extend this result and present an efficient algorithm solving the HSP over the groups $\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_p$.

Affiliated with

Also associated with

No associations

Rating

Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product 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 Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Quantum Algorithms for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-428664