# Simulate an arbitrary stablizer circuit with only CNOT gates

It is claimed that

Informally, this means that any stabilizer circuit can be simulated using CNOT gates alone; the availability of Hadamard and phase gates provides at most a polynomial advantage.

How does one obtain, say a Hadamard gate or phase gate, using only CNOTs?

For example, the simulation of a Clifford circuit on $$n$$ qubits usually involves writing down stabilizers, represented as binary strings of length $$2n$$. If you have $$m$$ such stabilizers, you'll put it all in an $$m\times 2n$$ matrix. A Hadamard operation just represents exchanging $$X$$ and $$Z$$ which, in this matrix-based representation, just means swapping two columns. But a swap operation can be broken down into three controlled-nots.
Similarly, think of the action of an $$S$$ gate on the Pauli matrices $$X\rightarrow Y$$, $$Z\rightarrow Z$$. As binary strings, this means $$\{1,0\}\rightarrow \{1,1\}$$ and $$\{0,1\}\rightarrow\{0,1\}$$. This is just the controlled-not acting on these strings (OK, there's a little bit of processing of phases as well, which I'm leaving out).