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?)
7
-
$\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 VeselyFeb 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$– Norbert SchuchFeb 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$– Martin VeselyFeb 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$– Norbert SchuchFeb 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$– Martin VeselyFeb 16, 2020 at 17:32
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
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).
$\begingroup$
$\endgroup$
1
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$– WolfLinkJun 2, 2020 at 1:19