Pauli groups
When we multiply the four Pauli matrices with one another we get Pauli matrices in return, but with possible phase factors \pm1 and \pm i (e.g. XY=iZ).
Once we include these phase factors, ensuring that we have a set that is closed under matrix multiplication, we obtain the single qubit Pauli group, which we denote by \mathcal{P}_1.
In order to characterise a group, we can simply list all its elements and define the group operation on each possible pair, but it is usually more efficient to use the notion of group generators.
Given a group G, these are elements g_1,\ldots,g_n of the group that are independent (we cannot write any one of them as a product of some of the others) and such that every element of G can be written as a product of (possibly repeated) elements of \{g_1,\ldots,g_n\}.
If G is generated by g_1,\ldots,g_n, then we write G=\langle g_1,\ldots,g_n\rangle.
The single-qubit Pauli group \mathcal{P}_1 is defined by
\begin{aligned}
\mathcal{P}_1
&\coloneqq \langle X,Y,Z\rangle
\\&= \{\pm\mathbf{1}, \pm i\mathbf{1}, \pm X, \pm iX, \pm Y, \pm iY, \pm Z, \pm iZ\}.
\end{aligned}
The n-qubit Pauli group \mathcal{P}_n is defined to consist of all n-fold tensor products of Pauli matrices, with possible global phase factors \pm1 and \pm i, i.e.
\mathcal{P}_n
\coloneqq \{P_1\otimes\ldots\otimes P_n \mid P_1,\ldots,P_n\in\mathcal{P}_1\}.
This group has 4^{n+1} elements: 4\times4^n, since we have to account for the possible global phase factors (which usually aren’t very important for practical applications, but are necessary in order to have a well defined group).
As a small mathematical aside, we could use some group theory here: \mathcal{P}_n has two trivial (multiplicative) subgroups, namely Z_2=\{\pm1\} and Z_4=\{\pm1,\pm i\}; the quotient group \mathcal{P}_n/Z_4 is exactly the n-qubit Pauli group but with the phases ignored.
Some researchers prefer to think of the (single-qubit) Pauli group as the group generated only by X and Z (leaving out Y), which then only has 8 elements: \pm1, \pm X, \pm Z, and \pm iY.
We do not follow this convention.
One abstract way of defining the Pauli group, without having to make any reference to matrices (and thus to bases), or even to operators, is using the notion of a central product.
This is a way of combining two smaller group into one large group, but “respecting” the commutative parts of each, which means that it arises as a quotient of the direct product (which is somehow the most blunt way of combining together two groups).
The cyclic group of order 4 is the abstract manifestation of something maybe more familiar: the additive group of integers modulo 4.
That is, the numbers 0, 1, 2, and 3 form a group under addition, but where we take the addition to be “remainder 4”, so that e.g. 3+2=1.
In abstract algebra, this group is denoted by C_4.
The dihedral group of order 8 (sometimes, very confusingly, also referred to as being of order 4) arises as the symmetry group of a square: we can rotate a square by 90^\circ, or reflect it along either of the axis joining any two diagonally opposite corners, or reflect it along either of the axis joining the midpoints of any two opposite sides — doing any of these actions leaves the square looking exactly how it started.
But some of these actions describe the same thing!
For example, reflecting through the vertical axis and then the horizontal axis is the same as rotating by 180^\circ (try visualising this by flipping and rotating your hand!), which is a specific example of the more general fact (which we briefly touched upon in Section 2.12) that the composition of two reflections is the same as a rotation through twice the angle between the two axes.
In abstract algebra, this group is denoted by D_8 (though in geometry it is often written as D_4 instead).
The relevance to the Pauli group is this: the central product of C_4 and D_8 is exactly \mathcal{P}_1.
If it is clear that we are working with tensor products of Pauli matrices, then we often (as per usual) omit the tensor product symbol, writing e.g. XY\mathbf{1}Z instead of X\otimes Y\otimes\mathbf{1}\otimes Z when talking about \mathcal{P}_4.
Note however that we only do this when it is obvious what we mean: this is very different from the product XY\mathbf{1}Z=i\mathbf{1} inside \mathcal{P}_1!
Let’s now talk a little bit about the algebraic structure of \mathcal{P}_n.
Multiplying together elements is fairly simple: since they are tensor products, we multiply them component-wise, but just remembering to pay attention to the global phase.
For example, we can multiply ZXX\mathbf{1} and XXYY in \mathcal{P}_4 as follows:
\begin{aligned}
(ZXX\mathbf{1})\cdot(XXYY)
&= (ZX)(XX)(XY)(\mathbf{1}Y)
\\&= (iY)(\mathbf{1})(iZ)(Y)
\\&= -Y\mathbf{1}ZY.
\end{aligned}
Next, any pair of elements in \mathcal{P}_n either commute or anticommute: given P=P_1\ldots P_n and Q=Q_1\ldots Q_n, we notice that they commute exactly whenever the number of anticommuting components (indices j such that P_jQ_j=-Q_jP_j) is even, since then the minus signs cancel out.
In other words, PQ=(-1)^J QP, where J=|\{j\text{ such that }P_jQ_j=-Q_jP_j\}|.
For example, if we consider two elements of \mathcal{P}_9 and write \checkmark to mean that two components commute, and ! to mean that they don’t, we can then just count to see if there are an odd or even number of ! overall, like so:
\begin{array}{ccccccccc}
Z&X&Y&X&Y&Z&X&X&Y
\\Z&X&\mathbf{1}&Z&Z&X&\mathbf{1}&Y&Z
\\\hline
\checkmark&\checkmark&\checkmark&!&!&!&\checkmark&!&!
\end{array}
and since there are 5 anticommuting components, we see that ZXYXYZXXY and ZX\mathbf{1}ZZX\mathbf{1}YZ anticommute.
Finally, the square of any element in \mathcal{P}_n is \pm\mathbf{1}.
Indeed, all the elements in the Pauli group are unitary, and each one is either Hermitian (overall phase \pm1 and squares to \mathbf{1}) or anti-Hermitian (overall phase \pm i and squares to -\mathbf{1}).
As per usual, we are only really interested in working with the Hermitian elements, and we refer to these as the Pauli operators.
An n-qubit Pauli operator is a Hermitian element of the n-qubit Pauli group \mathcal{P}_n.
Not only do n-qubit Pauli operators have eigenvalues equal to \pm1, these eigenvalues must be of the same degeneracy, and the eigenspaces corresponding to each eigenvalue are of the same dimension, as we can see by taking the trace:
\operatorname{tr}(P_1\otimes P_2\otimes\ldots\otimes P_n) = (\operatorname{tr}P_1)(\operatorname{tr}P_2)\ldots(\operatorname{tr}P_n)
which is zero, except in the trivial case where P_1=P_2=\ldots=P_n=\mathbf{1}.
Last but not least, the n-qubit Pauli group spans the space of (2^n\times 2^n) complex matrices.