3
$\begingroup$

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

$\endgroup$
  • $\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$ – Martin Vesely Feb 13 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$ – Norbert Schuch Feb 15 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$ – Martin Vesely Feb 16 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$ – Norbert Schuch Feb 16 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$ – Martin Vesely Feb 16 at 17:32
6
$\begingroup$

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

|improve this answer|||||
$\endgroup$
3
+50
$\begingroup$

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

|improve this answer|||||
$\endgroup$

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.