Physics Letters A

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

Published Jun 14, 2006• 7 citations

Publisher

DOI: 10.1016/j.physleta.2006.06.014

Related papers

Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups of Cyclic Groups

Yoshifumi Inui, Le Francois

IEICE Technical Report; IEICE Tech. Rep.Apr 11, 20050 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

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Hari Krovi, Martin Rötteler

Lecture notes in computer scienceJan 1, 20089 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

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

Mauro E. S. Morales

quant-pharXiv:2608.05321Aug 7, 20260 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

Gábor Ivanyos, Luc Sanselme, Miklós Sántha

arXiv:quant-ph/0701235Lecture notes in computer scienceJan 1, 200720 citations

Physics Letters A

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

Published Jun 14, 2006• 7 citations

Publisher

DOI: 10.1016/j.physleta.2006.06.014

Related papers

Quantum Algorithms for the Hidden Subgroup Problem over Semidirect Product Groups of Cyclic Groups

Yoshifumi Inui, Le Francois

IEICE Technical Report; IEICE Tech. Rep.Apr 11, 20050 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

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over Weyl-Heisenberg Groups

Hari Krovi, Martin Rötteler

Lecture notes in computer scienceJan 1, 20089 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

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

An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups

Gábor Ivanyos, Luc Sanselme, Miklós Sántha

arXiv:quant-ph/0701235Lecture notes in computer scienceJan 1, 200720 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

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