▍The Hidden Subgroup Problem is an important problem from Computer
Science / Mathematics and actually covers several well known problems as a
special case. The formal statement of the problem is:
Definition [Hidden Subgroup Problem (HSP)] Let $\mathbb{G}$ be a group and $\mathbb{H}$ an unknown subgroup of
$\mathbb{G}$, i.e., $\mathbb{H} \leq \mathbb{G}$. Let $S$ be any set and $f$
be a function that maps the group elements of $\mathbb{G}$ to $S$, i.e., $f:
\mathbb{G} \rightarrow S$. The function $S$ has the special property that it
can distinguish cosets of $\mathbb{H}$: $$ f(e_1) = f(e_2) \Leftrightarrow
e_1\mathbb{H} = e_2\mathbb{H} $$ The Problem is, given $\mathbb{G}$ and access
to the function $f$, to determine a generating set for the subgroup
$\mathbb{H}$ ∎
The notation $e\mathbb{H}$ denotes the coset $$e\mathbb{H} =
\left\{eh | h \in \mathbb{H}\right\}$$. Problems that can be described as an
instance of the HSP are for example:
- Integer Factorization Problem
- Discrete Logarithm Problem
- Shortest Vector Problem
- Deutsch Problem
- Simon's Problem
and probably many more. The definition of the HSP above seems very abstract,
but the subgroup $\mathbb{H}$ actually covers the usual integers of
interest, e.g. divisors of $\varphi(N)$ in case of the Factorization Problem
or multiples of the exponents in question in case of the Discrete Logarithm
Problem. Shors Algorithm is a special instance of an HSP-Solver that finds the
period of the function $g^x \pmod{N}$, i.e., it finds divisors of $\varphi(N)$. However, his algorithm only works in the ablian case. How to solve the HSP efficiently for non abelian groups is not known, also for quantum computers. The Shortest Vector Problem is a hard problem for quantum computers. So it is no surprise, that the reduction from SVP to HSP brings into play a non abelian group, the dihidral group.
