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$ – Norbert Schuch Jun 15 '18 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$ – cianibegood Jun 15 '18 at 14:27
  • $\begingroup$ Ok, but then your question really isn't about the proof of universality for this specific gate set. $\endgroup$ – Norbert Schuch Jun 15 '18 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$ – cianibegood Jun 15 '18 at 15:58
  • $\begingroup$ Your question is about the fact used to prove universality. It should be common to pretty much any universality proof. $\endgroup$ – 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:

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$ – Norbert Schuch Jun 15 '18 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$ – Craig Gidney Jun 15 '18 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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