# Thoughts on the Dihedral Hidden Subgroup Problem (part 2)

In a previous post, I've proposed a way to solve the Dihedral Hidden Subgroup Problem using a superposition of oracle evaluations. However, it seems to require a way to inverse the functions $x↦f\left(x,.\right)$ which is a bit cheating since we do not have this feature for the classical problem. In this post, we will consider the case $M=\frac{N}{N\text{'}}=2$, $d=2d\text{'}+b$ and try to determine the parity $b$ of $d$. If $N$ is a power of two, this is enough to find $d$ recursively. As in the previous post, the main idea is to consider the superpositions

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

and

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

Using the equality $f\left(g\left(d,1\right)\right)=f\left(g\right)$ we can rewrite the latter state

$\mid {\varphi }_{0}⟩=\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}\mid f\left(2i-b,0\right)⟩$

If $b=0$, the latter state is the same superposition as the former state, over $N\text{'}$ values of ${ℤ}_{N}$. Otherwise, $b=1$ and the latter state is the superposition over the $N\text{'}$ other values of ${ℤ}_{N}$. We let ${f}_{i}^{b}=f\left(2i-b,0\right)$ and measure the product state $\mid {\psi }_{0}⟩\mid {\varphi }_{0}⟩$ in the basis ${\mid x⟩\mid x⟩}_{x\in {ℤ}_{N}}$, ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x, ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x . It turns out that this allows to distinguish the two cases:

• If $b=0$, the product contains vectors with the same coordinates $\mid {f}_{i}^{0}⟩\mid {f}_{i}^{0}⟩$ for $i\in {ℤ}_{N}$. For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs $\mid {f}_{{i}_{1}}^{0}⟩\mid {f}_{{i}_{2}}^{0}⟩+\mid {f}_{{i}_{2}}^{0}⟩\mid {f}_{{i}_{1}}^{0}⟩$ for ${i}_{1}<{i}_{2}\in {ℤ}_{N}$. Finally, the product state belongs to the space spanned by ${\mid x⟩\mid x⟩}_{x\in {ℤ}_{N}}$ and ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x.
• If $b=1$, the product contains vectors $\mid {f}_{{i}_{1}}^{0}⟩\mid {f}_{{i}_{2}}^{1}⟩$ where the two coordinates are not equal. We never have two symmetric vectors i.e. which are the same after permutating the two coordinates. Moreover, each vector $\mid {f}_{{i}_{1}}^{0}⟩\mid {f}_{{i}_{2}}^{1}⟩$ is the expression of a sum/difference (according to the respective order of ${f}_{{i}_{1}}^{0}$ and ${f}_{{i}_{2}}^{1}$) of two vectors $\mid x⟩\mid y⟩+\mid x⟩\mid y⟩$ and $\mid x⟩\mid y⟩-\mid x⟩\mid y⟩$. So the product state belongs half to ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x and half to ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x.

Suppose that we have a procedure to create many states $\mid {\psi }_{0}⟩$ and $\mid {\varphi }_{0}⟩$. We measure a state in the space ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x with probability $\frac{b}{2}$. So repeating the procedure a constant number of times allow to determine $b$ with high probability.

The only gap in the previous algorithm is whether we can create the states $\mid {\psi }_{0}⟩$ and $\mid {\varphi }_{0}⟩$. As in the previous post, this is possible if the gates ${V}_{f,.}$ are available. Otherwise, we can create a superposition of states over ${ℤ}_{N\text{'}}$ and use the gate ${U}_{f}$ as well as a Quantum Fourier Transform to randomize the first coordinate. We get two random numbers ${j}_{1},{j}_{2}\in {ℤ}_{N\text{'}}$ and the states

$\mid {\psi }_{{j}_{1}}⟩=\frac{1}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi {j}_{1}i}{N\prime }}\mid f\left(2i,0\right)⟩$

and$\mid {\varphi }_{{j}_{2}}⟩=\frac{{e}^{\frac{2i\pi {j}_{2}d\prime }{N\prime }}}{\sqrt{N\prime }}\sum _{i=0}^{N\prime -1}{e}^{\frac{2i\pi {j}_{2}i}{N\prime }}\mid f\left(2i-b,0\right)⟩$

Next, we can apply the same measurement as above. After a bit of calculation,we get the probabilities:

Space case $b=0$ case $b=1$
${\mid x⟩\mid x⟩}_{x\in {ℤ}_{N}}$ $\frac{1}{N\text{'}}$ 0
${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x $\frac{2}{{N\prime }^{2}}\sum _{{i}_{2}=0}^{N\prime -1}\sum _{{i}_{1}=0}^{{i}_{2}-1}{\mathrm{cos}}^{2}\frac{\pi }{N\prime }\left({j}_{2}-{j}_{1}\right)\left({i}_{2}-{i}_{1}\right)$ $\frac{1}{2}$
${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x $\frac{2}{{N\prime }^{2}}\sum _{{i}_{2}=0}^{N\prime -1}\sum _{{i}_{1}=0}^{{i}_{2}-1}{\mathrm{sin}}^{2}\frac{\pi }{N\prime }\left({j}_{2}-{j}_{1}\right)\left({i}_{2}-{i}_{1}\right)$ $\frac{1}{2}$

If we repeat the procedure several times, we need to take the means over the choice of ${j}_{1},{j}_{2}\in {ℤ}_{N\text{'}}$. Using some trigonometric identities, it is possible to write the sums of the first column $\frac{1}{2}+S+o\left(\frac{1}{N\text{'}}\right)$ where $S$ is a sum of cosinus. Unfortunately, evaluating $S$ with a computer suggests that $S=\Theta \left(\frac{1}{N\text{'}}\right)$ . Hence, we can not distinguish the two cases with only a polynomial (in $\mathrm{log}N$) number of samplings.

It is still open whether we can find a variation to make such an algorithm efficient...