Quantum Algorithms & the Hidden Subgroup Problem

In the last century, we have seen incredible growth in the field of quantum computing. Quantum computing offers us the opportunity to find efficient solutions to certain computational problems which are intractable on classical computers. One class of problems that seems to benefit from quantum computing is the Hidden Subgroup Problem (HSP). In the following proposal, we will examine basics of quantum computing as well as the current research surrounding the HSP. We will also discuss the importance of the HSP and its relation to other popular problems such as Integer Factoring, Discrete Logarithm, Shortest Vector, and Subset Sum problems.

The proposed research aims to develop a quantum algorithmic polynomial-time reduction to special cases of the HSP where the parameterizing group is the Dihedral group. This problem is known as the Dihedral HSP (DHSP). The usual approach to the HSP relies on harmonic analysis in the domain of the problem and the best-known algorithm using this approach is sub-exponential, but still super-polynomial. The algorithm we have designed focuses on the structure encoded in the codomain which uses this structure to direct a “walk” down the subgroup lattice terminating at the hidden subgroup.