Emilia Dunfelt: Quantum Computing - From Shor's Algorithm to The Hidden Subgroup Problem

Abstract

The following paper aims to present the basic theory of quantum computing, Shor’s algorithm, the graph isomorphism problem, and their connection to the hidden subgroup problem. A mathematical approach is taken to these concepts, in contrast to a physical or computer scientific focus. Each topic is introduced with an emphasis on Hilbert spaces, analytic number theory, representation theory, and group theory. First, Shor’s factoring algorithm is presented and summarized in detail, giving a complete overview of the factoring process. Then, after introducing basic notions of representation theory of finite groups, the standard method of quantum algorithms is presented in the context of the hidden subgroup framework. Finally, the graph isomorphism problem is discussed, and a brief overview of the current status of this problem is given.