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.

  • $\begingroup$ 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 $\endgroup$ Commented Jun 15, 2018 at 12:43
  • $\begingroup$ 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. $\endgroup$ Commented Jun 15, 2018 at 14:27
  • $\begingroup$ Ok, but then your question really isn't about the proof of universality for this specific gate set. $\endgroup$ Commented Jun 15, 2018 at 15:15
  • $\begingroup$ 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. $\endgroup$ Commented Jun 15, 2018 at 15:58
  • 1
    $\begingroup$ you may also try to ask this question (or a related one) on quantumcomputing.SE if you don't get satisfying answers here $\endgroup$
    – glS
    Commented Jul 5, 2018 at 9:24

1 Answer 1


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:

Tof plus resource to T

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

  • $\begingroup$ 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. $\endgroup$ Commented Jun 15, 2018 at 20:15
  • $\begingroup$ @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. $\endgroup$ Commented Jun 15, 2018 at 22:55

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.