Here is a TeX version, that may be easier to read.
Group_Theory_Part1.pdf (185.9K)
Number of downloads: 49
Quantum computing studies models of computation which utilize quantum mechanical phenomena to perform the computations. Such phenomena include entanglement (https://en.wikipedia.org/wiki/Quantum_entanglement) and superposition (https://en.wikipedia.org/wiki/Quantum_superposition). While the study of quantum computing dates back to 1980, the field garnered considerable interest due to the algorithm of Peter Shor which shows that quantum computers can efficiently solve the integer factorization problem. The RSA cryptosystem, which is used to secure online transactions, is based on the difficulty of factoring integers. As a result of Shor's algorithm, the RSA cryptosystem is susceptible to attacks from quantum computers. The good news is, at the moment, practical quantum computing does not exist.
Aside from its applications to cryptology, quantum computation shows promise in more efficiently solving a number of problems compared to classical computing models. Examples of such problems include simulating molecular many-body systems in chemistry and physics, machine learning, numerical linear algebra, and searching unstructured data. Grover's quantum algorithm for searching unstructured data, for instance, provides quadratic speedup compared to classical computers, which is also provably optimal. Today, quantum computing and information is in its infancy, with a growing amount of theoretical research.
In order to model notions such as superposition and entanglement, a number of mathematical tools are required. Namely, quantum computing utilizes tools from representation theory (https://en.wikipedia.org/wiki/Representation_theory), Lie groups (https://en.wikipedia.org/wiki/Lie_group), and Fourier analysis (https://en.wikipedia.org/wiki/Fourier_analysis). It is quite possible to avoid the more technical language from these areas, restricting to linear algebra, basic group theory, and some familiarity with the field of complex numbers. In this tutorial series, we seek to introduce the requisite linear algebra and group theory, so that we can thoroughly explore quantum computation in later tutorials. We also seek to convey some of the relevant ideas from representation theory, Lie groups, and Fourier analysis, without being overly technical. The goal of this tutorial is to introduce basic notions from group theory, including the quaternion group, subgroups, homomorphisms, and isomorphisms. This particular tutorial assumes some comfort reading mathematical proofs, but no background in any particular area of mathematics.
Group Theory
Introduction
The study of groups is of key importance in quantum computing for several reasons. Quantum computers are particularly well-suited for solving various number theoretic and algebraic problems, such as factoring. Many of these problems reduce to the Hidden Subgroup Problem (https://en.wikipedia.org/wiki/Hidden_subgroup_problem), which is a central problem in quantum computing. For instance, Shor's quantum factoring algorithm effectively solves the Hidden Subgroup Problem for Abelian groups. Solutions to the Hidden Subgroup Problem for non-Abelian groups are also of particular interest. Namely, an efficient solution for the Hidden Subgroup Problem over the Dihedral group (https://en.wikipedia.org/wiki/Dihedral_group) would yield an efficient quantum algorithm to solve certain Shortest Vector Problems (https://en.wikipedia.org/wiki/Lattice_problem#Shortest_vector_problem_(SVP)) in lattices. The security of lattice-based cryptosystems relies on the difficulty of these Shortest Vector Problems. Similarly, a solution to the Hidden Subgroup Problem over the Symmetric group (https://en.wikipedia.org/wiki/Symmetric_group) would yield an efficient quantum algorithm to solve the Graph Isomorphism (https://en.wikipedia.org/wiki/Graph_isomorphism_problem) problem. At present, the best known classical algorithm for Graph Isomorphism runs in quasi-polynomial time.
Beyond solving algebraic problems, quantum computation is modeled by multiplying complex unitary matrices. The complex unitary matrices of dimension n form a group, which in fact represents the unit quaternions. The group of 2 x 2 complex unitary matrices also admits a certain geometric structure, providing rotational symmetries of the three-dimensional unit sphere, which we call S^{3}. Intuitively, quantum computation involves rotating S^{3}, doing some work, and then rotating S^{3} back to its original position. The fact that the unitary matrices form a group allows us to undo the original rotation.
The goal of this tutorial is to introduce enough group theory, so that we can discuss the algebraic tools needed to model quantum computation, as well as several important quantum algorithms such as Shor's quantum factoring algorithm and Grover's quantum search algorithm.
Informally, a group provides an abstraction of the notion of multiplication. Formally, a group is defined as follows.
Definition 1 (Group).
A group is an ordered pair (G, ★), where G is a set and ★ : G x G -> G satisfies the following axioms:
- Associativity: For every a, b, c \in G, (a ★ b) ★ c = a ★ (b ★ c).
- Identity: There exists an element which we call 1 \in G, such that for every a \in G the following holds: 1 ★ a = a ★ 1 = a.
- Inverses: For every a \in G, there exists a multiplicative inverse of a, which we call a^{-1} \in G, that satisfies: a ★ a^{-1} = a^{-1} ★ a = 1.
Remark: By convention, the multiplication operator is usually dropped. That is, we write a ★ b = ab. Note that as a group has an identity element, the group is necessarily non-empty.
Let us now consider some examples of groups.
Example 1.
Let Z denote the set of integers, R denote the set of real numbers, and C denote the set of complex numbers. Each of these sets forms a group under the operation of addition, with 0 as the identity element (recall that x + 0 = x for any x). Furthermore, R^{x} =R - {0} and C^{x} = C - {0} form groups under multiplication, with 1 as the multiplicative identity (as 1x = x for any x). For a non-zero x \in R, the multiplicative inverse x^{-1} = \dfrac{1}{x}. That is, x \cdot \dfrac{1}{x} = 1. Now for a non-zero z = a + bi \inC, the multiplicative inverse of z is:
z^{-1} = (a-bi) / (a^{2} + b^{2}).
Observe that (a+bi)(a-bi) = a^{2} - b^{2}(i^{2}) = a^{2}+b^{2}. Thus:
(a+bi) * (a-bi)/(a^{2} + b^{2}) = (a^{2} + b^{2}) / (a^{2} + b^{2}) = 1,
as desired. We note that the non-zero integers do not form a group under multiplication, as most integers do not have multiplicative inverses. In particular, the multiplicative inverse of 2 is 1/2, which is certainly not an integer. Rather, the multiplicative group of the integers Z^{x} = {1, -1}.
Example 2.
Let n >= 1 be a positive integer, and denote Z_{n} = { \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1} } to be the integers modulo n, which forms a group under addition. Here, \overline{0} denotes the set of integers which have remainder 0 when divided by n. Similarly, \overline{1} is the set of integers which have remainder 1 when divided by n, and so on. The sets \overline{0}, \overline{1}, \overline{2}, \ldots, \overline{n-1} form equivalence classes; that is, two integers are equivalent if they have the same remainder when divided by n. We add two elements of Z_{n} by adding the remainders, then dividing by n. That is, \overline{i} + \overline{j} = \overline{i+j}.
We illustrate the addition in Z_{6}. Recall that Z_{6} = { \overline{0}, \overline{1}, \overline{2}, \overline{3}, \overline{4}, \overline{5} }. Consider:
- \overline{2} + \overline{3} = \overline{2 + 3} = \overline{5}.
- \overline{4} + \overline{5} = \overline{4 + 5}. Now when we divide 9 by 6, a remainder of 3 is left over. So \overline{4 + 5} = \overline{3}.
- \overline{5} + \overline{1} = \overline{5+1}. Now when we divide 6 by 6, a remainder of 0 is left over. So \overline{5 + 1} = \overline{0}. In particular, observe that the additive inverse of \overline{i} is \overline{n-i}.
Remark: The groups we have seen thus far all have commutative group operations. Such groups are known as \textit{Abelian groups.} In general, groups do not have commutative operations. The group of quaternions and matrix groups (under the operation of matrix multiplication) are non-Abelian groups of particular interest in quantum computing. We will look at these groups more later.
We conclude with the following proposition, establishing some basic results about groups.
Proposition 2.1.
Let G be a group. The following hold:
- The identity element 1 \in G is unique.
- For each a \in G, a^{-1} is unique.
- (a^{-1})^{-1} = a for all a \in G.
- (ab)^{-1} = b^{-1}a^{-1}.
- For any a_{1}, a_{2}, \ldots, a_{n}, the product a_{1}a_{2} \cdots a_{n} is independent of how the expression is parenthesized. (This is known as the Generalized Associative Law).
Proof:
- Let f, g \in G be identities. So fg = f, as g is an identity. Similarly, as f is an identity, fg = g. So f = g, as desired.
- Let a \in G. Let x, y \in G such that ax = ya = 1. Now y = y1 = y(ax). By associativity, we have that y(ax) = (ya)x = x. So y = x, as desired.
- Let a \in G. Observe that a^{-1}a = aa^{-1} = 1. So a is an inverse of a^{-1}. By part (B), inverses are unique, so (a^{-1})^{-1} = a.
- Let a, b \in G. Now observe that abb^{-1}a^{-1} = a(bb^{-1})a^{-1} = aa^{-1} = 1. So b^{-1}a^{-1} is an inverse of ab. As inverses are unique, (ab)^{-1} = b^{-1}a^{-1}, as desired.
- We prove the result by induction on n. When n \leq 3, the associativity axiom of the group yields the desired result. Now fix k \geq 3 and suppose that for any a_{1}, \ldots, a_{k} \in G, the product a_{1}a_{2}\cdots a_{k} is uniquely determined, regardless of the parenthesization. Fix a_{k+1} \in G and i \in \{1, ..., k-1\}. Let x := a_{1} \cdots a_{i} and y := a_{i+1} \cdots a_{k}. By the inductive hypothesis, x and y are invariant under parenthesization. Now observe that:
a_{1} * ... * a_{k} a_{k+1} = (xy)a_{k+1}.
By associativity, (xy)a_{k+1} = x(y \cdot a_{k+1}). The result follows by induction.
QED.
Quaternion Group
In this section, we introduce the quaternion group of order 8, which we denote Q_{8}. The elements of Q_{8} serve as the building blocks for the ring of Hamiltonians (also known as the ring of quaternions). The key takeaway for this section is to understand how the elements of Q_{8} interact, which will be particularly important later. Additionally, this section serves to provide an example of a non-Abelian group.
The elements of Q_{8} are { 1, -1, i, -i, j, -j, k, -k}. The group operation can be deduced from a number of relations:
- We first note that -1 behaves as one would expect in R. That is, (-1)^{2} = 1 and (-1)x = -x for any x \in Q_{8}.
- Next, we have that i, j, k are all square roots of -1. That is, i^{2} = j^{2} = k^{2} = -1.
- Finally, we have that ij = k, ji = -k (so ij = -ji), jk = i, kj = -i (so jk = -kj), and ik = -j, ki = j (so ik = -ki). As ij = -ji, we say that i and j anti-commute. Similarly, i and k anti-commute, and j and k anti-commute.
For completeness, we include the multiplication table for Q_{8} below.
Subgroups and Homomorphisms
The two primary approaches to studying groups. The first approach is to examine the subgroups of a given group G; that is, we examine the subsets of G that also possess the group structure. The second approach is to embed one group G into another group H in such a way that preserves the group operation. Such embeddings are known as group homomorphisms. We note that group homomorphisms need not be one-to-one; it is quite possible (and often of interest) to map a larger group into a smaller group. We begin by formalizing some of these notions.
Definition (Subgroup).
Let G be a group. A subset H \subset G is said to be a subgroup of G if H itself is also a group. We denote that H is a subgroup of G as follows: H \leq G.
Example 3.
Let G = Z_{6}. Consider the set H = { \overline{0}, \overline{3}} \subset G. We show that H is a subgroup of G. H is inherits the group operation of G, which is associative as G is a group. Now the identity element of G is \overline{0}, which is in H. Now observe that \overline{0} is its own inverse, and \overline{3} is its own inverse. So H is closed under the group operation of G, as well as inverses. Thus, H is a subgroup of G.
Example 4.
Let G = Q_{8}, and let H = {1, -1, i, -i}. By inspection, one can check that H is closed under the group operation. Observe that 1 \in H, so H has the identity element of Q_{8}. Now we note that -1 is its own inverse. Similarly, i(-i) = -i^{2} = -(-1) = 1. So i and -i are inverses. Thus, we have that H is a subgroup of G.
Definition (Group Homomorphism).
Let G and H be groups. A group homomorphism \varphi : G -> H is a function satisfying \varphi(xy) = \varphi(x)\varphi(y) for every x, y \in G.
Example 5.
Let G = Z_{4} and H = Z_{2}. Consider the map \varphi : Z_{4} \to Z_{2} sending:
\varphi( \overline{0}_{4} ) = \overline{0}_{2}
\varphi( \overline{2}_{4} ) = \overline{0}_{2}
\varphi( \overline{1}_{4} ) = \overline{1}_{2}
\varphi( \overline{3}_{4} ) = \overline{1}_{2}
We verify that \varphi is indeed a group homomorphism. Let \overline{x}_{4}, \overline{y}_{4} \in Z_{4}. Now \varphi( (\overline{x+y})_{4}) = \overline{0}_{2} if and only if (\overline{x+y})_{4} = (\overline{x}_{4} + \overline{y}_{4}) \in { \overline{0}_{4}, \overline{2}_{4} }. So \varphi( (\overline{x+y})_{4}) = \varphi( \overline{x}_{4}) + \varphi(\overline{y}_{4}), as desired.
Example 6.
We note that there exists at least one homomorphism between every pair of groups; namely, the trivial homomorphism. Let G, H be groups. The \textit{trivial homomorphism} \varphi : G \to H maps \varphi(g) = 1_{H} for every g \in G. Here, 1_{H} is the identity element of H.
Homomorphisms preserve a number of important properties of the original group. We examine a couple of them here. First, we note that a group homomorphism preserves the identity element. Similarly, the image of a group homomorphism \varphi : G \to H is a subgroup of H.
Lemma 2.1.
Let G, H be groups, and let \varphi : G \to H be a group homomorphism. Then \varphi(1_{G}) = 1_{H}.
Proof: We note that \varphi(1_{G}) = \varphi(1_{G}) \cdot 1_{H}. Similarly, \varphi(1_{G}) = \varphi(1_{G} \cdot 1_{G}) = \varphi(1_{G}) \varphi(1_{G}). So \varphi(1_{G}) \cdot 1_{H} = \varphi(1_{G}) \varphi(1_{G}). By cancelling out a \varphi(1_{G}) term on each side, we obtain that \varphi(1_{G}) = 1_{H}, as desired. QED.
Lemma 2.2
Let G, H be groups, and let \varphi : G \to H be a group homomorphism. Let g \in G. We have that \varphi(g^{-1}) = \varphi(g)^{-1}.
Proof:
We have that \varphi(gg^{-1}) = \varphi(1_{G}) = 1_{H}, where the last equality follows from Lemma \ref{IdentityPreserved}. Similarly, we have that \varphi(gg^{-1}) = \varphi(g)\varphi(g^{-1}) = 1_{G}. So \varphi(g^{-1}) = \varphi(g)^{-1}, as desired. QED.
Lemma 2.3. Let G, H be groups, and let \varphi : G \to H be a group homomorphism. Then \varphi(G) = { \varphi(g) : g \in G } is a subgroup of H.
Proof:
By Lemma 2.1, \varphi(1_{G}) = 1_{H}. So 1_{H} \in \varphi(G). We next show that \varphi(G) is closed under the group operation. Let k, \ell \in \varphi(G), and let g, h \in G such that \varphi(g) = k and \varphi(h) = \ell. As \varphi is a homomorphism, we have that k \ell = \varphi(g)\varphi(h) = \varphi(gh). As G is a group, gh \in G. By definition of \varphi(G), \varphi(gh) \in H. So k\ell \in \varphi(G), as desired. By Lemma 2.2, \varphi(g^{-1}) = \varphi(g)^{-1} for all g \in G. Using this fact, as well as the fact that G is closed under inverses, we have that \varphi(G) is closed under inverses. So \varphi(G) is a subgroup of H. QED.
Isomorphisms
Groups are often represented in several different manners, including as permutations, matrices, or by a set of variables which we call generators. It is often non-obvious that these different representations all describe the same group. The notion of a group isomorphism captures such instances of representing the same group in two different ways. We begin with the definition of a group isomorphism.
Definition (Group Isomorphism).
Let G, H be groups. A group isomorphism between G and H is a bijection \varphi : G \to H that is also a group homomorphism. If such an isomorphism exists, we say that G and H are isomorphic, denoted G \cong H.
There are some natural examples of isomorphism.
Example 7. Let G be a group. The identity map \text{id} : G \to G, which maps every element g to itself, is an isomorphism of G.
Example 8. Consider the group R under addition, and the group R^{+} of positive integers under multiplication. Let \text{exp} : R \to R^{+} be the map sending x \mapsto e^{x}. The map \text{exp} is a bijection, as there is a well-defined inverse function: the natural logarithm. Now observe that \text{exp}(x+y) = e^{x}e^{y}, by the rules of exponents. So \text{exp} is a homomorphism. We conclude that \text{exp} is an isomorphism. So the additive group R is isomorphic to the multiplicative group R^{+}.
Remark: Most groups are non-isomorphic. In particular, as an isomorphism is a bijection, two groups of different sizes are non-isomorphic. Similarly, it is usually the case that two groups of the same size are not isomorphic. Establishing non-isomorphism is more challenging than establishing isomorphism. To establish that two groups are isomorphic, it suffices to provide an isomorphism between the two groups. In order to establish that two groups are non-isomorphic, we seek to find some invariant that is present in one group, but not the other. We establish some basic invariants that isomorphism preserves.
Lemma 2.4. Let G, H be groups such that G is Abelian and G \cong H. Then H is Abelian.
Proof: Let \varphi : G \to H be an isomorphism. Let k, \ell \in H. As \varphi is an isomorphism, there exist g, h \in G such that \varphi(g) = k and \varphi(h) = \ell. As G is Abelian, gh = hg. So k\ell = \varphi(gh) = \varphi(hg) = \ell k. Thus, H is Abelian. QED.
We now introduce the notion of order.
Definition (Order). Let G be a group. The order of G is the cardinality of G as a set, which we denote as |G|. For an element g \in G, the order of g, denoted |g| := min { n \in Z^{+} : g^{n} = 1}. If no such n exists, we have that |g| = infinity.
Remark: We note that |g| is also the size of the subgroup generated by G, a notion we will not pursue further here.
Example 9. Let G = Z_{6}. We note that |G| = 6. Consider \overline{3} \in G. Observe that \overline{3} + \overline{3} = \overline{0}. So |\overline{3}| \leq 2. Now as \overline{3} != \overline{0}, we have that |\overline{3}| > 1. So |\overline{3}| = 2. Similarly, |\overline{2}| = 3.
\end{ex}
Remark: The only element in a group with order 1 is the identity element. For finite groups, the order of any element must divide the order of the group. This is known as Lagrange's Theorem, which we will not prove here.
We now show that isomorphism preserves the order of the elements.
Lemma 2.5. Let G, H be groups, and let \varphi : G \to H be a group homomorphism. For every g \in G, |g| \geq |\varphi(g)|.
Proof: Fix g \in G. If |g| = \infty, we are done. So suppose n := |g| < \infty. We have that \varphi(g^{n}) = \varphi(g)^{n}, using the fact that \varphi is a homomorphism. As |g| = n, \varphi(g^{n}) = \varphi(1_{G}) = 1_{H}, where the last equality follows from Lemma \ref{IdentityPreserved}. So |\varphi(g)| \leq n, as desired. QED.
Lemma 2.6. Let G, H be groups, and let \varphi : G \to H be a group isomorphism. Let \varphi^{-1} : H \to G be the inverse function of \varphi. Then \varphi^{-1} is also an isomorphism.
Proof: As \varphi is a bijection, \varphi^{-1} : H \to G is a well-defined function and a bijection. It suffices to verify that \varphi^{-1} is a group homomorphism. Let a, b \in G, and let c, d \in H such that \varphi(a) = c and \varphi(b) = d. So \varphi(ab) = \varphi(a)\varphi(b) = cd. Applying \varphi^{-1}, we obtain that: \varphi^{-1}(cd) = \varphi^{-1}(\varphi(ab)) = ab. Similarly, \varphi^{-1}©\varphi^{-1}(d) = ab. So \varphi^{-1} is a homomorphism. The result follows. QED.
With Lemmas 2.5 and 2.6 in tow, we show that isomorphism preserves the order of the elements.
Lemma 2.7. Let G, H be groups, and let \varphi : G \to H be an isomorphism. For every g \in G, |g| = |\varphi(g)|.
Proof: By Lemma 2.5, we have that |g| \geq |\varphi(g)|. By Lemma 2.6, \varphi^{-1} is an isomorphism. Exchanging the roles of g and \varphi(g), we have that |\varphi(g)| \geq |g|. So |g| = |\varphi(g)|, as desired. QED.
Remark: Fix groups G and H, such that G \cong H. Lemma 2.7 tells us that for every k \in N where k divides |G|, G and H have the same number of elements of a given order k.
Example 10. The group Q_{8} and the group Z_{8} are non-isomorphic. There are a couple of ways to see this. First, we recall that Z_{8} is Abelian, while Q_{8} is not Abelian. So we conclude that Q_{8} \not \cong Z_{8}.
Alternatively, we observe that every element in Q_{8} has order at most 4. The elements \pm i, \pm j, \pm k all have order 4, while -1 has order 2. Of course, 1 has order 1. Now Z_{8} has several elements of order 8, including \overline{1}, \overline{3}, \overline{5}, and \overline{7} (recall that \overline{0} is the identity element in Z_{8}). As Q_{8} has no elements of order 8, we note that Q_{8} \not \cong Z_{8}.
Conclusion
In this tutorial, we have introduced basic notions from group theory, including subgroups, homomorphisms, and isomorphisms. We also introduced common examples of groups, including those most relevant to quantum computation. In the next tutorial, we will examine the ring of Hamiltonians H, including linear representations as well as the topological structure of the multiplicative group H^{x} as the sphere S^{3}. Rotational symmetries of S^{3} are of key importance in modeling quantum computation.
This post has been edited by macosxnerd101: 29 December 2018 - 06:05 PM