STNB2025 (38th edition)
The Hidden Subgroup Problem for Non-abelian Groups
Presenters
Yaiza Aguilar Carós
Abstract
The hidden subgroup problem is a theoretical formalism that encompasses several highly relevant problems, such as factorization, discrete logarithm, and graph isomorphism. While this problem can be solved for abelian groups using quantum computation in polynomial time, a general resolution for non-abelian groups has not yet been found. This talk explores some results related to the potential resolution of the problem for finite non-abelian groups, as well as its limitations. We will begin by introducing the foundations of quantum mechanics, which are necessary to describe the quantum computation model. Next, we will present the basic concepts of finite group representation theory that help us construct the quantum Fourier transform, a key component in most quantum algorithms. Subsequently, we will discuss a general result on the possibility of solving the problem for arbitrary finite groups with a polynomial number of queries, although possibly requiring exponential time. Furthermore, we will analyze which non-abelian groups allow the construction of a more efficient algorithm, as well as some theorems that demonstrate the impossibility of implementing an efficient algorithm in the cases of the dihedral group and the symmetric group. Finally, we will address some potential limitations of solving the problem and reflect on its possible extension to infinite groups.
Files
No files available for download
