arXiv:1307.1183

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

Jeong San Kim, Eunok Bae, Soojoon Lee

Published Jul 4, 2013• 2 citations

Abstract

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.

DOI: 10.48550/arxiv.1307.1183

Related papers

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

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

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Mauro E. S. Morales

quant-pharXiv:2608.05321Aug 7, 20260 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

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

Wim van Dam, Dey, Siladitya

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.

Leibniz international proceedings in informaticsJan 1, 20142 citations

Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups

Demerson Nunes Gonçalves, Renato Portugal

arXiv:1104.1361Apr 7, 20113 citations

arXiv:1307.1183

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

Jeong San Kim, Eunok Bae, Soojoon Lee

Published Jul 4, 2013• 2 citations

arXiv HTML PDF

Abstract

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.

DOI: 10.48550/arxiv.1307.1183

Related papers

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

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

The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups

Mauro E. S. Morales

Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$ , with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$ , for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$ , where $\mathrm{Exp}(A)$ is the exponent of $A$ . Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$ . This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$ , studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).Several early quantum algorithms, including Simon's algorithm and Shor's period-finding are instances of the hidden subgroup problem (HSP) over finite abelian groups. No polynomial-time quantum algorithm is known for the HSP over arbitrary non-abelian finite groups. The non-Abelian case is of particular interest because some instances, such as the dihedral and symmetric group HSPs, are connected to lattice problems and graph isomorphism, respectively. In this work, we give polynomial-time quantum algorithms for two further families containing non-Abelian groups. First, we consider groups of the form $G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}$, with $A$ finite Abelian, $p$ prime, $k\in \mathbb{N}$ and the action of $\mathbb Z_{p^k}$ is generated by the scalar automorphism $a\mapstoμa$, for some $μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times$, where $\mathrm{Exp}(A)$ is the exponent of $A$. Our algorithm is efficient when $A$ has bounded generator rank and $\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)$. This includes the case $A=\mathbb{Z}_N$ for $N\in\mathbb{N}$ and $k=1$, studied by Bacon, Childs and van Dam (FOCS 2005), and $A=\mathbb{Z}_{q^r}$ with $q$ prime and $r\in \mathbb{N}$ studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).

quant-pharXiv:2608.05321Aug 7, 20260 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

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

Wim van Dam, Dey, Siladitya

Leibniz international proceedings in informaticsJan 1, 20142 citations

Solution to the Hidden Subgroup Problem for a Class of Noncommutative Groups

Demerson Nunes Gonçalves, Renato Portugal

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group $\Z_{p^r} \rtimes \Z_{q^s}$ , when $p^r/q= \up{poly}(\log p^r)$, where $p$ , $q$ are any odd prime numbers and $r, s$ are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms can be casted in the HSP structure. In this paper, we present a new polynomial-time quantum algorithm that solves the HSP over the group $\Z_{p^r} \rtimes \Z_{q^s}$, when $p^r/q= \up{poly}(\log p^r)$, where $p$, $q$ are any odd prime numbers and $r, s$ are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.

arXiv:1104.1361Apr 7, 20113 citations

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.

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

G=A\rtimes_{\varphi} \mathbb{Z}_{p^k}

, with

A

finite Abelian,

p

prime,

k\in \mathbb{N}

and the action of

\mathbb Z_{p^k}

is generated by the scalar automorphism

a\mapstoμa

, for some

μ\in\mathbb Z_{\operatorname{Exp}(A)}^\times

, where

\mathrm{Exp}(A)

is the exponent of

A

. Our algorithm is efficient when

A

has bounded generator rank and

\mathrm{Exp}(A)/p=\mathrm{polylog}(|G|)

. This includes the case

A=\mathbb{Z}_N

for

N\in\mathbb{N}

and

k=1

, studied by Bacon, Childs and van Dam (FOCS 2005), and

A=\mathbb{Z}_{q^r}

with

q

prime and

r\in \mathbb{N}

studied by van Dam and Dey (TQC 2014). Second, we give a polynomial-time quantum algorithm for finite quasi-Hamiltonian groups under a mild assumption on the input structure. Quasi-Hamiltonian groups are finite nilpotent groups with modular subgroup lattice, or equivalently the finite groups in which every subgroup is permutable. As far as we know, this is the first quantum algorithm to exploit the modularity of the subgroup lattice for solving the HSP. This extends, under the aforementioned structured input assumption, the quantum algorithm for Dedekind groups given by Hallgren, Russell, and Ta-Shma (SIAM J. Comput. 32, 2003).

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.

\Z_{p^r} \rtimes \Z_{q^s}

, when $p^r/q= \up{poly}(\log p^r)$, where

p

q

are any odd prime numbers and

r, s

are any positive integers. To find the hidden subgroup, our algorithm uses the abelian quantum Fourier transform and a reduction procedure that simplifies the problem to find cyclic subgroups.