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

Abstract

We present efficient quantum algorithms for the hidden subgroup problem (HSP) on the semidirect product of cyclic groups ${\mathbb{Z}}_{p^r}{⋊}_{\varphi }{\mathbb{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 ${\mathbb{Z}}_N{⋊}_{\varphi }{\mathbb{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.

5 pages, no figures

Cited by in corpus (1)

• Quantum Computation Beyond the Circuit Model