UC Davis

This dissertation continues the progress on using quantum algorithms to efficiently solve the hidden subgroup problem (HSP) for various groups. We first give a necessary foundation on defining hidden subgroup problems and their efficient solutions. We then focus on the case when $G=\Z^k$, a natural continuation of the historical progress on HSP. The current algorithm for HSP on $\Z^k$ as shown by Kitaev is only successful when the hidden subgroup is of finite index. Kuperberg has recently proposed an algorithm that solves HSP on $\Z^k$ for subgroups of arbitrary index. His algorithm follows the quantum component of Kitaev's algorithm closely, but diverges with a novel use of the LLL algorithm in its classical post-processing. When covering the background of quantum algorithms to attack HSP, we emphasize the similarities in their quantum structure. We realize Kuperberg's results by providing explicit bounds on his defined parameters, and show success with computer simulations on his algorithm. We then propose modifications that significantly improve performance and resource usage, and provide computer simulations to demonstrate our results. We end by discussing applications in modern-day cryptography and how our research could assist with further development in the field of quantum algorithms.