# 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\mapsto 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}\u27e9=\frac{1}{\sqrt{N\prime}}\sum _{i=0}^{N\prime -1}\mid f(2i,0)\u27e9$$

and

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

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

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

If $b=0$, the latter state is the same superposition as the former state, over $N\text{'}$ values of ${\mathbb{Z}}_{N}$. Otherwise, $b=1$ and the latter state is the superposition over the $N\text{'}$ other values of ${\mathbb{Z}}_{N}$. We let ${f}_{i}^{b}=f(2i-b,0)$ and measure the product state $\mid {\psi}_{0}\u27e9\mid {\varphi}_{0}\u27e9$ in the basis ${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$, ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$, ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ . 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}\u27e9\mid {f}_{i}^{0}\u27e9$ for $i\in {\mathbb{Z}}_{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}\u27e9\mid {f}_{{i}_{2}}^{0}\u27e9+\mid {f}_{{i}_{2}}^{0}\u27e9\mid {f}_{{i}_{1}}^{0}\u27e9$ for ${i}_{1}<{i}_{2}\in {\mathbb{Z}}_{N}$. Finally, the product state belongs to the space spanned by ${\mid x\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$ and ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$.
- If $b=1$, the product contains vectors $\mid {f}_{{i}_{1}}^{0}\u27e9\mid {f}_{{i}_{2}}^{1}\u27e9$ 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}\u27e9\mid {f}_{{i}_{2}}^{1}\u27e9$ 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\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9$ and $\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9$. So the product state belongs half to ${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ and half to ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$.

Suppose that we have a procedure to create many states $\mid {\psi}_{0}\u27e9$ and $\mid {\varphi}_{0}\u27e9$. We measure a state in the space ${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ 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}\u27e9$ and $\mid {\varphi}_{0}\u27e9$. As in the previous post, this is possible if the gates ${V}_{f,.}$ are available. Otherwise, we can create a superposition of states over ${\mathbb{Z}}_{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 {\mathbb{Z}}_{N\text{'}}$ and the states

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

and$$\mid {\varphi}_{{j}_{2}}\u27e9=\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(2i-b,0)\u27e9$$

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\u27e9\mid x\u27e9}_{x\in {\mathbb{Z}}_{N}}$ | $\frac{1}{N\text{'}}$ | 0 |

${\mid x\u27e9\mid y\u27e9+\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ | $\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}({j}_{2}-{j}_{1})({i}_{2}-{i}_{1})$ | $\frac{1}{2}$ |

${\mid x\u27e9\mid y\u27e9-\mid x\u27e9\mid y\u27e9}_{x<y\in {\mathbb{Z}}_{N}}$ | $\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}({j}_{2}-{j}_{1})({i}_{2}-{i}_{1})$ | $\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 {\mathbb{Z}}_{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...