El problema del subgrup amagat per a grups no abelians

Abstract

El problema del subgrup amagat és un formalisme teòric que engloba alguns problemes de gran rellevància, com el de factorització, el del logaritme discret i el d’isomorfisme de grafs. Tot i que per a grups abelians es pot resoldre aquest problema amb l’ús de computació quàntica en temps polinòmic, encara no s’ha trobat una resolució general per a grups no abelians. Aquest treball explora alguns resultats relacionats amb la possible resolució del problema per a grups finits no abelians, aixı́ com també les seves limitacions. Començarem introduint els fonaments de la mecànica quàntica, necessaris per a descriure el model de computació quàntica. A continuació, presentarem els conceptes bàsics de la teoria de representació de grups finits que ens ajuden a construir la transformada de Fourier, una peça clau en la majoria d’algoritmes quàntics. Posteriorment, exposarem un resultat general sobre la possibilitat de resoldre el problema per a grups finits qualssevol en un nombre de peticions polinòmic, malgrat poder requerir temps exponencial. A més, analitzarem quins grups no abelians permeten la construcció d’un algoritme més eficient, així com alguns teoremes que demostren la impossibilitat d’implementar un algoritme eficaç en els casos del grup diedral i del grup simètric. Finalment, abordarem algunes possibles limitacions de la resolució del problema i reflexionarem sobre la seva possible extensió als grups no finits.

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 work 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.