In this report we have studied the Hidden Subgroup Problem, whose solution for various groups is expected to provide new efficient quantum algorithms. In a first part, we have reviewed the classical efficient Quantum algorithms of Simon and Shor and identified their main features. We have introduced the Hidden Subgroup Problem and showed how the previous algorithms can be defined in that framework.
In a second part, we have been interested in the standard method based on coset sampling. We have presented the well-known solution to the abelian case which includes the algorithms seen in the first part. We have described precisely a natural extension to the non-abelian case, by defining a Quantum Fourier Transform over finite groups as well as Weak/Strong Fourier Sampling. We have shown that Weak Fourier Sampling is able to find normal hidden subgroups and thus provides a solution to HSP over dedekindian groups. We have mentioned some extensions when the group is, in some sense, not too far from a dedekindian group. However, the Weak Fourier Sampling can not distinguish conjugate groups and thus it is not applyable to an arbitrary group.
In a third part, we have turned our attention to the dihedral and symmetric hidden subgroup problems. We have given a complete presentation of the structure of the dihedral group and recalled the reduction of the dihedral HSP to the search of a hidden slope . We have presented Kupenberg's subexponential algorithm to find this slope and mentioned the results about the optimal measurement for dihedral coset sampling. We have studied Regev's algorithm for the uniqueSVP and noticed that it can be modified to work for some generalized dihedral groups and "recursive" coset sampling. We have also shown that the approximation factor obtained for the uniqueSVP is strongly related to the degree of the polynomial bounding the complexity of the coset sampling algorithm used. Finally, we have presented the classical reduction from graph isomorphism to symmetric hidden subgroup problems but have also recalled the negative results on the symmetric group: we need at least a linear number of entangled coset states at once but using an algorithm similar to Kupenberg's one does not help.
In the fourth and last part, we have considered the general HSP. We have suggested a general approach to the hidden subgroup problem based on the mathematical description of finite groups. We have shown that we could reduce the general case to a solution over simple groups and construction of some efficient oracles. These two points are precisely where we are stuck on for dihedral and symmetric groups. However, several efficient algorithms have been discovered for other non-abelian groups. We have given an overview of these solutions which are essentially with respect to "almost abelian" groups in some sense or the other. We have described some efficient algorithms with concrete application, including applications in cryptography, which are related to the hidden subgroup problem. Finally, we have mentioned variants and extensions to the HSP which have been solved for some particular cases and are expected to yield new efficient quantum algorithms.
As a conclusion, we have provided a good overview of the hidden subgroup problem going from its origin to the state of the art as of 2010. We have also brought some contributions to the topic. While the general problem still remains difficult, we hope that our work will help people to have a better understanding of the subject and guide them toward some research directions.
