Thoughts on the Dihedral Hidden Subgroup Problem

16 Jun 2010

This morning, I've been thinking again about a way to solve the Hidden Subgroup Problem for the dihedral group $D_N={\mathbb{Z}}_N{⋊}_{\phi }{\mathbb{Z}}_2$ (where $\phi \left(1\right)$ is the inversion of ${\mathbb{Z}}_N$). It is well-known that there exists a reduction to the case where the hidden subgroup is $H=⟨(d,1)⟩$ for some $d\in {\mathbb{Z}}_N$. In that case, if we fix $b\in \{0,1\}$, the elements $\left(i,b\right)$ for $i\in {\mathbb{Z}}_N$ form a complete set of coset representatives, so $f$ is one-to-one over ${\mathbb{Z}}_N\times \left\{b\right\}$. Thus, $x\mapsto f\left(x,b\right)$ is a permutation of ${\mathbb{Z}}_N$, a property that will be used below to construct a unitary transform.

First let's recall the classical inductive method to determine $d$. If $M$ is a divisor of $N$, let $N\text{'}=\frac{N}{M}$ and write the euclidean division $d=Md\text{'}+r$. If we are able to determine $r$ in polynomial time, then we can define the oracle $f\text{'}(x,y)=f(Mx+r,y)$ for $x\in {\mathbb{Z}}_{N\text{'}}$ and $y\in {\mathbb{Z}}_2$ and obtain a dihedral HSP with hidden subgroup $⟨(d\text{'},1)⟩$. Since the prime factorization has only $O\left(\log N\right)$ factors, we can repeat this inductive step to get an efficient algorithm. Of course, this is likely to be useful only when the factors are small for otherwise it may be as much difficult to determine $r$ as to determine the whole $d$. One interesting case is $N=2^n$ and $M=2$: at each step, $N$ remains a power of 2 and we determine the parity of $d$.

For $0\le l<M$, we consider the $N\text{'}$-dimensional subspace spanned by the vectors $\mid lN\text{'}+m⟩$ for $0\le m<N\text{'}$. Since these $M$ subspaces are orthogonal, we can construct a unitary transform by applying a Quantum Fourier Transform $F_{N\text{'}}$ on each subspace separately. Finally, we apply the permutation mentionned at the beginning for $b=0$. We get a unitary transform $W$ below where $x=Mi+k$ is the euclidean division of $x$ by $M$:

$$\forall x\in Z_N,W\mid x⟩=\frac{1}{\sqrt{N\prime }}\sum _{j=0}^{N\prime -1}{e}^{2i\pi \frac{ij}{N\prime }}\mid f(Mj+k,0)⟩$$

Now, let's consider the superposition (again, we see that it is well-defined by considering the permutation mentionned at the beginning for $b=1$):

$$\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi,1)⟩$$

The state can be rewritten, using the fact that $f$ is constant on $H=⟨(d,1)⟩$:

$$\begin{array}{rl}\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi,1)⟩& =\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi-d,0)(d,1)⟩\\ & =\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi-d,0)⟩\\ & =\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi-\left(Md\prime +r\right),0)⟩\\ & =\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(M(i-d\prime +(N\prime -1))+(M-r),0)⟩\\ & =\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f(Mi+(M-r),0)⟩\end{array}$$

Applying $W^{-1}$ to this state gives $\mid M-r \mathrm{mod} \left(M\right)⟩$ and so the value of $r$ by a measurement in the standard basis.

Two questions remain: can we implement $W$ and create the state $\mid \Psi ⟩$ efficiently? If $N=2^n$ and $M=2$, there are many simplifications because we are working with qubits. In that case, it is easy to see that the answer to the previous questions is affirmative if we have gates $V_{f,b}\mid x⟩=\mid f\left(x,b\right)⟩$ implementing the permutation mentioned at the beginning. However, it is not clear how to build $V_{f,b}$ from the gate $U_f$ generally given in the classical presentation of the problem...

update: OK, there is also the trivial solution $N=M,N\text{'}=1$where the algorithm above is just computing $V_{f,0}^{-1}{V}_{f,1}\mid 0⟩=\mid N-d \mathrm{mod} \left(N\right)⟩$. However, I'm still wondering if there is a way to modify the previous method to work with $U_f$.