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• 2 citations

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, 200424 citations

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

Y. Inui, François Le Gall

arXiv:quant-ph/0412033Quantum Information and ComputationJul 1, 200712 citations

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

Carlos Magno Martins Cosme, Renato Portugal

arXiv:quant-ph/0703223Mar 23, 20073 citations

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

Jeong San Kim, Eunok Bae, Soojoon Lee

arXiv:1307.1183Jul 4, 20132 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 AJun 14, 20067 citations

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

In this paper we show that certain special cases of the hidden subgroup problem can be solved in polynomial time by a quantum algorithm. These special cases involve finding hidden normal subgroups of solvable groups and permutation groups, finding hidden subgroups of groups with small commutator subgroup and of groups admitting an elementary Abelian normal 2-subgroup of small index or with cyclic factor group.

arXiv:quant-ph/0102014Feb 2, 20012 citations

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• 2 citations

Publisher

Abstract

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

Dec 4, 200424 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$ .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/0412033Quantum Information and ComputationJul 1, 200712 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.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/0703223Mar 23, 20073 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.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.1183Jul 4, 20132 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 AJun 14, 20067 citations

Efficient quantum algorithms for some instances of the non-Abelian hidden subgroup problem

Gábor Ivanyos, Frédéric Magniez, Miklós Sántha

arXiv:quant-ph/0102014Feb 2, 20012 citations

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

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.

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

N

, and provide a polynomial-time quantum computational algorithm solving hidden symmetry subgroup problem of the groups.