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 which is a bit cheating since we do not have this feature for the classical problem. In this post, we will consider the case , and try to determine the parity of . If is a power of two, this is enough to find recursively. As in the previous post, the main idea is to consider the superpositions
Using the equality we can rewrite the latter state
If , the latter state is the same superposition as the former state, over values of . Otherwise, and the latter state is the superposition over the other values of . We let and measure the product state in the basis , , . It turns out that this allows to distinguish the two cases:
- If , the product contains vectors with the same coordinates for . For the other vectors, we have a symmetry between the two coordinates. Hence we can group them by pairs for . Finally, the product state belongs to the space spanned by and .
- If , the product contains vectors 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 is the expression of a sum/difference (according to the respective order of and ) of two vectors and . So the product state belongs half to and half to .
Suppose that we have a procedure to create many states and . We measure a state in the space with probability . So repeating the procedure a constant number of times allow to determine with high probability.
The only gap in the previous algorithm is whether we can create the states and . As in the previous post, this is possible if the gates are available. Otherwise, we can create a superposition of states over and use the gate as well as a Quantum Fourier Transform to randomize the first coordinate. We get two random numbers and the states
Next, we can apply the same measurement as above. After a bit of calculation,we get the probabilities:
If we repeat the procedure several times, we need to take the means over the choice of . Using some trigonometric identities, it is possible to write the sums of the first column where is a sum of cosinus. Unfortunately, evaluating with a computer suggests that . Hence, we can not distinguish the two cases with only a polynomial (in ) number of samplings.
It is still open whether we can find a variation to make such an algorithm efficient...