Skip to main content
eScholarship
Open Access Publications from the University of California

UC Davis

UC Davis Electronic Theses and Dissertations bannerUC Davis

Improved Quantum Algorithms for Solving Abelian Hidden Subgroup Problems for Subgroups of Arbitrary Index

Abstract

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.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View