Thoughts on the Dihedral Hidden Subgroup Problem (part 3)
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 rather than finding its parity. For convenience, we assume to be even and define . We consider for and the sets of successive values
We suppose that we can efficiently create uniform superposition over these states. As in part 2, we have with and we measure the tensor product of the uniform superpositions over and in the basis , , . We define the number of common elements.
The figure above shows that in the case , we have . In general, the expression is
Using an analysis similar to the one part 2, we get the probability to measure an element in :
Repeating the measurements, we can approximate , and consequently and finally . We can also play with the value , to improve the approximation. Unfortunately, using a number of repetitions polynomial in , it does not seem possible to bound the error better than . 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 , erase or uncompute the first register to get a superposition over elements . 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 .