Hidden subgroup problem

This article describes the problem of converting from one subgroup description (namely: coset-separating function) to another (namely: generating set)

Description

Setup

A group $G$ described by means of an encoding. A subgroup $H$ of $G$.

Conversion to be achieved

We are given a coset-separating function for $H$ in $G$, say $f:G\to X$.

We need to output a generating set for $H$ (in terms of encodings of the various elements).

Complexity notions

Log-size assumption

We study the hidden subgroup proble under the log-size assumption, that is, we assume that:

• The encoding of $G$ has logarithmic size with the multiplication and inversion implemented in polylogarithmic time
• The set $X$ is also encoded using words whose length is at most logarithmic in the order of $G$
• The time taken by this coset-separating function (which behaves like a black box) is also polylogarithmic in the size of the group

Under these assumptions, we want an algorithm that is polylogarithmic in the size of the group.