%% Antes de processar este arquivo LaTeX (LaTeX2e) deve
%% verificar que o arquivo TEMA.cls estah no mesmo
%% diretorio. O arquivo TEMA.cls pode ser obtido do
%% endereco www.sbmac.org.br/tema.

\documentclass{TEMA}

%\usepackage[brazil]{babel}      % para texto em Português
\usepackage[english]{babel}    % para texto em Inglês

\usepackage[latin1]{inputenc}   % para acentuação em Português
%\input{P-margin.inf}

\usepackage[dvips]{graphics}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{epsfig}

%\usepackage{graphics}
%\usepackage{subfigure}
%\usepackage{graphicx}
%\usepackage{epsfig}
\usepackage[centertags]{amsmath}
\usepackage{graphicx,indentfirst,amsmath,amsfonts,amssymb,amsthm,newlfont}
\usepackage{longtable}
\usepackage{cite}
\usepackage[usenames,dvipsnames]{color}
\usepackage{algorithm}
\usepackage{algorithmic}

\newcommand{\B}{{\tt\symbol{92}}}
\newcommand{\til}{{\tt\symbol{126}}}
\newcommand{\chap}{{\tt\symbol{94}}}
\newcommand{\agud}{{\tt\symbol{13}}}
\newcommand{\crav}{{\tt\symbol{18}}}



\newenvironment{demo}{\noindent{\bf Proof:}}{\\\hspace*{\fill}\bloco}
\newcommand{\bloco}{\hfill\rule{2mm}{2mm}}
\newcommand{\al}{\alpha}
\newcommand{\p}{\psi}
\newcommand{\ep}{\varepsilon}
\newcommand{\lam}{\lambda}
\newcommand{\ka}{\kappa}
\newcommand{\LB}{\left|}
\newcommand{\RB}{\right|}
\newcommand{\rnor}{\vartriangleright}
\newcommand{\lnor}{\vartriangleleft}
\newcommand{\f}{\phi}
\newcommand{\vf}{\varphi}
\newcommand{\LL}{\left\langle}
\newcommand{\RR}{\right\rangle}
\newcommand{\LP}{\left(}
\newcommand{\RP}{\right)}
\newcommand{\pt}{\forall}
\newcommand{\dsp}{\displaystyle}
\newcommand{\om}[2]{\omega_{#1}^{#2}}
\newcommand{\braket}[2]{\ensuremath{\langle #1 |#2\rangle}} % quantum bracket
\newcommand{\brakett}[3]{\ensuremath{\langle #1 |#2| #3 \rangle}} % 3 place quantum bracket
\newcommand{\aut}[1]{{\rm{Aut}}\left(#1\right)}
\newcommand{\mdc}[1]{{\rm{mdc}}\left(#1\right)}
\newcommand{\qbit}{{\it qbit}}
\newcommand{\qbits}{{\it qbits}}
\def\grp#1{\left\langle #1\right\rangle}     % variable < >
\def\sVEV#1{\left\langle #1\right\rangle}     % variable < >
%\def\bra#1{\Big\langle #1\Big|}               % < |
%\def\ket#1{\Big| #1\Big\rangle}               % | >
\def\sbra#1{\left\langle #1\right|}           % variable < |
\def\sket#1{\left| #1\right\rangle}           % variable | >
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\X{\mathcal{X}}
\def\G{\mathcal{G}}
\def\H{\mathcal{H}}
\def\A{\mathcal{A}}
\def\ze#1{\mathcal{Z}\left( #1\right)}
\def\w{\omega}
%\def\cl{\mathcal{c}}
\def\up{\textup}
\floatname{algorithm}{Algorithm}

\begin{document}

%********************************************************
\title
    {An Efficient Quantum Algorithm for the Hidden Subgroup Problem over some Non-Abelian
    Groups~\thanks{Paper presented to III CMAC-SE, Vitória, 2015.}}

\author
 {
%   Author A%
%     \thanks{email@email.br}\,,
%     Address Brazil
%     \\ \\
%     Author B%
%     \thanks{email@email.br}\,,
%     Address Brazil
%     \\ \\
%     Author C%
%     \thanks{email@email.br}\,,
%     Address Brazil
     }

\criartitulo

%\runningheads {Author A, Author B and Author C}{Instruções para
%Preparação de Trabalhos}
%
\begin{abstract}
{\bf Abstract}. 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.

%{\bf Palavras-chave}. Palavra-chave 1, palavra-chave 2,
%palavra-chave 3.

\noindent {\bf Keywords}. Quantum Algorithms, Hidden Subgroup
Problem, Quantum Computational Group Theory
\end{abstract}


%********************************************************
\newsec{Introduction}

    The most important problem in group theory in terms of quantum
algorithms is called hidden subgroup problem (HSP)~\cite{cris}.
The HSP can be described as follows: given a group $G$ and a
function $f:G \rightarrow X$ on some set $X$ such that $f(x)=f(y)$
iff $x\cdot H=y\cdot H$ for some subgroup $H$, the problem
consists in determining a generating set for $H$ by querying the
function $f$. We say that the function $f$ hides the subgroup $H$
in $G$ or that $f$ separates the cosets of $H$ in $G$. A quantum
algorithm for the HSP is said to be efficient when the running
time is $O(\up{poly}(\log |G|))$. There are many examples of
efficient quantum algorithms for the HSP in particular
groups~\cite{simon94,shor2}. It is known that for finite abelian
groups, the HSP can be solved efficiently on a quantum
computer~\cite{cris}.  On the other hand, an efficient solution
for a generic non-abelian group is not known. Two important groups
in this context are the symmetric and the dihedral groups. An
efficient algorithm for solving the HSP for the former would imply
in an efficient solution for the graph isomorphism
problem~\cite{Beals,boneh, hoyer1997, ettinger1999} and for the
latter would solve instances of the problem of finding the
shortest vector in a lattice, which has applications in
cryptography~\cite{Regev1}.

One way to design new quantum algorithms for the HSP is to
investigate the structures of all subgroups of a given group, and
then to find a quantum algorithm applicable to each subgroup
structure. Following this, Inui and Le Gall presented an efficient
quantum algorithm for the HSP on groups of the form
$\mathbb{Z}_{p^r}^m\rtimes \mathbb{Z}_{p}$ with prime $p$ and
positive integers $r$ and $m$~\cite{inui2005efficient}. Later,
Cosme~\cite{cmagnothesis} presented an efficient quantum algorithm
for the HSP in $\Z_{p^r}\rtimes_\phi\Z_{p^s}$ where $p$ is any odd
prime number, $r$ and $s$ are positives integers and the
homomorphism $\phi$ is given by the root $tp^{r-s+l}+1$ such that
$r\geq 2s-l$. Subsequently, Gonçalves et al. presented an
efficient quantum algorithm for the HSP in $\Z_{p} \rtimes
\Z_{q^s}$, with $p/q = \up{poly}( \log p)$, where $p$, $q$ are
distinct odd prime numbers and $s$ is an arbitrary positive
integer~\cite{DRC1, demersonthesis}. The case $\Z_{p^r} \rtimes
\Z_{q^s}$ with $p,q$ distinct odd prime numbers and $r,s>0$ such
that $p^r/q^t= \up{poly}(\log p^r)$ was discussed
in~\cite{DNGarXiv:1104.1361}. The parameter $t\in\{0,1,\ldots,s\}$
characterizes the group. The case $t=0$ reduces to the abelian
group $\Z_{p^r} \times \Z_{q^s}$ and the case $t=1$ was addressed
by the authors, with unsuccessful results. This work established,
for the first time, a complete description of the structure of the
subgroups of $\Z_{p^r} \rtimes \Z_{q^s}$. Recently, using the
algebraic structure of the subgroups of $\Z_{p^r} \rtimes
\Z_{q^s}$, van Dam and Dey~\cite{wim14} presented a new quantum
algorithm for the HSP over $\Z_{p^r} \rtimes \Z_{q^s}$ for all
possible values of $t\in\{0,1,\ldots,s\}$ by imposing a
restriction on the parameters $p$ and $q$: the relative sizes of
subgroups are bounded by $p^r/q^{t-j}\in O(\mbox{poly}(\log
p^r))$, where $j\in\{0,\ldots,t-1\}$.

In this article, we describe a new efficient quantum algorithm to
solve the HSP in the specific class of non-abelian groups, i.e.,
the semi-direct product groups of the form  $G=
\Z_{N}\rtimes\Z_{q^s}$, where, $N$ is factorized as
$p_1^{r_1}\ldots p_n^{r_n}$ and there exists a $1\leq k \leq n$
such that $q^t$ ($q$ odd prime) divides $p_k-1$ and $q$ does not
divide $p_i-1$ for all $i\neq k$. The parameter $t$ is related to
the type of the homomorphism that describes the group, as can be
checked in Sec.~\ref{semi-direct} Using a similar approach
presented in~\cite{dong}, we define an isomorphism between $
\Z_{N}\rtimes\Z_{q^s}$ and the direct product of
$\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$ with cyclic groups, reducing
the HSP in $G$ to similar HSPs the solutions of which are already
known.


%we show that the HSP in $G$ reduces the problem to similar ones
%with known efficient solution. We show that the HSP over $G$
%reduces to the HSP over
%
%By employing an isomorphism between $ \Z_{N}\rtimes\Z_{q^s}$ and
%the direct product of $\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$ with
%cyclic groups we have shown that the HSP can be reduced to similar
%HSPs the solutions of which are already known.


%Our algorithm was inspired by the work of Chi et. al.~\cite{dong}
%that solved the HSP in $\Z_{N}\rtimes\Z_{p}$, where $p$ is a prime
%that does not divide $p_i-1$ for any of the prime factors $p_i$ of
%$N$. As in~\cite{dong}, we use the homomorphic properties of $G=
%\Z_{N}\rtimes\Z_{q^s}$ to reduce the problem to similar ones with
%known efficient solutions. As far as we know this is the first
%efficient quantum algorithm to solve the HSP in this class of
%groups.

This work is organized as follows. In Section~\ref{semi-direct},
we give the relevant definitions and results concerning the
semi-direct product groups and explain its homomorphisms and their
properties. In Section~\ref{sec3}, we present our main result and
we show that there exist an efficient quantum algorithm for the
HSP on the groups. In Section~\ref{conclusion}, we draw our
conclusions.

%\section{Preliminaries}



\section{Semi-direct Product Groups}\label{semi-direct}

The semi-direct product of two groups $A$ and $B$ is defined by a
homomorphism  $\phi : B \rightarrow \mbox{Aut}(A )$, where
$\textup{Aut}(A)$ denotes the automorphism group of $A$. The
semi-direct product $A\rtimes_{\phi} B$ is the set $\{(a,b):a\in
A, b\in B\}$ with the group operation defined as
$(a,b)(a',b')=(a+\phi(b)(a'),b+b')$. One easily checks that the
group inversion operation satisfies $(a,b)^{-1}=(\phi(-b)(-a),
-b)$.

In this paper we consider the HSP on the semi-direct product
groups $G= \Z_{N}\rtimes_{\phi }\ \Z_{q^s}$ for positive integers
$N$ and $s$ and odd prime number $q$. We assume that the prime
factorization of $N$ is $p_1^{r_1}\ldots p_n^{r_n}$ and there
exist a $1\leq k \leq n$  such that $q^t$ divides $p_k-1$ and $q$
does not divide $p_i-1$ for all $i\neq k$. The parameter
$t\in\{0,1,\ldots,s\}$ characterizes the group as shown in the
following.

The elements $x=(1,0)$ and $y=(0,1)$ generate the groups
$\Z_{N}\rtimes_{\phi} \Z_{q^s}$. Since $\mbox{Aut}(\Z_{N})$ is
isomorphic to $ \Z_{N}^{*}$, the homomorphism $\phi$ is completely
determined by $\alpha:=\phi(1)(1)\in \Z_{N}^{*}$ and
$\phi(b)(a)=a\alpha^b$ for all $a\in \Z_N$ and $b\in \Z_{q^s}$.
Now, note that $\phi (0) =\phi (q^s):\Z_ {N}\rightarrow\Z_{N}$ is
the identity element of the group Aut$(\Z_{N})$. Then
$\alpha^{q^s} =\phi(q^s)(1)=1$. If the element
$\alpha\in\Z_{N}^{*} $ satisfies the congruence relation $X^{q^s}=
1 \mod N$, then it defines the semi-direct product $\Z_
{N}\rtimes_{\alpha}\Z_ {q^s} $. In this case, we must have
$\textup{ord}(\alpha)=q^{t}$ for some integer $0\le t \le s$. The
case $t=0$ reduces to the direct product $\Z_{N}\times\Z_{q^s} $,
which is an abelian group. An efficient solution for the HSP is
known for this case~\cite{cris}. Since $\alpha \in \Z_{N}^{*}$,
$q^t$ divides $\varphi(N)=p_1^{r_1-1}\ldots
p_n^{r_n-1}(p_1-1)\ldots(p_n-1)$, where $\varphi$ is the Euler
phi-function. Then, we can choose the option $q^t\mid p_n-1$ with
no loss of generality.


%Because $q^t$ must divide $p_1^{r_1}\ldots
%p_n^{r_n}(p_1-1)\ldots(p_n-1)$ (the order of $\Z_N^{*}$), we
%choose the option $q^t\mid p_n-1$ with no loss of generality.

Now note that due to factorization of $N$, the group $\Z_{N}$ is
isomorphic to product of cyclic groups $\Z_{p_1^{r_1}}\times
\ldots \times \Z_{p_n^{r_n}}$, which implies
\begin{equation}
\Z_{N}\rtimes_{\phi} \Z_{q^s}\cong(\Z_{p_1^{r_1}}\times \ldots
\times \Z_{p_n^{r_n}})\rtimes_{\phi} \Z_{q^s}.
\end{equation}
%Since $\Z_{N}$ is isomorphic to $\Z_{p_1^{r_1}}\times \ldots
%\times \Z_{p_n^{r_n}}$ the group $\Z_{N}\rtimes_{\phi} \Z_{q^s}$
%is isomorphic to $G=(\Z_{p_1^{r_1}}\times \ldots \times
%\Z_{p_n^{r_n}})\rtimes_{\phi} \Z_{q^s}$.
The elements of $(\Z_{p_1^{r_1}}\times \ldots \times
\Z_{p_n^{r_n}})\rtimes_{\phi}\ \Z_{q^s}$ have the form
$((a_1,\ldots,a_n),b)$, where $(a_1,\ldots,a_n)\in
\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_n^{r_n}}$ and $b\in
\Z_{q^s}$. For each $b$ in $\Z_{q^s}$ the element $\phi(b)$ is an
automorphism on $\Z_{p_1^{r_1}}\times \ldots \times
\Z_{p_n^{r_n}}$ such that $\alpha=\phi(1)(1)$ is an element in
$\Z_{p_1^{r_1}}^{*}\times \ldots \times \Z_{p_n^{r_n}}^{*}$ of
order $q^t$. Note that $\Z_{p_i^{r_i}}$ is isomorphic to the
subgroup $\mathcal{I}_1\times \Z_{p_i^{r_i}}\times \mathcal{I}_2$
of $\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_n^{r_n}}$, where
$\mathcal{I}_1$ is the identity on
$\Z_{p_1^{r_1}}\times\ldots\times\Z_{p_{i-1}^{r_{i-1}}}$ and
$\mathcal{I}_2$ is the identity on
$\Z_{p_{{i+1}}^{r_{i+1}}}\times\ldots\times\Z_{p_{n}^{r_{n}}}$,
for all $i=1,\ldots,n$. Thus, we can identify an element $a_i$ in
$\Z_{p_i^{r_i}}$ with the point $\overline{ a_i}$ in
$\mathcal{I}_1\times \Z_{p_i^{r_i}}\times \mathcal{I}_2$ such that
it has an integer value $a_i$ in the $i$-th coordinate and $0's$
elsewhere.
%Using this notation we can state following two results

Now we are ready to state the following results.
\begin{lemmaTEMA}\label{lemma1}
Let $\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_n^{r_n}}$ and
$\Z_{q^s}$ be finite abelian groups with distinct odd prime
numbers $p_1,\ldots,p_n, q$ and positive integers $r_1,\ldots,r_n$
and $s$. Define the semi-direct product group
$(\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_n^{r_n}})\rtimes_{\phi}
\Z_{q^s}$. Then, for each $b\in \Z_{q^s}$ and $a_i
\in\Z_{p_i^{r_i}}$ there exists a $ c_i\in\Z_{p_i^{r_i}}$ such
that $\phi(b)(\overline{ a_i})= \overline{ c_i}$.
\end{lemmaTEMA}
\begin{proof}
Let $e_i$ be elements in  $\Z_{p_1^{r_1}}\times \ldots \times
\Z_{p_n^{r_n}}$ with all components equal zero except the $i$-th
one which is 1. It is enough to show that
$\phi(b)(e_i)=\overline{d_i}$, for some $d_i\in\Z_{p_i^{r_i}}$. In
fact, let us suppose that $\phi(b)(e_i)=(d_1,\ldots,d_n)$. Note
that
\begin{eqnarray*}
(0,\ldots,0)&=&\phi(b)(0,\ldots,0)=\phi(b)(0,\ldots,0,p_i^{r_i},0,\ldots,0)=p_i^{r_i}\phi(b)
e_i\\
&=& (p_i^{r_i}d_1,\ldots,p_i^{r_i}d_n).
\end{eqnarray*}
Then, for all $j=1,\ldots,n$ we have
$p_i^{r_i}a_j\,\equiv\,0\textup{ mod }p_j^{r_j}$ and this implies
that $a_j\,\equiv\,0\textup{ mod }p_j^{r_j}$ for all $j\neq i$.
Hence, $\phi(b)(e_i)=(0\ldots,d_i,0,\ldots,0)=\overline{d_i}$ as
was to be shown.
\end{proof}
%Besides, since $\alpha$ is an element in $\Z_{N}^{*}$ of order
%$q^t$ then $q^t$ must be a divisor of $\varphi(N)=p_1^{r_1}\ldots
%p_n^{r_n}(p_1-1)\ldots(p_n-1)$, where $\varphi$ is the Euler
%phi-function. Without loss of generality, we can suppose $q^t$
%divides $p_k-1$.
\begin{lemmaTEMA}
\label{lemma2}Let $N$ be a positive integer with prime
factorization $p_1^{r_1}\ldots p_n^{r_n}$ and $q$ an odd prime
such that $q\neq p_i$ and $s$ a positive integer. Define the
semi-direct product group $G=\Z_{N}\rtimes_{\alpha} \Z_{q^s}$ for
an $\alpha \in \Z_N^{*}$. Let $t\in\{1,\ldots,s\}$ be the smallest
positive integer such that $\alpha^{q^t}=1$. Let us assume that
there exist a $1\leq k \leq n$ such that $q^t \mid p_k-1$ and
$q\nmid p_i-1$ for all $i\neq k$. By choosing $k=n$ (WLOG) we have
%$$
%\Z_{N}\rtimes_{\alpha} \Z_{q^s}\cong $q^t\mid p_n-1$
%(\Z_{p_1}^{r_1}\times\ldots\times\Z_{p_{n-1}}^{r_{n-1}})\times (
%$$
\begin{equation}
\Z_N\rtimes_{\phi}\Z_{q^s}\cong(\Z_{p_1^{r_1}}\times \ldots \times
\Z_{p_{n-1}^{r_{n-1}}})\times (\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}),
\end{equation}
for some homomorphism $\psi$ from $\Z_{q^s}$ into the group of
automorphisms of $\Z_{p^{r}}$ and $p=p_n$ and $r=r_n$.
\end{lemmaTEMA}
\begin{proof}
Note that $\phi(q^s)$ is the identity map $\mathcal{I}$ on
$\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_{n}^{r_{n}}}$. For all
$i=1,\ldots,n-1$, follows from Lemma~\ref{lemma1} that $
e_i=\phi(q^s)e_i=(0\ldots,{d_i}^{q^s},\ldots,0)$. Then
${d_i}^{q^s}=1\textup{ mod } p_i^{r_i}$ and
$d_i\in\Z_{p_i^{r_i}}^{*}$ has order $q^{t'}$, for some $t'\in
\{1,\ldots,s\}$. Suppose $d_i\neq 1$. Since $q^{t'}$ divides the
order of $\Z_{p_i^{r_i}}^{*}$ and $\textup{gcd}(p_i,q)=1$, we have
that $q^{t'}$ divides $p_i-1$. But that leads to an absurd, hence
$d_i$ must be 1 and $\phi$ acts trivially on $\Z_{p_1^{r_1}}\times
\ldots \times \Z_{p_{n-1}^{r_{n-1}}}$. Thus, there exists a
homomorphism $\psi$ from $\Z_{q^s}$ into the group of
automorphisms of $\Z_{p^{r}}$ ($p=p_n$ and $r=r_n$), such that for
all $b\in \Z_{q^s}$ and all $(a_1,\ldots,a_n)\in
\Z_{p_1^{r_1}}\times\ldots \times\Z_{p_n^{r_n}}$ we have
\begin{equation}
\phi(b)(a_1,\ldots,a_n)=(a_1,\ldots,a_{n-1},\psi(b)(a_n)).
\end{equation}
Now for two elements $g=((a_1\ldots,a_n),b)$ and
$g'=((a_1'\ldots,a_n'),b')$ in $(\Z_{p_1^{r_1}}\times \ldots
\times \Z_{p_n^{r_n}})\rtimes_{\phi}\ \Z_{q^s}$, the group
operation is defined by
\begin{eqnarray}
gg'&=&((a_1,\ldots,a_n)+\phi(b)(a_1',\ldots,a_n'),b+b')\nonumber\\
   &=&((a_1+a_1',\ldots,a_{n-1}+a_{n-1}',a_n+\psi(b)(a_n'),b+b').
\end{eqnarray}
Define the map
\begin{equation}
\Gamma:\Z_{N}\rtimes_{\phi}\ \Z_{q^s}\rightarrow
(\Z_{p_1^{r_1}}\times \ldots \times \Z_{p_{n-1}^{r_{n-1}}})\times
(\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}),
\end{equation}
such that
$\Gamma(a_1,\ldots,a_{n},b))=((a_1,\ldots,a_{n-1}),(a_n,b))$. It
is easy to show that this map is indeed an isomorphism.
\end{proof}

\begin{lemmaTEMA}\label{lemma3}
Let $G_1$ and $G_2$ be finite groups with relatively prime orders.
If $H$ is a subgroup of $G$ then $H=H_1\times H_2$ for some
subgroups $H_1$ of $G_1$ and $H_2$ of $G_2$.
\end{lemmaTEMA}
\begin{proof}
Let $\pi_i:G_1\times G_2 \rightarrow G_i$ such that
$\pi_i(g_1,g_2)=g_i$, $i=1,2$. For any subgroup $H$ of $G_1\times
G_2$ define $H_1=\pi_1(H)\leq G_1$ and $H_2=\pi_2(H)\leq G_2$.
Then $H\leq H_1\times H_2$. We claim that $H=H_1\times H_2$. In
fact, if $(h_1,h_2)\in H_1\times H_2$ it follows from definition
of $H_1$ and $H_2$ that there exist $h_1'\in G_1$ and $h_2'\in
G_2$ such that $(h_1,h_2'),(h_1',h_2)\in H$. From the fact that
$\gcd(|G_1|,|G_2|)=1$ and by the Chinese remainder theorem, there
exist integers $r_1$ and $r_2$ such that
    \begin{equation}\label{TCR}
        \left\{\begin{array}{c}
                r_1\equiv 1 \mod |G_1| \\
                r_1\equiv 0 \mod |G_2|
               \end{array}\right.\;\mbox{and}\;
        \left\{\begin{array}{c}
                r_2\equiv 0 \mod |G_1|\\
                r_2\equiv 1 \mod |G_2|.
               \end{array}\right.
    \end{equation}
   It follows from (\ref{TCR}) that there are integers $k_1,k_2,k_3,k_4$
   such that
    \begin{equation*}
        \left\{\begin{array}{l}
                r_1=k_1|G_1|+1\\
                r_1=k_2|G_2|
               \end{array}\right.\;\mbox{and}\;
        \left\{\begin{array}{l}
                r_2=k_3|G_1|\\
                r_2=k_4|G_2|+1.
               \end{array}\right.
    \end{equation*}
    Thus,
    \begin{eqnarray*}
        (h_1,h_2')^{r_1}&=&(h_1^{r_1},h_2'^{r_1})=(h_1^{k_1|G_1|+1},h_2'^{k_2|G_2|})=(h_1,e_2) \in H\\
        (h_1',h_2)^{r_2}&=&(h_1'^{r_2},h_2^{r_2})=(h_1'^{k_3|G_1|},h_2^{k_4|G_2|+1})=(e_1,h_2) \in H
    \end{eqnarray*}
    where $e_1$ and $e_2$ are the identities elements in the groups $G_1$ and $G_2$, respectively. Hence, $(h_1,h_2)=(h_1,e_2)(e_1,h_2)\in H$.

\end{proof}

\section{Quantum Algorithm for HSP in $\Z_{N}\rtimes_{\phi} \Z_{q^s} $}

\label{sec3}In this section we present an efficient quantum
algorithm that can solve the HSP in $\Z_{N}\rtimes_{\phi} \Z_{q^s}
$, where $N$ is factorized as $N=p_1^{r_1}\ldots p_n^{r_n}$ and
given a $1\leq t\leq s$, there exists a $1\leq k \leq n$ such that
$q^t \mid p_k-1$ and $q\nmid p_i-1$ for all $i\neq k$.

Before stating our main theorem, let us introduce the last two
intermediate results.
\begin{propTEMAi}\label{prop1}
Let $G$ be a finite group, $H$ a subgroup of $G$ and
$f:G\rightarrow X$ the oracle function that hides $H$ in $G$. For
any subgroup $\widetilde{G}$ of $G$ we have
$\widetilde{f}=f\Big|_{\widetilde{G}}:\widetilde{G}\rightarrow X$
hides $\widetilde{H}=H \cap\widetilde{G}$ in $\widetilde{G}$.
\end{propTEMAi}
\begin{proof}
We must show that $\widetilde{f}(a)=\widetilde{f}(b)$ if and only
if $a\widetilde{H}=b\widetilde{H}$, for all $a, b\in
\widetilde{G}$. In fact, let $a, b\in \widetilde{G}$ such that
$\widetilde{f}(a)=\widetilde{f}(b)$. Since $f$ hides $H$ in $G$,
$aH=bH$ which implies $a=bh$, for some $h\in H$. Since  $a, b\in
\widetilde{G}$, we have $h=b^{-1}a\in \widetilde{G}$ which implies
$h\in \widetilde{H}$, hence $a\widetilde{H}=b\widetilde{H}$.
Conversely, if $a\widetilde{H}=b\widetilde{H}$, since
$a\widetilde{H} \subset aH$ and $b\widetilde{H} \subset bH$ we
have $aH\cap bH \neq \emptyset $ which implies $aH=bH$, or
equivalently $\widetilde{f}(a)=\widetilde{f}(b)$.
\end{proof}

\begin{coroTEMAi}\label{coro1}
Let $G_1$ and $G_2$ be finite groups with relatively prime orders.
Then, an efficient solution to the HSP over $G_1$ and $G_2$
implies in an efficient solution to the HSP over the direct
product $G_1\times G_2$.
\end{coroTEMAi}
\begin{proof}
By Lemma~\ref{lemma3}, if $H$ is a subgroup of $G_1\times G_2$
then $H=H_1\times H_2$ for some subgroup $H_1$ of $G_1$ and
subgroup $H_2$ of $G_2$. Let $f$ be the oracle function that hides
$H$ in $G_1\times G_2$. By Proposition~\ref{prop1}, the
restrictions of $f$ to $G_1$ and $G_2$ hide, respectively, $H_1$
and $H_2$. Since the HSP can solved efficiently over the groups
$G_1$ and $G_2$ one can efficiently find generators to $H_1$ and
$H_2$, or equivalently, generators to $H_1\times H_2$.

\end{proof}

Define $N'=N/p_n^{r_n}$ then $\Z_{p_1^{r_1}}\times \ldots \times
\Z_{p_{n-1}^{r_{n-1}}}\cong \Z_{N'}$. By Lemma~\ref{lemma2},
$$
\Z_{N}\rtimes_{\phi} \Z_{q^s} \cong \Z_{N'}\times
(\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}).
$$
The orders of the groups in this direct product are relatively
prime, then by Corollary~\ref{coro1}, the HSP over $
\Z_{N}\rtimes\Z_{q^s}$ can be solved efficiently on a quantum
computer. In fact,
%Hence, from Lemma 3 , if $H$ is a subgroup of $\Z_{N'}\times
%(\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s})$ then $H=H_1\times H_2$, where
%$H_1$ is a subgroup of  $\Z_{N'}$ and $H_2$ is a subgroup of
%$\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$. The HSP on $
%\Z_{N}\rtimes\Z_{q^s}$ reduces to the HSP on each factor by the
%following.
%
%Let $f$ be the oracle function that hides the subgroup $H$ in
%$\Z_{N'}\times (\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s})$. For simplicity
%of notation, let us call $A=\Z_{N'}$ and
%$B=\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$. Define oracle function $f_1$
%by the restriction of $f$ to $A$, which hides $H_1$ in $A$.
%Analogously, define oracle function $f_2$ by the the restriction
%of $f$ to $B$, which hides $H_2$ in $B$.
%%$f_2=\mid_{\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}}$ (restriction of $f$
%%to $\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$)which hides $H_2$ in
%%$\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$.
%The solution of the HSP in the groups $A$ and $B$ with functions
%$f_1$ and $f_2$ determines generators for the subgroups $H_1$ and
%$H_2$, respectively.
the group $\Z_{N'}$ is abelian and the group
$\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$ was addressed
in~\cite{DRC1,DNGarXiv:1104.1361} and recently generalized
by~\cite{wim14}. Therefore, we obtain the following result:
%
%
\begin{thmTEMA}
Let $N$ be a positive integer with prime factorization
$p_1^{r_1}\ldots p_n^{r_n}$, $q$ an odd prime such that $q\neq
p_i$ and $s$ a positive integer. Define the semi-direct product
group $G=\Z_{N}\rtimes_{\alpha} \Z_{q^s}$ for an $\alpha \in
\Z_N^{*}$. Let $t\in\{1,\ldots,s\}$ be the smallest positive
integer such that $\alpha^{q^t}=1$. Let us assume that there exist
a $1\leq k \leq n$ such that $q^t \mid p_k-1$ and $q\nmid p_i-1$
for all $i\neq k$. Then there exists an efficient quantum
algorithm that solves the HSP in the semi-direct product groups
$\Z_{N}\rtimes_{\alpha} \Z_{q^s} $.
\end{thmTEMA}


\section{Conclusion}\label{conclusion}
We have addressed the HSP on the semi-direct product groups $G=
\Z_{N}\rtimes\Z_{q^s}$ where $N$ is factorized as
$N=p_1^{r_1}\ldots p_n^{r_n}$ and given a $1\leq t\leq s$, there
exists a $1\leq k \leq n$  such that $q^t$ divides $p_k-1$ $q\nmid
p_i-1$ for all $i\neq k$. By employing an isomorphism between $
\Z_{N}\rtimes\Z_{q^s}$ and the direct product of
$\Z_{p^{r}}\rtimes_{\psi}\Z_{q^s}$ with cyclic groups we have
shown that the HSP can be reduced to similar HSPs the solutions of
which are already known. This provides a new efficient solution
for the HSP on $G$.


\section*{Acknowledgements}
The authors would like to tank the CNPq and Faperj for financial
support and the anonymous reviewers for their valuable comments
and suggestions to improve the manuscript.


\begin{thebibliography}{8}
\bibitem{Beals}
R.~Beals, ``Quantum computation of {F}ourier transforms over
symmetric groups'', Proc. 29th ACM Symp. on Theory of Computing,
pages 48--53, New York, (1997).

\bibitem{boneh}
D. Boneh and R. J. Lipton, ``Quantum cryptanalysis of hidden
linear functions'', In Lecture Notes in Computer Science, volume
963, pages 424--437, Berlin, (1995).

\bibitem{dong}
D.~P. Chi, J.~S. Kim and S.~Lee, Quantum algorithms for the hidden
subgroup problem on some semi-direct product groups by reduction
to Abelian cases, {\em Physics Letters A}, pages 114--116, (2006).

\bibitem{cmagnothesis}
C.M.M. Cosme, ``Algoritmos Quânticos para o Problema do Subgrupo
Oculto não Abeliano'', Tese de Doutorado, LNCC, Petrópolis, RJ,
2008.

\bibitem{childs}
A.~M. Childs and W.~van Dam, Quantum algorithms for algebraic
problems, {\em Rev. Mod. Phys.}, 82(1): 1--52, (2010).

\bibitem{wim14}
W.~van Dam and S. Dey, ``Hidden Subgroup Quantum Algorithms for a
Class of Semi-Direct Product Groups'', Proc. of 9th Conference on
the Theory of Quantum Computation, Communication and Cryptography,
TQC´14, pages 110--117, (2014).

\bibitem{ettinger1999}
M. Ettinger and P. H{\o}yer, ``A quantum observable for the graph
isomorphism problem'', arXiv:quant-ph/9901029, (1999).

\bibitem{DRC1}
D.~N. Gon\c{c}alves, R.~Portugal, and C.~M.~M. Cosme, ``Solutions
to the hidden subgroup problem on some metacylic groups'', Proc.
4th Worshop on Theory of Quantum Computation, Communication and
Cryptography, LNCS, Springer-Verlag, (2009).

\bibitem{demersonthesis}
D.N. Gonçalves, ``Algoritmos Quânticos para Problemas em Teoria de
Grupo Computacional'', Tese de Doutorado, LNCC, Petrópolis, RJ,
2009.

\bibitem{DNGarXiv:1104.1361}
D.~N. Gonçalves and R.~Portugal, ``Solution to the Hidden Subgroup
Problem for a Class of Noncommutative Groups'', Quantum Physics,
Abstract quant-ph/1104.1361, (2011).

\bibitem{hoyer1997}
P.~Hoyer, ``Efficient quantum transforms'',
arXiv:quant-ph/9702028, (1997).

\bibitem{inui2005efficient}
Y.~Inui and F.~Le~Gall, An efficient quantum algorithm for the
hidden subgroup problem over a class of semi-direct product
groups, {\em Quantum Information and Computation}, (2005).

\bibitem{cris}
C.~Lomont, ``The Hidden Subgroup Problem - Review and Open
Problems'', Quantum Physics, Abstract quant-ph/0411037, (2004).


\bibitem{michele}
M.~Mosca,  ``Quantum algorithms'', Encyclopedia of Complexity and
Systems Science, pages 7088--7118, (2009).

\bibitem{Regev1}
O.~Regev, Quantum Computation and Lattice Problems, {\em SIAM
Journal on Computing,} 33(3):738--760, (2004).

\bibitem{simon94}
D.~R. Simon, ``On the Power of Quantum Computation'', Proceedings
of the 35th Annual Symposium on Foundations of Computer Science,
pages 116--123, (1994).

\bibitem{shor2}
P.~W. Shor, ``Algorithms for quantum computation: discrete logs
and factoring'', Proc. of the 35th Ann. IEEE Symp. on the
Foundation of Computer Science, pages 124--134, (1994).









\end{thebibliography}


\end{document}
\newpage
$ \  \  $  \thispagestyle{myheadings}  \markboth{      }{   }
