I was trying to find a reference for the 7 T-gate decomposition of the Toffoli gate given by Cirq. The decomposition originates from the the one used for CCZPowGate as given in the doc string here


This is mentioned as an adjacency respecting decomposition by which I understand that the CNOTs are nearest neighbour

Most of the literature I have seen on Toffoli gate decompositions seem to use long range CNOTs for example in Neilson and Chuang or here

https://arxiv.org/abs/2101.04764 .

Does anyone have an idea about the source of the decomposition used?


1 Answer 1


I'm the one who added this code to Cirq. I found that decomposition as part self-answering a question from 2018. I found it by messing around in Quirk, trying different strategies.

Norbert Schuch has a comment on the answer saying the decomposition appears in his thesis in 2002. I wasn't able to get his thesis to check as the link he gave is dead now, but I don't doubt he also found it or that the original discovery predates mine by more than a decade.

  • $\begingroup$ Thanks Craig, that is very helpful! $\endgroup$ Commented Jul 29, 2022 at 2:07

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.