Thoughts on the Dihedral Hidden Subgroup Problem (part 3)

05 Jul 2010

Back to the DHSP again (see part 1 and part 2 in previous blog posts)... This time, I've tried to approximate the value of $d$ rather than finding its parity. For convenience, we assume $N$ to be even and define $N\text{'}=2M=\frac{N}{2}$. We consider for $a\in {\mathbb{Z}}_N$ and $b\in {\mathbb{Z}}_2$ the sets of $N\text{'}$ successive values$$F_a^b=\{f(a+i,b),i\in {\mathbb{Z}}_{N\prime }\}$$

We suppose that we can efficiently create uniform superposition over these states. As in part 2, we have $F_a^1=F_{a-d}^0=F_s^0$ with $-N<s<N$ and we measure the tensor product of the uniform superpositions over $F_a^1=F_s^0$ and $F_0^0$ in the basis ${\mid x⟩\mid x⟩}_{x\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩+\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$, ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$. We define $l=\mid F_0^0\cap F_a^1\mid$ the number of common elements.

The figure above shows that in the case $0\le s\le N\text{'}$, we have $l=N\text{'}-s$. In general, the expression is

$$l=\mid N\text{'}-\mid s\mid \mid =\mid N\text{'}-\mid d-a\mid \mid$$

Using an analysis similar to the one part 2, we get the probability to measure an element in ${\frac{1}{\sqrt{2}}\left(\mid x⟩\mid y⟩-\mid x⟩\mid y⟩\right)}_{x<y\in {\mathbb{Z}}_N}$:

$$P=\frac{1}{2}[1-{\left(\frac{l}{N\prime }\right)}^2]$$

Repeating the measurements, we can approximate $P$, and consequently $l,s$ and finally $d$. We can also play with the value $a$, to improve the approximation. Unfortunately, using a number of repetitions polynomial in $\log N$, it does not seem possible to bound the error better than $O\left(N\right)$. It seems however that it is still a better result than the one that I obtained with the standard Coset Sampling method. Hence it is another hint of the fact that using a superposition over several oracles values would yield improvement.

I'm still wondering how to create efficiently an uniform superposition over several oracle values. One thing I've read in many papers, is given a superposition over elements $\mid x⟩\mid f(x)⟩$, erase or uncompute the first register to get a superposition over elements $\mid f(x)⟩$. However, I'm not sure what are the requirements to apply such an operation. If it could work for the algorithm of part 2, then this would solve the case $N=2^n$.