Hidden Subgroup Problem : About Some Classical and Quantum Algorithms

Abstract

Most quantum algorithms that are efficient as opposed to their equivalent classical algorithms are solving variants of the Hidden Subgroup Problem (HSP), therefore HSP is a central problem in the field of quantum computing. In this thesis, we offer some interesting results about the subgroup and coset structure of certain groups, including the dihedral group. We describe classical algorithms to solve the HSP over various abelian groups and the dihedral group. We also discuss some existing quantum algorithms to solve the HSP and give our own novel algorithms and ideas to approach the HSP for the dihedral groups.