Group Theory Essentials

Several of the most important quantum algorithms — Shor's factoring, Deutsch–Jozsa, Simon's algorithm — are unified by a single algebraic framework called the Hidden Subgroup Problem. Before diving into that framework you need a small vocabulary from abstract algebra. This lesson gives you exactly what you need: groups, subgroups, and cosets.

Groups

A group $(G, \cdot)$ is a set $G$ equipped with a binary operation $\cdot$ satisfying four axioms:

1. Closure — for all $a, b \in G$, the product $a \cdot b$ is also in $G$.
2. Associativity — $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for all $a, b, c \in G$.
3. Identity — there exists an element $e \in G$ such that $e \cdot a = a \cdot e = a$ for every $a \in G$.
4. Inverses — for every $a \in G$ there exists $a^{-1} \in G$ with $a \cdot a^{-1} = e$.

The operation need not be commutative. When $a \cdot b = b \cdot a$ for all $a, b$ the group is called abelian (or commutative).

Familiar examples

| Group | Operation | Identity | Abelian? | |-------|-----------|----------|----------| | $\mathbb{Z}$ (integers) | addition | $0$ | yes | | $\mathbb{Z}_N = \{0,1,\dots,N{-}1\}$ | addition mod $N$ | $0$ | yes | | $\mathbb{Z}_2^n = \{0,1\}^n$ | bitwise XOR | $\mathbf{0}$ | yes | | $(\mathbb{Z}/N\mathbb{Z})^*$ (units mod $N$) | multiplication mod $N$ | $1$ | yes | | $S_n$ (permutations of $n$ items) | composition | identity permutation | no (for $n \geq 3$) |

The group $\mathbb{Z}_2^n$ with bitwise XOR is the domain for Simon's algorithm; the group $(\mathbb{Z}/N\mathbb{Z})^*$ is the domain for Shor's order-finding.

Subgroups

A subset $H \subseteq G$ is a subgroup of $G$ if $H$ is itself a group under the same operation. The quickest check is the subgroup criterion: a non-empty subset $H$ is a subgroup if and only if for every $a, b \in H$, the element $a \cdot b^{-1}$ is also in $H$.

Example — even integers

Inside $(\mathbb{Z}, +)$, the set of even integers $2\mathbb{Z} = \{\dots, -4, -2, 0, 2, 4, \dots\}$ is a subgroup: the sum of two even numbers is even, and the additive inverse of an even number is even.

Example — powers of a group element

Given any $g \in G$, the set $\langle g \rangle = \{e, g, g^2, g^3, \dots\}$ is a subgroup called the cyclic subgroup generated by $g$. If $g$ has order $r$, then $|\langle g \rangle| = r$.

Lagrange's theorem states that for a finite group $G$ and any subgroup $H$, $|H| \text{ divides } |G|.$ This is the reason we always expect the order $r$ in Shor's algorithm to divide $\phi(N)$.

Cosets

Given a subgroup $H \leq G$ and an element $g \in G$, the left coset of $H$ containing $g$ is

$g H = \{ g \cdot h \;\mid\; h \in H \}.$

Two left cosets are either identical or completely disjoint; together they partition $G$ into $[G : H] = |G|/|H|$ equal-sized pieces (each of size $|H|$).

Concrete example in $\mathbb{Z}_6$

Let $G = \mathbb{Z}_6 = \{0,1,2,3,4,5\}$ (addition mod 6) and $H = \{0, 2, 4\}$ (the even residues — a subgroup of order 3). The cosets are

$H = \{0, 2, 4\}, \qquad 1 + H = \{1, 3, 5\}.$

There are two cosets ($|G|/|H| = 6/3 = 2$), they are disjoint, and their union is all of $\mathbb{Z}_6$.

Why this matters for quantum computing

The Hidden Subgroup Problem (HSP) asks: given a function $f : G \to S$ that is constant on cosets of some hidden subgroup $H$ and distinct on different cosets, find $H$.

Every classical algorithm for this problem requires exponentially many queries when $G$ is large. Quantum algorithms can solve it with a polynomial number by creating a uniform superposition over a coset, measuring $f$, and then using the quantum Fourier transform to extract the hidden subgroup from the resulting coset state.

Deutsch–Jozsa, Bernstein–Vazirani, Simon's algorithm, and Shor's algorithm are all instances of this single template applied to specific groups:

• Deutsch–Jozsa: $G = \mathbb{Z}_2^n$, $H \in \{\{0^n\}, \mathbb{Z}_2^n\}$.
• Simon's algorithm: $G = \mathbb{Z}_2^n$, $H = \{0^n, s\}$ for a hidden string $s$.
• Shor's order-finding: $G = \mathbb{Z}$, $H = r\mathbb{Z}$ (multiples of the hidden order $r$).

The next lesson makes this connection precise.

Sign in on the full site to ask questions and join the discussion.