Thoughts on the Dihedral Hidden Subgroup Problem
This morning, I've been thinking again about a way to solve the Hidden Subgroup Problem for the dihedral group (where is the inversion of ). It is well-known that there exists a reduction to the case where the hidden subgroup is for some . In that case, if we fix , the elements for form a complete set of coset representatives, so is one-to-one over . Thus, is a permutation of , a property that will be used below to construct a unitary transform.
First let's recall the classical inductive method to determine . If is a divisor of , let and write the euclidean division . If we are able to determine in polynomial time, then we can define the oracle for and and obtain a dihedral HSP with hidden subgroup . Since the prime factorization has only factors, we can repeat this inductive step to get an efficient algorithm. Of course, this is likely to be useful only when the factors are small for otherwise it may be as much difficult to determine as to determine the whole . One interesting case is and : at each step, remains a power of 2 and we determine the parity of .
For , we consider the -dimensional subspace spanned by the vectors for . Since these subspaces are orthogonal, we can construct a unitary transform by applying a Quantum Fourier Transform on each subspace separately. Finally, we apply the permutation mentionned at the beginning for . We get a unitary transform below where is the euclidean division of by :
Now, let's consider the superposition (again, we see that it is well-defined by considering the permutation mentionned at the beginning for ):
The state can be rewritten, using the fact that is constant on :
Applying to this state gives and so the value of by a measurement in the standard basis.
Two questions remain: can we implement and create the state efficiently? If and , there are many simplifications because we are working with qubits. In that case, it is easy to see that the answer to the previous questions is affirmative if we have gates implementing the permutation mentioned at the beginning. However, it is not clear how to build from the gate generally given in the classical presentation of the problem...
update: OK, there is also the trivial solution where the algorithm above is just computing . However, I'm still wondering if there is a way to modify the previous method to work with .