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?)
Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.Sign up to join this community
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