Thoughts on the Dihedral Hidden Subgroup Problem (part 2)

20 Jun 2010

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

and

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

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(2i-b,0)⟩$$

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⟩\mid {\varphi }_0⟩$ in the basis ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$, ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$, ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{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⟩\mid f_i^0⟩$ 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⟩\mid f_{i_2}^0⟩+\mid f_{i_2}^0⟩\mid f_{i_1}^0⟩$ for $i_1<i_2\in {\mathbb{Z}}_N$. Finally, the product state belongs to the space spanned by ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$ and ${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$.
• 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<y\in {\mathbb{Z}}_N}$ and half to ${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{x<y\in {\mathbb{Z}}_N}$.

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

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(2i-b,0)⟩$$

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 {\mathbb{Z}}_N}$	$\frac{1}{N\text{'}}$	0
${\mid x⟩\mid y⟩+\mid x⟩\mid y⟩}_{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}{\cos }^2\frac{\pi }{N\prime }(j_2-j_1)(i_2-i_1)$	$\frac{1}{2}$
${\mid x⟩\mid y⟩-\mid x⟩\mid y⟩}_{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}{\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 $\log N$) number of samplings.

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