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

Abstract

In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups ${\mathbb{Z}}_{p^r}⋊{\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}⋊{\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}}_{p^r}^m⋊{\mathbb{Z}}_p$.

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

References in corpus (3)

• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
• The Symmetric Group Defies Strong Fourier Sampling: Part II

Cited by in corpus (5)

• Quantum Computation Beyond the Circuit Model
• Optimal measurements for the dihedral hidden subgroup problem
• Normalizer Circuits and Quantum Computation
• How a Clebsch-Gordan Transform Helps to Solve the Heisenberg Hidden Subgroup Problem
• Abelian Hypergroups and Quantum Computation