Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Leibniz international proceedings in informatics

Hidden Subgroup Quantum Algorithms for a Class of Semi-Direct Product Groups

Wim van Dam, Dey, Siladitya

Published Jan 1, 2014• 4 citations
Publisher

Abstract

A quantum algorithm for the Hidden Subgroup Problem over the group Z/p^{r}Z \rtimes Z/q^{s}Z is presented. This algorithm, which for certain parameters of the group qualifies as 'efficient', generalizes prior work on related semi-direct product groups.
DOI
10.4230/lipics.tqc.2014.110

Related papers

An Efficient Algorithm for the Hidden Subgroup Problem over a Class of Semi-direct Product Groups

Yoshifumi Inui, François Le Gall

Abstract. In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zn⋊Zq. The definition of the semi-direct product depending on the choice of an homomorphism, we first analyze the different possibilities for this homomorphism in function of n and q. Then, we present a polynomial-time quantum algorithm for the case Zp r ⋊ Zp when p is an odd prime. Keywords: Quantum Algorithms, Hidden Subgroup Problem, Semi-direct Product 1

•Dec 4, 2004•23 citations

Efficient quantum algorithms for the hidden subgroup problem over semi-direct product groups

Y. Inui, François Le Gall

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$.

arXiv:quant-ph/0412033•Quantum Information and Computation•Jul 1, 2007•24 citations

Quantum algorithm for the hidden subgroup problem on a class of semidirect product groups

Carlos Magno Martins Cosme, Renato Portugal

We present efficient quantum algorithms for the hidden subgroup problem (HSP) on the semidirect product of cyclic groups $\Z_{p^r}\rtimes_ϕ\Z_{p^2}$, where $p$ is any odd prime number and $r$ is any integer such that $r>4$. We also address the HSP in the group $\Z_{N}\rtimes_ϕ\Z_{p^2}$, where $N$ is an integer with a special prime factorization. These quantum algorithms are exponentially faster than any classical algorithm for the same purpose.

arXiv:quant-ph/0703223•Mar 23, 2007•6 citations

Quantum computational algorithm for hidden symmetry subgroup problems on semi-direct product of cyclic groups

Jeong San Kim, Eunok Bae, Soojoon Lee

We characterize the algebraic structure of semi-direct product of cyclic groups, $\Z_{N}\rtimes\Z_{p}$, where $p$ is an odd prime number which does not divide $q-1$ for any prime factor $q$ of $N$, and provide a polynomial-time quantum computational algorithm solving hidden symmetry subgroup problem of the groups.

arXiv:1307.1183•Jul 4, 2013•2 citations

Quantum algorithms for the hidden subgroup problem on some semi-direct product groups by reduction to Abelian cases

Dong Pyo Chi, Jeong San Kim, Soojoon Lee

Physics Letters A•Jun 14, 2006•7 citations

Dihedral Hidden Subgroup Problem: A Survey

Hirotada Kobayashi, François Le Gall

After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.

IPSJ Digital Courier•Jan 1, 2005•7 citations
In this paper, we consider the hidden subgroup problem (HSP) over the class of semi-direct product groups Zpr⋊Zq\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_qZpr​⋊Zq​, for ppp and qqq 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 Zpr⋊Zp\mathbb{Z}_{p^r}\rtimes\mathbb{Z}_pZpr​⋊Zp​, where ppp 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 Zprm⋊Zp\mathbb{Z}^m_{p^r}\rtimes\mathbb{Z}_pZprm​⋊Zp​.
We present efficient quantum algorithms for the hidden subgroup problem (HSP) on the semidirect product of cyclic groups Zpr⋊ϕZp2\Z_{p^r}\rtimes_ϕ\Z_{p^2}Zpr​⋊ϕ​Zp2​, where ppp is any odd prime number and rrr is any integer such that r>4r>4r>4. We also address the HSP in the group ZN⋊ϕZp2\Z_{N}\rtimes_ϕ\Z_{p^2}ZN​⋊ϕ​Zp2​, where NNN is an integer with a special prime factorization. These quantum algorithms are exponentially faster than any classical algorithm for the same purpose.
We characterize the algebraic structure of semi-direct product of cyclic groups, ZN⋊Zp\Z_{N}\rtimes\Z_{p}ZN​⋊Zp​, where ppp is an odd prime number which does not divide q−1q-1q−1 for any prime factor qqq of NNN, and provide a polynomial-time quantum computational algorithm solving hidden symmetry subgroup problem of the groups.
After Shor's discovery of an efficient quantum algorithm for integer factoring, hidden subgroup problems play a central role in developing efficient quantum algorithms. In spite of many intensive studies, no efficient quantum algorithms are known for hidden subgroup problems for many non-Abelian groups. Of particular interest are the hidden subgroup problems for the symmetric group and for the dihedral group, because an efficient algorithm for the former implies an efficient solution to the graph isomorphism problem, and that for the latter essentially solves a certain lattice-related problem whose hardness is assumed in cryptography. This paper focuses on the latter case and gives a comprehensive survey of known facts related to the dihedral hidden subgroup problem.