Hidden subgroup problem

Motivation

On Neilson&Chuang[1] p.38，it says that Kitaev has generalized multiple problems that could be efficiently solved by Quantum Fourier Transform(i.e. Deutsche's problem, Shor's Algorithms for factoring and discrete logarithm) to the hidden subgroup problem. I wonder what this problem is about, and how this problem is mapped to other important problem?

Problem description

Given a group $G$ and a function $f: G \rightarrow X$ , find a subgroup $H\subseteq G$ such that $\forall \ g_1, g_2 \in G$ , $f(g_1) = f(g_2) \Leftrightarrow g_1H = g_2H$ . That is, the function $f$ distinguishes cosets of $H$ .

Coset [2]

Coset is a mathematical concept in group theory. For an element $g$ in group $G$ and its subgroup $H$ , the coset of $H$ is defined as

gH = \{\ gh\ |\ h \in H\ \}

All elements in $G$ shall be in one and only one coset of $H$ . In other words, the cosets of $H$ are mutually exclusive.

Example

Let $G = \{ I, a, b, ab, a^2, a^2b \}$ , $H = \{ I, b\}$ , the rules of the elements follows this table:

∗	$I$	$a$	$a^2$	$b$	$ab$	$a^2b$
$I$	$I$	$a$	$a^2$	$b$	$ab$	$a^2b$
$a$	$a$	$a^2$	$I$	$ab$	$a^2b$	$b$
$a^2$	$a^2$	$I$	$a$	$a^2b$	$b$	$ab$
$b$	$b$	$a^2b$	$ab$	$I$	$a^2$	$a$
$ab$	$ab$	$b$	$a^2b$	$a$	$I$	$a^2$
$a^2b$	$a^2b$	$ab$	$b$	$a^2$	$a$	$I$

We can get the cosets of $H$ as:

$IH = bH = H = \{ I, b \}$

$aH = abH = \{ a, ab \}$

$a^2H = a^2bH = \{ a^2, a^2b \}$

And these three consist of cosets of $H$ .

Take $H = \{ I, a, a^2\}$ for another example:

$IH = aH = a^2H = H = \{ I, a, a^2 \}$

$bH = abH = a^2bH = \{ b, ab, a^2b \}$

so this $H$ also can be a valid subset to form cosets.

** Note: $H = \{ a, a^2\}$ is not a coset because

$IH = a^2H = H = \{ a, a^2 \}$ ,but

$aH = \{ I, a^2 \}$

As you can see, $a^2$ appears in two cosets. Cosets has to be mutually exclusive.

Recall: The hidden subgroup problem aims to find if there is a valid $H$ such that $f$ can distinguish the cosets of $H$ . Specifically, the elements in the same coset would have the same output of $f(g_i)$ , and different coset has different output of $f$ .

How is hidden subgroup problem mapped to other problems? [3]

As long as we specify $G$ and $f$ , it is very obvious that the $H$ exists and is definitely something we want to find. As for $X$ , it is a specification for output of $f$ .

Problem	G	H	X	f
Simon	$\mathbb{Z}_2^n$	$\{0, s\}$	$\mathbb{Z}_2^n$	$s$ is an n-bit binary string such that $x = x'\oplus s$ and $f(x) = f(x')$
Order Finding	$\mathbb{Z}_N$	$r\mathbb{Z}_N$	$\mathbb{Z}_N$	r is the valid integer of x such that $f(x) = a^x\ mod(N_0)$
Discrete Logarithm	$\mathbb{Z}_{p-1} \times \mathbb{Z}_{p-1}$	$(y-1)\mathbb{Z}_{p-1}$	$\mathbb{Z}_{p-1} /\{0\}$	$f(a,b)=g^a x^b\ mod(p)$

Reference

[1] Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press.

[2] https://en.wikipedia.org/wiki/Coset

[3] Wang, F. (2010). The hidden subgroup problem. arXiv preprint arXiv:1008.0010.