Hidden subgroup problem

The hidden subgroup problem (HSP) is a topic of research in mathematics and theoretical computer science. It is a generalization of problems including factoring, discrete logarithm, graph isomorphism, and the shortest vector problem. This makes it especially important in the theory of quantum computing because Shor's algorithms for factoring and finding discrete logarithms in quantum computing are instances of the hidden subgroup problem for finite abelian groups, while the other problems correspond to finite groups that are not abelian.

Problem statement

Given a group

G

{\displaystyle G}

, a subgroup

H

≤

G

{\displaystyle H\leq G}

, and a set

X

{\displaystyle X}

, we say a function

f

:

G

→

X

{\displaystyle f:G\to X}

hides the subgroup

H

{\displaystyle H}

if for all

g

1

,

g

2

∈

G

,

f

(

g

1

)

=

f

(

g

2

)

{\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}

if and only if

g

1

H

=

g

2

H

{\displaystyle g_{1}H=g_{2}H}

. Equivalently,

f

{\displaystyle f}

is constant on each coset of H, while it is different between the different cosets of H.

Hidden subgroup problem: Let

G

{\displaystyle G}

be a group,

X

{\displaystyle X}

a finite set, and

f

:

G

→

X

{\displaystyle f:G\to X}

a function that hides a subgroup

H

≤

G

{\displaystyle H\leq G}

. The function

f

{\displaystyle f}

is given via an oracle, which uses

O

(

log

⁡

|

G

|

+

log

⁡

|

X

|

)

{\displaystyle O(\log |G|+\log |X|)}

bits. Using information gained from evaluations of

f

{\displaystyle f}

via its oracle, determine a generating set for

H

{\displaystyle H}

.

A special case is when

X

{\displaystyle X}

is a group and

f

{\displaystyle f}

is a group homomorphism in which case

H

{\displaystyle H}

corresponds to the kernel of

f

{\displaystyle f}

.

Motivation

The hidden subgroup problem is especially important in the theory of quantum computing for the following reasons.

Shor's algorithm for factoring and for finding discrete logarithms (as well as several of its extensions) relies on the ability of quantum computers to solve the HSP for finite abelian groups.