1
$\begingroup$

This is a continuation of my question asked here.

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations. In Definition 2, the authors start with the following function.

$$ f : G \to \mathbb{C} $$

Then the Fourier transform of $f$ at the irrep $\rho$ is defined as the $d_\rho \times d_\rho$ matrix:

$$ \hat{f}(\rho) = \sqrt{\frac{d_\rho}{|G|}} \sum_{g \in G} f (g) \rho(g) $$

In the quantum computational settings, the authors identify the superposition $\sum_{g \in G} f_g |g\rangle$ ($|a\rangle$ is a quantum state which is the $a$-th computational basis vector), with the function $f:G\to\mathbb{C}$ defined by $f(g) = f_g$.

In this notation, $\sum_{g \in G} f(g)|g\rangle$ is mapped under the Fourier transform to $\sum_{\rho \in \hat{G}, 1\le i,j \le d_\rho} \hat{f}(\rho)_{i,j} |\rho, i, j\rangle$.

$(\rho, i, j)$ is the label of the $(\rho, i, j)$-th computational basis vector $|\rho, i, j\rangle$. $\hat{f}(\rho)_{i,j}$ is a complex number and the $(i,j)$-th element of the matrix $\hat{f}(\rho)$. $\hat{G}$ is the collection of all irreps of $G$.

Then the authors say as follows.

When the first portion of this triple is measured, we observe $\rho \in \hat{G}$ with probability

$$ \sum_{1\le i,j\le d_\rho} |\hat{f}(\rho)_{i,j}|^2 = ||\hat{f}(\rho)||^2\\ = tr ((\hat{f}(\rho))^* \hat{f}(\rho)) $$

Here, ($\rho, i, j$) is the triple the authors are referring to. Measuring $\rho$ means measuring the qubits which encode the label $\rho$.

I understand up to this part. Then in Section 3, right after Equation 2, the authors go on saying:

$$ ||\hat{f}(\rho)||^2 = ||\sqrt{\frac{d_\rho}{|G|}} \sum_{h\in H} \rho(h)||^2 $$

I know that $\rho$ may not be an irrep for $H$. But, the matrix elements in $\hat{f}(\rho)$ comes from the direct sum of the matrices $\rho(h)$. I assume the previous equation works because of the Equation (2) in the paper.

I do not understand from here. The equation written by the authors is as follows:

$$ ||\hat{f}(\rho)||^2 = ||\sqrt{\frac{d_\rho}{|G|}} \sum_{h\in H} \rho(h)||^2\\ = \frac{d_\rho}{|G|} \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H \\= \frac{|H|}{|G|} d_\rho \langle \chi_\rho, \chi_{1_H} \rangle_H $$

Here, $\chi_{1_H} $ is the character of the trivial representation of the subgroup $H$.

My question:

Why is $||\sum_{h\in H} \rho (h)||^2 = \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H$? According to the definition of the Frobenius Norm, it should be like $||\sum_{h\in H} \rho (h)||^2 = Tr \left(\left(\sum_{h\in H} \rho (h)\right)\left(\sum_{h\in H} \rho (h)\right)^\dagger\right)$. I do not understand the following relationship.

$$ Tr \left(\left(\sum_{h\in H} \rho (h)\right)\left(\sum_{h\in H} \rho (h)\right)^\dagger\right) = \frac{1}{|H|} |H|^2 \langle \chi_\rho, \chi_{1_H} \rangle_H $$

$\endgroup$
1
$\begingroup$

It's important that on the first page the paper states that, without loss of generality, all of their irreducible representations are unitary, so that $\rho(g)^\dagger=\rho(g)^{-1}$ for all $g\in G$.

By the way, the beginning of section $3$ is in error. The sum $\sum_{h\in H}\rho(h)$ is not a projection, because it is not normalized correctly. Instead, $|H|^{-1}\sum_{h\in H}\rho(h)$ is the projection:

$$\left(\frac{1}{|H|}\sum_{h\in H}\rho(h)\right)^2=\frac{1}{|H|^2}\sum_{h_1,h_2\in H} \rho(h_1 h_2)=\frac{1}{|H|}\sum_{h\in H}\rho(h)$$

because $h_1h_2=h$ has $|H|$ solutions $(h_1,h_2)\in H\times H$.

Next, I am not sure why the bottom of the page introduces $\sqrt{d_\rho/|G|}$. According to the definition of the Fourier transform on the previous page, one introduces this constant when transforming from an initially given function $f:G\to\mathbb{C}$ to $\widehat{f}$. However section $3$ begins by defining $\widehat{f}$ to be a certain projection operator (at least it wanted to it seems), so there's no need for that constant.

Thus, let's just talk about the projection map $\widehat{f}(\rho)=|H|^{-1}\sum_{h\in H}\rho(h)$. We have

$$\begin{array}{ll} \|\widehat{f}(\rho)\|^2 & \displaystyle =\left\|\frac{1}{|H|}\sum_{h\in H}\rho(h)\right\|^2 \\ & \displaystyle =\frac{1}{|H|^2}\mathrm{tr}\left(\sum_{h_1\in H}\rho(h_1)\right)\left(\sum_{h_2\in H}\rho(h_2)\right)^\dagger \\ & \displaystyle =\frac{1}{|H|^2}\mathrm{tr}\sum_{h_1,h_2\in H}\rho(h_1h_2^{-1}) \\ & \displaystyle =\frac{1}{|H|}\sum_{h\in H}\chi(h), \end{array}$$

again because $h_1h_2^{-1}=h$ has $|H|$ solutions $(h_1,h_2)\in H\times H$. The above is $\langle \chi,\chi_{1_H}\rangle_H$.


The inner product $\langle \chi,\psi\rangle_H=\frac{1}{|H|}\sum_{h\in H}\chi(h)\overline{\psi(h)}$ on characters can be used to sift for the multiplicities of irreps within a given rep. Suppose that $V$ is a complex representation of $H$, and that $V\cong \bigoplus_{X\in\widehat{H}}X^{\oplus m(X)}$ is $V$'s decomp into irreps $X\in\widehat{H}$ with multiplicities $m(X)$. Then for a fixed irrep $Y$, because $\hom$ distributes over $\oplus$, we have

$$\begin{array}{ll} \hom_H(V,Y) & \displaystyle =\hom_H\left(\sum_{X\in\widehat{H}} X^{\oplus m(X)},Y\right) \\ & \displaystyle \cong\bigoplus_{X\in\widehat{H}} \hom_H(X,Y)^{\oplus m(X)} \\ & \displaystyle \cong \mathbb{C}^{\oplus m(Y)} \end{array}$$

This follows since, by Schur's lemma, $\hom_H(X,Y)\cong\mathbb{C}$ if $X=Y$ and is $0$ otherwise (when $X,Y$ are irreps of $H$). On the other hand, $\hom(V,Y)$, as a representation of $H$, is isomorphic to the tensor product $V^*\otimes Y$ (a special case of tensor-hom adjunction, the linearization of currying), and so $\dim\hom_H(V,Y)\cong\dim(V^*\otimes Y)^H$. But if $Z$ is an $H$-rep, the dimension of $Z^H$ is just the trace of any projection operator $Z\to Z^H$, which we know $|H|^{-1}\sum_{h\in H}\rho_Z(h)$ is, so applying this with $Z=V^*\otimes Y$ yields $m(Y)=|H|^{-1}\sum_{h\in H}\overline{\chi_V(h)}\chi_Y(h)=\langle \chi_Y,\chi_V\rangle$.


In response to comment thread:

For example, suppose $H=\langle\omega\rangle=\{1,\omega,\omega^2\}$ is the group of $3$rd roots of unity. If we write

$$\sum_{h_2\in H}\rho(h_2)=\rho(1)+\rho(\omega)+\rho(\omega^2)$$

and set $h_1=\omega$, then we have

$$\sum_{h_2\in H}\rho(h_1h_2)=\rho(\omega)+\rho(\omega^2)+\rho(1).$$

It's the same sum, only permuted. Therefore,

$$\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_1h_2)\right)=\left(\color{Purple}{\sum_{h_2\in H}\rho(h_2)}\right)+\left(\color{Blue}{\sum_{h_2\in H}\rho(\omega h_2)}\right)+\left(\color{Green}{\sum_{h_2\in H}\rho(\omega^2 h_2)}\right)$$

$$=\begin{array}{ccccc} & \color{Purple}{\rho(1)} & \color{Purple}{+} & \color{Purple}{\rho(\omega)} & \color{Purple}{+} & \color{Purple}{\rho(\omega^2)} \\ + & \color{Blue}{\rho(\omega)} & \color{Blue}{+} & \color{Blue}{\rho(\omega^2)} & \color{Blue}{+} & \color{Blue}{\rho(1)} \\ + & \color{Green}{\rho(\omega^2)} & \color{Green}{+} & \color{Green}{\rho(1)} & \color{Green}{+} & \color{Green}{\rho(\omega)} \end{array} \quad =3\big[\rho(1)+\rho(\omega)+\rho(\omega^2)\big]$$

$\endgroup$
  • 1
    $\begingroup$ @Omar for instance, $(\sum_i a_i)^2=(\sum_i a_i)(\sum_j a_j)=\sum_{i,j}a_ia_j$. same idea. $\endgroup$ – arctic tern May 3 '16 at 6:07
  • 1
    $\begingroup$ @Omar because for all $h\in H$, $\rho(h)$ appears as a summand in $\sum_{h_1,h_2\in H}\rho(h_1h_2)$ a total of $|H|$ times. If it helps, you can think of $x\mapsto h_1x$ as a bijection, hence $$\frac{1}{|H|^2}\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_1h_2)\right)=\frac{1}{|H|^2}\sum_{h_1\in H}\left(\sum_{h_2\in H}\rho(h_2)\right)=\frac{1}{|H|^2}|H|\sum_{h\in H}\rho(h)$$ $\endgroup$ – arctic tern May 3 '16 at 6:53
  • 1
    $\begingroup$ I'll repeat what I said: "for all $h\in H$, $\rho(h)$ appears as a summand in $\sum_{h_1,h_2\in H}\rho(h_1h_2)$ a total of $|H|$ times." This is because we can write any particular $h$ in the form $h_1h_2$ with $h_1,h_2\in H$ a total of $|H|$ many ways. Equivalently, the map $H\times H\to H$ given by $(h_1,h_2)\mapsto h_1h_2$ is an $|H|$-to-$1$ function. I am running out of ways to say the same thing. Also see my previous comment: Do you get why, for any fixed $h_1$, we have $\sum_{h_2\in H}\rho(h_1h_2)=\sum_{h_2\in H}\rho(h_2)$? $\endgroup$ – arctic tern May 3 '16 at 19:49
  • 1
    $\begingroup$ @OmarShehab Because for fixed $h_1$, the map $x\mapsto h_1x$ is a bijection on $H$, and so both sums have exactly the same summands, just possibly in a different order. $\endgroup$ – arctic tern May 4 '16 at 1:44
  • 1
    $\begingroup$ For example, suppose $H$ is the fifth roots of unity generated by a primitive root $\zeta$. If we write $$\sum_{h_2\in H}\rho(h_2)=\rho(1)+\rho(\zeta)+\rho(\zeta^2)+\rho(\zeta^3)+\rho(\zeta^4),$$ and set $h_1=\zeta^2$, then we have $$\sum_{h_2\in H}\rho(h_1h_2)=\rho(\zeta^2)+\rho(\zeta^3)+\rho(\zeta^4)+\rho(1)+\rho(\zeta),$$ which is exactly the same sum, only with its summands permuted. $\endgroup$ – arctic tern May 4 '16 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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