The Exercise

Take a register of $n$ qubits and a unitary gate $U$ that, under conjugation, sends every Pauli operator on the register, phase included, to a Pauli operator. The exercise is to build $U$, up to a global phase, from Hadamard gates, phase gates and controlled NOT (CNOT) gates, with a number of gates of order $n^2$. On a single qubit, Hadamard and phase gates are enough.

The library states both claims.

The Pauli Group

The Pauli matrices $\sigma_0, \sigma_1, \sigma_2, \sigma_3$ are the four complex $2 \times 2$ matrices, with rows and columns indexed by $\{0,1\}$, given by the identity and the matrices $X$, $Y$ and $Z$: $$\sigma_0 = I, \qquad \sigma_1 = X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \qquad \sigma_2 = Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \qquad \sigma_3 = Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}.$$(1)^✦

For a choice $a = (a_1, \dots, a_n) \in \{0,1,2,3\}^n$ of one Pauli matrix per qubit, the Pauli string $\sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n}$ is the operator on the $n$ qubits whose matrix, with rows and columns indexed by bit strings $x, y \in \{0,1\}^n$, has the entries $$(\sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n})_{xy} = \prod_{k=1}^{n} (\sigma_{a_k})_{x_k y_k}.$$(2)^✦

The Pauli group $G_n$ on $n$ qubits consists of the operators $$g = i^s \, \sigma_{a_1} \otimes \cdots \otimes \sigma_{a_n},$$(3)^✦ each fixed by its phase power $s$, an integer modulo $4$, and its Pauli string $a$. The phase $i^s$ is $i$ raised to the representative of $s$ in $\{0,1,2,3\}$, one of the four fourth roots of unity.^✦

The Pauli normalizer $N(G_n)$ is the set of unitary $2^n \times 2^n$ matrices $U$ on the $n$ qubits such that for every $g \in G_n$ there is a $g' \in G_n$ with $$U g U^\dagger = g'.$$(4)^✦

Clifford Circuits

An elementary Clifford gate on a register of $n$ qubits, whose wires $1, \dots, n$ carry the qubits one each, is a Hadamard gate $H$ on a wire $j$, a phase gate $S$ on a wire $j$, or a CNOT with control wire $c$ and target wire $t$ distinct from $c$.^✦ The matrix of a Hadamard or phase gate acts as $H$ or $S$ on qubit $j$, that of a CNOT acts as CNOT on qubits $c$ and $t$, and each acts as the identity on the remaining qubits.^✦

A Clifford circuit $\gamma$ on the register is a finite sequence $\gamma_1, \dots, \gamma_m$ of elementary Clifford gates, of length $|\gamma| = m$.^✦ Its matrix $U_\gamma$ is the product of the matrices of its gates, the last gate acting first: $$U_\gamma = U_{\gamma_1} U_{\gamma_2} \cdots U_{\gamma_m}.$$(5)

The Claim

What Is Checked

Both theorems are stated over the Pauli normalizer (4), built on the Pauli group (3) and the Pauli matrices (1), and over the matrix (5) of a circuit of Hadamard, phase and CNOT gates together with its length.