We know if we don't use auxiliary, the construction of Toffoli gate will be:

3 qubit construction of Toffoli

However, if now you are allowed to use one auxiliary qubit, how to realize a CCNOT in a simplier way? (Can we only use X,Y,Z,H and CNOT?)

  • $\begingroup$ Here you can see simpler implementation of Toffoli without ancillas: quantumcomputing.stackexchange.com/questions/9842/… Hope, it can be interesting for you as well. $\endgroup$ Feb 13, 2020 at 11:22
  • 1
    $\begingroup$ One problem with you question is that you don't specific what you mean by "simpler way": If I need less CNOTs but more T gates, is that better? Or is less T gates and more CNOTs better? What is your cost function? Without that, it is impossible to answer. $\endgroup$ Feb 15, 2020 at 11:49
  • $\begingroup$ @NorbertSchuch: It probably means: Is there any way how to reduce number of gates by employing ancillas? Since it is known that you can reduce depth of a circuit but only at cost of increasing number of ancilla qubits. $\endgroup$ Feb 16, 2020 at 11:52
  • $\begingroup$ @MartinVesely Reduce indiscriminately? Which gates are allowed? Can I use CCZ gates? And since you gave a bounty: What kind of answer are you looking for? $\endgroup$ Feb 16, 2020 at 13:14
  • $\begingroup$ @NorbertSchuch: I am interested in any possible solution of the problem. Regarding CCZ gates, it can be constructed with Toffoli, am I right or is there any other possibility (again with ancilla)? $\endgroup$ Feb 16, 2020 at 17:32

2 Answers 2


To give an answer to part of your question:

Can we only use X,Y,Z,H and CNOT?

No. The gates you mention are stabilizer gates. On the other hand, the Toffoli is not a stablizer gate. (In fact, Toffoli and Hadamard together are universal.) Thus, it is impossible to build the Toffoli with only stabilizer gates (and thus only the gates you mention).


To give another partial answer - considering only the CNOT cost (I agree that one needs to define a cost to answer this question, and CNOT cost is probably one of the most relevant, theoretically and practically): No matter how many ancillas you add, as long as CNOT is your only two-qubit gate, you cannot do better than the original circuit. This is Theorem 1 in Shende and Markov 08:

A circuit consisting of CNOT gates and one-qubit gates which implements the n-qubit TOFFOLI gate without ancillae requires at least 2n CNOT gates. For n = 3, this bound holds even when ancillae are permitted, and is achieved by the circuit of Figure 1

Where Figure 1 is just the circuit in the original question

  • $\begingroup$ Note that mapping of the circuit to the less-connected topology can complicate the matter $\endgroup$
    – WolfLink
    Jun 2, 2020 at 1:19

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.