On current quantum hardware, a depth of circuit is constrained because of noise. In some cases, results are totally decoherent and as a result meaningless. This is especially true when Toffoli gates are used. Moreover, when it is necessary to use multiple inputs Toffoli gate (i.e. with three or more inputs), one has to use ancilla qubit(s) which has to be uncomputed eventually. This increases complexity of a circuits further.

So my questions are these:

  1. Is it possible to implement two inputs Toffoli gate in simpler way than for example on IBM Q?
  2. How to implement Toffoli gate with three or more inputs without building it up from two inputs Toffoli gates and using ancilla qubits?

1 Answer 1


It is possible to employ a method presented in Transformation of quantum states using uniformly controlled rotations. The article shows (besides) how to implement gate controlled by $n$ qubits and yielding a state

$$ |\psi\rangle_{n+1} = |i\rangle_{n}\Big(\sqrt{1-f(i)}|0\rangle + \sqrt{f(i)}|1\rangle\Big), $$

where $i$ is a binary representation of $n$ bits number and $f(i)$ is an arbitrary function. Setting function $f(i) = 1$ for $|i\rangle = |1 \dots1\rangle$ and $f(i) = 0$ otherwise allows to construct Toffoli gate with as many input qubits as one wants without ancilla qubits. Note however, that increase in number of gates is exponential in number of input qubits. For $n$ input qubits $2^n$ $CNOT$s and $Ry$ rotations is used.

However, in comparison with complexity of circuits used for implementation of Toffoli gate on IBM Q, the circuit is simpler. In case of two qubits, four $CNOT$s and four $Ry$ gates are used (note that after transpiling the circuit on IBM Q, $Ry$ are replaced by $U3$ gates).

A implementation of Toffoli gate with above mentioned method is this:

2 input Toffoli

Note: Parameter $\theta$ is set to $\pm\frac{\pi}{4}$.

I tested the new gate "abilities" on input $|11\rangle$. Backend ibmqx2 was used, number of shots was set to 8,192. The circuit was designed to follow the backend physical implementation and hence to avoid qubits swaps after transpiling. A probability of measuring $|1\rangle$ was 93.286 %, while the same probability with Toffoli implemented on IBM Q was 87.486 %. Clearly, simpler circuits helped to get a more coherent results.

The method also allows to implement Toffoli gate with three inputs:

3 inputs Toffoli

Note: Parameter $\theta$ is set to $\pm\frac{\pi}{8}$.

I again tested the circuit on ibmqx2 with same setting as above and compared it with Toffoli gate on IBM Q (here I had to use ancilla qubit and three two input Toffoli gates - one for uncomputing the ancilla). Input of circuit was $|111\rangle$. A probability of measuring $|1\rangle$ was 81.213 %, while the probability with Toffoli implemented on IBM Q was 30.542 %. This means that output of construction with two inputs Toffoli gate and one ancilla qubit is very decoherent.

EDIT: based on DaftWullie comment.

Actually above introduced simplification of a Toffoli gate can be used only in case qubit $q_2$ (or $q_3$ in case of three inputs) is set to $|0\rangle$, i.e. the gate operate as AND known from classical Boolean logic. The reason is that a matrix describing circuit above is

$$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ \end{pmatrix} $$

This means that for input $|111\rangle$ a phase is shifted by $\pi$.

As a result, the circuit is not "general Toffoli" and can be used only in special cases where it is ensured that the "last" qubit is set to $|0\rangle$

  • 2
    $\begingroup$ IIRC, the circuit you gave as a different composition of Toffoli is NOT Toffoli. I believe it appears in Nielsen and Chuang and is similar to Toffoli but has different phases. There are places where you’re better off using it but you cannot just substitute one for the other arbitrarily. $\endgroup$
    – DaftWullie
    Commented Feb 14, 2020 at 6:55
  • $\begingroup$ @DaftWullie: Thanks for pointing this out, it is true that I checked proper work from point of classical Boolean logic. I have to do so again on arbitrary superposition of two input qubits. $\endgroup$ Commented Feb 14, 2020 at 7:25
  • 1
    $\begingroup$ Even when you compute the effect just on the basis states, you should be able to see different phases coming out (even if you might later choose to neglect them as global phases). I believe it is proven that the standard decomposition of Toffoli is optimal in terms of, for example, c-NOT gate counts and T-gate counts. $\endgroup$
    – DaftWullie
    Commented Feb 14, 2020 at 8:57
  • $\begingroup$ What about k-CNOT? $\endgroup$ Commented Feb 21, 2023 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.