Rejtett részcsoport probléma

A Wikipédiából, a szabad enciklopédiából

A rejtett részcsoport probléma a következő: ha adva van egy csoport és egy függvény, ami a csoport egy részcsoportjának mellékosztályain különböző konstans értékeket vesz fel, meghatározható-e a részcsoport az elemszámához képest polinomiális időben? Számos fontos matematikai probléma megfogalmazható a rejtett részcsoport probléma speciális eseteként, például a prímfaktorizáció vagy a gráfizomorfizmus.

A rejtett részcsoport probléma fontos kutatási terület a kvantuminformatikában, mert egyes fajtáinál kvantumalgoritmussal a leghatékonyabb ismert algoritmushoz képest exponenciális gyorsulást lehet elérni. Legismertebb esete ennek a Shor-algoritmus.