If an auxiliary qubit is allowed, how to construct toffoli gate in easier way?

Question

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

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

Answer 1

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

Answer 2

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