10
$\begingroup$

I noticed that approaches for finding quantum algorithms the hidden subgroup problem for both Abelian groups ($(\Bbb Z_n\times \Bbb Z_n, +)$, $(\Bbb R, +)$, etc.) and non-Abelian finite groups like the dihedral group and symmetric group often use representation theory.

  1. Why is this the case? How's it helpful?

  2. What are some resources for where I can learn sufficient representation theory to at least get started with understanding such algorithms? (I'm not in a position to read a heavy grad-level math textbook on representation theory.)

$\endgroup$
1
  • 3
    $\begingroup$ To 1: Basically because these problems are about group theory but Quantum mechanics (in the standard formulation) is built around vector spaces. How can you connect these two algebraic objects: via representations which map group elements to matrices (or linear maps if you want). To be more precise: the construction often involves labelling the basis states by group elements as $|g\rangle$. Then you need a representation of the group to actually act with another group element $g'$ on this state. $\endgroup$
    – Marsl
    Nov 23, 2019 at 21:08

1 Answer 1

8
$\begingroup$

Two classical texts for the representation theory of finite groups are the books of Hamermesh and Serre. These books however lack chapters on Fourier analysis needed for the quantum computation applications.

For a more modern text for finite group representations which includes a chapter on Fourier analysis, please see the lecture notes by: Steinberg.

However, for a fast introduction, quite sufficient for the quantum computation applications, there are very concise texts: in Enrique Alvarez lecture notes (Chapter 9, in first reading one can skip the representation theory of $S_N$ and study the 17 pages 79-95 only), and in chapter 2 of the lecture notes by Willwacher.

Since these concise resources also lack the subject of Fourier analysis, you can read the 5 pages of chapter 3 of Shengyu Zhang quantum computing course giving an introduction to the group theory needed for the hidden subgroup problem.

In the hidden subgroup problem, we are given a function $f: G \rightarrow S$ ($S$ is a finite set) which is invariant on the cosets of some subgroup $H$ of $G$; i.e., $f(g) = f(gh), \,\, h\in H$; and we want to identify the subgroup $H$.

Representation theory appears because every function on a finite group $G$ can be written as a linear combination of the matrix elements of its irreducible representations; and we need to identify the representations appearing in the function $f$. We do so by preparing a state: $$\sum_G |g, f(g)\rangle$$ (This state is efficiently preparable, when there is an efficient oracle for the computation of $f$). If we measure the second register, we are left with a uniformly weighted combination of group elements belonging to the coset corresponding to the measured values of $f$: $$\sum_H |ch\rangle$$ ($c$ is any element in this coset).

Let $\rho$ be an irreducible representation of $G$, then $\rho$ is a matrix function of $G$ of dimension $d_{\rho} \times d_{\rho}$; the quantum Fourier transform, transforms a group vector $|g\rangle$ to:

$$\sum_{\rho \in \hat{G}} \sum_{i=1}^{d_{\rho}}\sum_{j=1}^{d_{\rho}}\sqrt{\frac{d_{\rho}}{|G|}} \rho(g)_{ij} |i, j, \rho\rangle$$

Where $\hat{G}$ is the set of irreducible representations, (which is in a one to one correspondence with the conjugacy classes of $G$).

In order to appreciate the role of the Fourier transform, please consider the case of $\mathbb{Z}_N = \{ z_0, …, z_{N-1}\}$. Since $\mathbb{Z}_N$ is Abelian all its irreducible representations are one dimensional given by:

$$\rho_m (z_n) = e^{\frac{2 \pi i mn}{N}}$$

This is the kernel of the usual Fourier transform. $m$ is the representation index and $n$ is the group element index. We know that if we perform a Fourier transform of the function $\rho_m$, we get a peaked function at $m$ by which we identifiy the representation $m$.

In the general case when we measure the $\rho$ register in $|i, j, \rho\rangle$, we get with a high probability a representation appearing in $f$, thus by repeating the experiment, we get with a high probability all representations having $H$ in their kernel and we can identify $H$ as their mutual kernel.

Please see the following https://arxiv.org/abs/0812.0380v1 work by Childs and Dam reviewing cases where the above standard method and other improved methods lead to efficient hidden subgroup identification in the non-Abelian cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.