# Proof of the Universality of Toffoli and Hadamard Gates

I was trying to reproduce the result that the Toffoli gate and the Hadamard gate are universal for quantum computation as proved by Shi in "Both Toffoli and Controlled-NOT need little help to do universal quantum computation". The proof relies on Lemma 3.4 which the author says was proven by Kitaev in "Quantum computations: algorithms and error correction" (1997). Shi seems to refer to a statement at page 1214 right below Lemma 4.6 in Kitaev's paper. Kitaev however does not give a proof but literally says

"Now we shall use the following geometric fact. Let $Μ$ be a unitary space of dimension $\ge 3$.We consider a subgroup $Η \subset SU(M)$ the stabilizer of a non-zero vector $|{\xi}\rangle \in M$. Let $V$ be an arbitrary unitary operator that does not preserve the subspace ($| {\xi}\rangle$). Then the set of operators $H$ union $V^{-1} H V$ generates the whole group $SU(N)$."

This seems like a standard result in group theory, but I'm really struggling to understand it and finding related literature about it. Any help in finding references or explanations is welcome. Thanks in advance.

• I don't know the Shi paper, but I know that Aharonov gives a very simple proof of this fact: arxiv.org/abs/quant-ph/0301040 – Norbert Schuch Jun 15 '18 at 12:43
• True, but Ahronov's proof also relies on this statement by Kitaev indirectly, because it assumes the universality of controlled-S gate and Hadamard, which Kitaev proves using the previous argument. Ahronov gives reference to the same paper of Kitaev as Shi. – cianibegood Jun 15 '18 at 14:27
• Ok, but then your question really isn't about the proof of universality for this specific gate set. – Norbert Schuch Jun 15 '18 at 15:15
• Indirectly (like Ahronov), my question is also a question about the universality of controlled-S and Hadamard, since all proofs rely on this statement by Kitaev. I can "geometrically" understand with some examples that the above fact should work for SO(3), but I don't know how to generalize it. – cianibegood Jun 15 '18 at 15:58
• Your question is about the fact used to prove universality. It should be common to pretty much any universality proof. – Norbert Schuch Jun 15 '18 at 20:20

This may not be the answer you're looking for, but it is related.

Assuming you're allowed a constant number of ancillae in a specified state, you can catalyze T gates out of Toffolis:

Given those four catalyst states, Hadamard+Toffoli is universal because it can synthesize Hadamard+T+CNOT (which is universal).

Note that it is important that the circuit not consume the catalyst states. This is what distinguishes Toffoli+H from the Clifford gate set (which can synthesize T gates only by consuming the magic states).

• This has nothing to do with the question. Also, if you have the right ancillas, you can get T gates using only stabilizers, no need for universal gates. – Norbert Schuch Jun 15 '18 at 20:15
• @NorbertSchuch As I stated in my answer, stabilizer circuits need a continuous supply of magic states. This is very different from the circuit I showed, where the same four states can be used and reused indefinitely. – Craig Gidney Jun 15 '18 at 22:55