arXiv:2202.04047 · Quantum Information and Computation

An exact quantum hidden subgroup algorithm and applications to solvable groups

Muhammad Imran, Gábor Ivanyos

Published May 30, 2022• 1 citation

Abstract

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in $\Z_{m^k}^n$. The algorithm uses the quantum Fourier transform modulo $m$ and does not require factorization of $m$. For smooth $m$, i.e., when the prime factors of $m$ are of size $(\log m)^{O(1)}$, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general $m$, the algorithm of Mosca and Zalka is available. Even for $m=3$ and $k=1$ our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as $m$. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

DOI: 10.26421/qic22.9-10-4

Related papers

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

Demerson Nunes Gonçalves, Renato Portugal

arXiv:1104.1361Apr 7, 20113 citations

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Tharso D. Fernandes, Carlos Magno Martins Cosme

TEMA (São Carlos)Aug 24, 20177 citations

Hidden Translation and Translating Coset in Quantum Computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

arXiv:quant-ph/0211091SIAM Journal on ComputingJan 1, 201415 citations

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

Mauro E. S. Morales

quant-pharXiv:2608.05321Aug 7, 20260 citations

The Hidden Subgroup Problem for Generalized Quaternions

Julia Tumasova Upton

The hidden subgroup problem is a pivotal problem in quantum computation since it reflects the structure of tasks for which quantum algorithms significantly outperform classical algorithms. In this paper, a quantum algorithm that solves the hidden subgroup problem over the generalized quaternion group is developed. The algorithm employs the abelian quantum Fourier transform and Kuperberg sieve to reveal the hidden subgroup.

International Conference on Quantum, Nano and Micro Technologies (ICQNM)Feb 1, 20101 citation

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Renato Portugal, Tharso D. Fernandes

Proceeding Series of the Brazilian Society of Computational and Applied MathematicsNov 18, 20150 citations

arXiv:2202.04047 · Quantum Information and Computation

An exact quantum hidden subgroup algorithm and applications to solvable groups

Muhammad Imran, Gábor Ivanyos

Published May 30, 2022• 1 citation

arXiv HTML PDF

Abstract

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in

\Z_{m^k}^n

. The algorithm uses the quantum Fourier transform modulo

m

and does not require factorization of

m

. For smooth

m

, i.e., when the prime factors of

m

are of size

(\log m)^{O(1)}

, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general

m

, the algorithm of Mosca and Zalka is available. Even for

m=3

and

k=1

our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as

m

. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

DOI: 10.26421/qic22.9-10-4

Related papers

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

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Tharso D. Fernandes, Carlos Magno Martins Cosme

The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups $\Z_{N}\rtimes\Z_{q^s}$ where $N$ is an integer with a special prime factorization, $q$ prime number and $s$ any positive integer.The hidden subgroup problem (HSP) plays an important role in quantum computation, because many quantum algorithms that are exponentially faster than classical algorithms are special cases of the HSP. In this paper we show that there exist a new efficient quantum algorithm for the HSP on groups $\Z_{N}\rtimes\Z_{q^s}$ where $N$ is an integer with a special prime factorization, $q$ prime number and $s$ any positive integer.

TEMA (São Carlos)Aug 24, 20177 citations

Hidden Translation and Translating Coset in Quantum Computing

Katalin Friedl, Gábor Ivanyos, Frédéric Magniez +2 more

We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in $\mathbb{Z}_p^n$ , whenever $p$ is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group $G$ is reducible to instances of Translating Coset in $G/N$ and $N$ , for appropriate normal subgroups $N$ of $G$ . Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.We give efficient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of nonabelian solvable groups, including solvable groups of constant exponent and of constant length derived series. Our algorithms are recursive. For the base case, we solve efficiently Hidden Translation in $\mathbb{Z}_p^n$, whenever $p$ is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group $G$ is reducible to instances of Translating Coset in $G/N$ and $N$, for appropriate normal subgroups $N$ of $G$. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

arXiv:quant-ph/0211091SIAM Journal on ComputingJan 1, 201415 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

The Hidden Subgroup Problem for Generalized Quaternions

Julia Tumasova Upton

International Conference on Quantum, Nano and Micro Technologies (ICQNM)Feb 1, 20101 citation

An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian Groups

Demerson Nunes Gonçalves, Renato Portugal, Tharso D. Fernandes

Proceeding Series of the Brazilian Society of Computational and Applied MathematicsNov 18, 20150 citations

We present a polynomial time exact quantum algorithm for the hidden subgroup problem in

\Z_{m^k}^n

. The algorithm uses the quantum Fourier transform modulo

m

and does not require factorization of

m

. For smooth

m

, i.e., when the prime factors of

m

are of size

(\log m)^{O(1)}

, the quantum Fourier transform can be exactly computed using the method discovered independently by Cleve and Coppersmith, while for general

m

, the algorithm of Mosca and Zalka is available. Even for

m=3

and

k=1

our result appears to be new. We also present applications to compute the structure of abelian and solvable groups whose order has the same (but possibly unknown) prime factors as

m

. The applications for solvable groups also rely on an exact version of a technique proposed by Watrous for computing the uniform superposition of elements of subgroups.

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

\Z_{N}\rtimes\Z_{q^s}

where

N

is an integer with a special prime factorization,

q

prime number and

s

any positive integer.

\mathbb{Z}_p^n

, whenever

p

is a fixed prime. For the induction step, we introduce the problem Translating Coset generalizing both Hidden Translation and Hidden Subgroup and prove a powerful self-reducibility result: Translating Coset in a finite solvable group

G

is reducible to instances of Translating Coset in

G/N

and

N

, for appropriate normal subgroups

N

G

. Our self-reducibility framework, combined with Kuperberg's subexponential quantum algorithm for solving Hidden Translation in any abelian group, leads to subexponential quantum algorithms for Hidden Translation and Hidden Subgroup in any solvable group.

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