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?


1 Answer 1


Note that it's talking about simulation, not actually performing something like a Hadamard. In is not saying that you could just replace Hadamards in a circuit with controlled-nots.

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).

  • 1
    $\begingroup$ Ah so it's a classical CNOT acting on the representation of the quantum states. Gotcha, thanks! $\endgroup$ Jan 30 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.