The states aren't really important, and they aren't really physical. The fundamental thing is the operator algebra

When you're first learning quantum, you learn to think of states as "things", and operators/observables as "measurements we do to states". Given a state $\ket \psi$ and a Hermitian operator $\mathcal{O}$, we get the "expected value of measuring $\mathcal{O}$ on $\ket \psi$" by computing $\mathbb{E}_{\ket\psi}[\mathcal{O}] := \bra \psi \mathcal{O} \ket \psi$.

But it turns out we can also look at the problem from a different perspective. When you learn intro quantum, you don't actually spend that long learning about properties of states. Instead, you learn a lot about the properties of the observables. You study their commutation relations, and that sort of thing. Really, the basic objects that we study are these observables. And in fact, we can take observables to be our fundamental "things". Then, you can think of states as "ways of measuring observables".

And we can make this formal. We can say that a state is any positive, linear functional of norm 1 on the space of observables. By linear functional, I mean that it's a function that takes in operators and spits out real numbers. By positive, I mean that the functions are nonnegative on positive semidefinite operators. And by norm 1, I mean that these functions are 1 on the identity. It's pretty simple to check that the expected value function $\mathbb{E}_{\ket\psi}$ that I defined above has these properties.

Amazingly, the GNS construction tells us that ever positive linear function of norm 1 can be represented as a vector state (i.e. it is an expected value for some state vector). So the reasonable measurements that we can do to operators look like measuring state vectors! We can think of state vectors as being a convenient representation of the measurements we can do to our operators.

Functions on Groups

Given a finite group $G$, I want to consider the algebra of complex-valued functions on $G$ (i.e. $\{f:G \to \C\}$).

Why? There are several reasons to study this algebra of functions. From a purely group-theoretic perspective, it is interesting because it can help you understand groups better. Today, however, I'll mostly focus on applications to CS.

What algebra structure are we using?

There are multiple choices of algebra structure on the set of functions $\{f:G \to \C\}$. Addition and scalar multiplication are pretty straightforward; clearly they should be done pointwise. You might also want to multiply the functions pointwise. This defines a perfectly fine algebra, but then nothing in our algebra actually depends on the group structure. We want to take advantage of the group structure to study these functions. So we won't define multiplication this way. Instead, we take the slightly stranger definition that \[ f_1 * f_2 (g) := \sum_{g_1 g_2 = g} f_1(g_1)\cdot f_2(g_2) \] We call this product convolution.

Miscellaneous facts about $\C[G]$

For $h \in G$, we define the $\delta$-function \[ \delta_h(g) := \begin{cases} 1 & g = h\\0 & \text{otherwise}\end{cases} \] With the convolution product, the multiplicative identity is the function $\delta_e$.

You can check that \[ f \star \delta_e(g) = \sum_{g_1g_2 = g} f(g_1) \delta_e(g_2) = f(g)\delta_e(e) = f(g) \] One useful basis for $\C[G]$ is given by $\{\delta_h\;|\;h \in G\}$.

We can define a hermitian product on $\C[G]$ by \[ \inrp {f_1} {f_2} := \frac 1 {|G|} \sum_{g \in G} f_1(g) \cdot \overline{f_2(g)} \]

Example: $\C[\Z/n\Z]$

Suggestively, I'll denote $\delta_k$ by $x^k$. Then, elements of $\C[\Z/n\Z]$ are sums $a = \sum_{i=0}^{n-1} a_i x^i$. The product is given by \[ a\cdot b = \sum_{i = 0}^{n-1} \left[\sum_{j + k = i} a_j b_k \right]x^i \] So we see that $\C[\Z/n\Z] = \C[x]/(x^n-1)$. This is an important example for CS applications.

One useful tool for studying rings is studying modules over that ring. This trick will be very helpful to us.

Modules over $\C[G]$

Let $M$ be a module over $\C[G]$. First, we note that we can use our action of $\C[G]$ on $M$ to define an action of $\C$ on $M$. Simply define $\lambda \cdot m := (\lambda \delta_e) \cdot m$ for all $m \in M$. You can check that this makes $M$ into a complex vector space. Since $\delta_e$ is the multiplicative identity, it commutes with every element of $\C[G]$. So the action of every other element of $\C[G]$ on $M$ is linear with respect to this $\C$-action.

Furthermore, given a $\C$-vector space structure on $M$, the $\C[G]$ module structure is entirely determined by how each $\delta_g$ acts on $M$. So we can describe $M$ as a complex vector space along with a map $\rho:G \to \Aut(M)$.

Representations

Characters

Now we've gone full circle and come back to $\C[G]$.

Note: $\chi_V$ is constant on conjugacy classes of $G$.

So we can also think the characters are complex-valued class functions.

There's a very nice theorem about the inner products of characters.

I don't have time to prove this at the moment. It's not too hard, though.

Therefore, the characters of irreps are an orthonormal subset of the group algebra.

Fact: the number of irreducible representations of $G$ is the same as the number of conjugacy classes of $G$. Therefore, characters of irreps form a basis for the space of class functions on $G$.

Example: $\C[\Z/n\Z]$

Recall that $\C[\Z/n\Z] = \C[x]/(x^n-1)$, the ring of polynomials modulo $(x^n-1)$. What do these look like in the irreducible character basis?

What are the irreps of $\Z/n\Z$?

Thus, to find the irreps of $\Z/n\Z$, we only have to consider homomorphisms $\phi : \Z/n\Z \to \Aut[\C] = \C \setminus \{0\}$. Since $\Z/n\Z$ is cyclic, these homomorphisms are determined by $\phi(1)$. Since 1 has order $n$ in $\Z/n\Z$, $\phi(1)$ must be an $n$th root of unity. Let $\omega$ be a primitive $n$th root of unity. Then for all $k = 0, \ldots, n-1$ we get a homomorphism $\phi_k : \Z/n\Z \to \C$ given by $\phi_k(1) = \omega^k$. Since we have found $n$ irreducible representations, we have them all. Since the representations are all 1-dimensional, these are also the irreducible characters.

We can express a function on $\Z/n\Z$ in the character basis by taking its inner products with the irreducible characters. \[ \inrp {\phi_k} f = \sum_{\ell=0}^{n-1} \phi_k(\ell) \overline{f(\ell)} = \sum_{\ell=0}^{n-1} \overline{f(\ell)} \omega^{\ell k}\] Recall, we expressed these functions $f$ as $f = \sum_{\ell = 0}^{n-1} f(\ell) x^{\ell}$. So this is essentially evaluating the polynomial on $\omega^k$. This also looks a lot like the Fourier transform. In fact, it is the Discrete Fourier Transform.

If we write the function as a column vector, we can express this operation by the matrix \[ \begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1\\ 1 & \omega & \omega^2 & \omega^3 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^4 & \omega^6 & \cdots & \omega^{2(n-1)}\\ 1 & \omega^3 & \omega^6 & \omega^9 & \cdots & \omega^{3(n-1)}\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & \omega^{n-1} & \omega^{2(n-1)} & \omega^{3(n-1)} & \cdots & \omega^{(n-1)(n-1)} \end{pmatrix} \begin{pmatrix} \overline{f(0)}\\ \overline{f(1)}\\ \overline{f(2)}\\ \overline{f(3)}\\ \vdots\\ \overline{f(n-1)} \end{pmatrix} \] It turns out that because this matrix is so regularly-structured, we can compute this matrix-vector product really quickly. The Fast Fourier Transform lets us compute this in $O(n \log n)$ time, which is must faster than the naive $O(n^2)$ time for regular matrix-vector products. The Fast Fourier Transform has applications all over CS. It's used in signal processing, data compression (e.g. image processing), solving PDEs, multiplying polynomials, multiplying integers, and convolution, among other things.