# The Heisenberg Representation of Quantum Computers

This is a review notes for the paper Gottesman, D. (1998). *The Heisenberg representation of quantum computers*. arXiv preprint quant-ph/9807006.

## Heisenberg Representation
Suppose we have a quantum computer in the state $|\psi\rangle$, and we apply the operator $U$. Note
$$
U N |\psi\rangle = UNU^\dagger U |\psi\rangle
$$
The key idea of Heisenberg Representation is not changing the state $|\psi\rangle$ but the operator. In this case, $U$ transforms an arbitary operator $N$ by
$$
N \longrightarrow UNU^\dagger \;\;\;\; \textrm{(conjugate transformation)}
$$
Futhermore, this is a multiplicative group *homomorphism*:
$$
MN \longrightarrow (UMU^\dagger) (UNU^\dagger)
$$
A common set is *Pauli group* $\mathcal{P}_n$, which consists of $4\cdot 4^n$ elements:
$$
\begin{eqnarray}
\mathcal{P}_n = \left\{e^{i\theta\pi/2} \sigma_{j_1}\otimes \ldots\otimes \sigma_{j_n} | \theta = 0, 1, 2, 3 ,\; j_k = 0, 1, 2, 3\right\}
\end{eqnarray}
$$

## The Clifford Group

The definition of Clifford group $\mathcal{C}$ is the set of operators which leave *Pauli Group* $\mathcal{P}$ fixed under conjugate. It is the *normalizer* of $\mathcal{P}$ in $U(2^n)$. Recall the normalizer in group theorem means
$$
N_{U(2^n)}(P) = \{g \in U(2^n) \,|\, gPg^{-1} = P \}
$$
Three common clifford gates are phase gate $S$, Hadmard gate $H$, and controlled-NOT gate $CNOT$ or $CX$. In fact, $S$, $H$, and $CNOT$, applied to arbitrary qubits or pairs of qubits, generate the full Clifford group $\mathcal{C}$ .

## Applying the Heisenberg Representation

It is easy to that Clifford gate fits to the Heisenberg Representation perfertly due to the normalizer property. Since all Clifford gates can be generated by $H, S, CNOT$ and the Pauli Gates can be generated by $X_i, Z_i$, all transformation we need to know, threoratically, are just:
$$
\begin{eqnarray}
HXH^\dagger \longrightarrow Z,&\quad& HZH^\dagger \longrightarrow X, \\
SXS^\dagger \longrightarrow Y,&\quad& SZS^\dagger \longrightarrow Z, \\
CNOT_{1,2} (X\otimes I) CNOT_{1,2}^\dagger &\longrightarrow& X\otimes X\\
CNOT_{1,2} (I\otimes X) CNOT_{1,2}^\dagger &\longrightarrow& I\otimes X\\
CNOT_{1,2} (Z\otimes I) CNOT_{1,2}^\dagger &\longrightarrow& Z\otimes I\\
CNOT_{1,2} (I\otimes Z) CNOT_{1,2}^\dagger &\longrightarrow& Z\otimes Z\\
\end{eqnarray}
$$

## Stabilizers
The last piece is the stabilizers. Consider the set of operators in $\mathcal{P}$ for which the input states are $+1$ eigenvectors. The set of such operators is closer under the multiplication, and therefore forms a group, known as the *stabilizer* $S$ :
$$
S = \{M\in \mathcal{P} \textrm{ such that } M|\psi\rangle = |\psi\rangle\; \textrm{for all allowed inputs } |\psi\rangle\}
$$
The stabilizer is always an Abelian group: If $M, N \in S$, then
$$
MN |\psi\rangle = |\psi\rangle,\; NM |\psi\rangle = |\psi\rangle,\; [M, N] |\psi\rangle = 0
$$

## Putting everything together
Now, we can combine all above concepts together. Suppose $|\psi\rangle$ is a stabilizer states, we have
$$
U |\psi\rangle = U M |\psi\rangle = U M U^\dagger U|\psi\rangle
$$
where $M$ is some pauli string is the stabilizer group, and $U$ is operator in the Clifford group. Notice that a) $U M U^\dagger$ is still some elements, i.e. pauli string, in the pauli group. b) The state after the operator $U |\psi\rangle$ is the eigenvector of new $U M U^\dagger$.

A state can be uniformly determined by the stabilizers. Hence, knowing the transformation of all generators of $\mathcal{S}$ under $U$ is equivalent to the computing of $U|\psi\rangle$.