A CCCNOT gate is a four-bit reversible gate that flips its fourth bit if and only if the first three bits are all in the state $1$.

How would I implement a CCCNOT gate using Toffoli gates? Assume that bits in the workspace start with a particular value, either 0 or 1, provided you return them to that value.

  • $\begingroup$ Using only Toffoli gates, or Toffoli and CNOT are fair game? $\endgroup$ – user1271772 Jun 19 '18 at 17:59
  • $\begingroup$ Only Toffoli gates are allowed. $\endgroup$ – chuster Jun 19 '18 at 18:09
  • 1
    $\begingroup$ What part of this question is quantum? It seems you want to decompose a classical reversible gate (CCCNOT) into smaller classical reversible gates (CCNOTs). $\endgroup$ – user1271772 Jun 19 '18 at 18:35
  • 1
    $\begingroup$ The question itself doesn't pertain to quantum computing, but the gates are important to quantum circuitry. $\endgroup$ – chuster Jun 19 '18 at 18:51

I guess what you're looking for is the following circuit. Here, $b_1,b_2,b_3,b_4 \in \{0,1\}$, and $\oplus$ is addition modulo $2$.

enter image description here

Here, the fifth qubit is used as an auxiliary, or ancilla qubit. It starts at $|0\rangle$ and ends in $|0\rangle$ when the circuit is applied.

Let me elaborate on how this circuit works. The idea is to first of all check whether the first two qubits are in state $|1\rangle$. This can be done using a single Toffoli gate, and the result is stored in the auxiliary qubit. Now, the problem reduces to flipping qubit $4$, whenever qubits $3$ and the auxiliary qubit are in $|1\rangle$. This can also be achieved using one application of a Toffoli gate, namely the middle one in the circuit shown above. Finally, the last Toffoli gate serves to uncompute the temporary result that we stored in the auxiliary qubit, such that the state of this qubit returns to $|0\rangle$ after the circuit is applied.

In the comment section, the question arose whether it is possible to implement such a circuit using only Toffoli gates, without using auxiliary qubits. This question can be answered in the negative, as I will show here.

We want to implement the $CCCNOT$-gate, which acts on four qubits. We can define the following matrix (the matrix representation of the Pauli-$X$-gate): $$X = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$$ Furthermore, we denote the $N$-dimensional identity matrix by $I_N$. Now, we observe that the matrix representation of the $CCCNOT$-gate, acting on four qubits, is given by the following $16 \times 16$ matrix: $$CCCNOT = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ Hence, we can determine its determinant: $$\det(CCCNOT) = -1$$ Now consider the matrix representation of the Toffoli gate, acting on the first three qubits of a $4$-qubit system. Its matrix representation is written as (where we used the Kronecker product of matrices): $$Toffoli \otimes I_2 = \begin{bmatrix} I_6 & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{12} & 0 \\ 0 & X \otimes I_2 \end{bmatrix} = \begin{bmatrix} I_{12} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ Calculating its determinant yields: $$\det(Toffoli \otimes I_2) = 1$$ The Toffoli gates can also act on different qubits of course. Suppose we let the Toffoli gate act on the first, second and fourth qubit, where the fourth qubit is the target qubit. Then we obtain the new matrix representation from the one displayed above by swapping the columns corresponding to the states that differ only in the third and fourth qubit, i.e., $|0001\rangle$ with $|0010\rangle$, $|0101\rangle$ with $|0110\rangle$, etc. The important thing to note here, is that the number of swaps of columns is even, and hence that the determinant remains unchanged. As we can write every permutation of qubits as a sequence of consecutive permutations of just $2$ qubits (that is, $S_4$ is generated by the transpositions in $S_4$), we find that for all Toffoli gates, applied to any combination of control and target qubits, its matrix representation has determinant $1$.

The final thing to note is that the determinant commutes with matrix multiplication, i.e., $\det(AB) = \det(A)\det(B)$, for any two matrices $A$ and $B$ compatible with matrix multiplication. Hence, it now becomes apparent that applying multiple Toffoli gates in sequence never creates a circuit whose matrix representation has a determinant different from $1$, which in particular implies that the $CCCNOT$-gate cannot be implemented using only Toffoli gates on $4$ qubits.

The obvious question, now, is what changes when we do allow an auxiliary qubit. We find the answer when we write out the action of the $CCCNOT$-gate on a $5$-qubit system: $$CCCNOT \otimes I_2 = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix} \otimes I_2 = \begin{bmatrix} I_{28} & 0 & 0 \\ 0 & 0 & I_2 \\ 0 & I_2 & 0 \end{bmatrix}$$ If we calculate this determinant, we find: $$\det(CCCNOT \otimes I_2) = 1$$ Hence, the determinant of the $CCCNOT$-gate acting on $5$ qubits is $1$, instead of $-1$. This is why the previous argument is not valid for $5$ qubits, as we already knew because of the explicitly constructed circuit the OP asked for.

  • 1
    $\begingroup$ a source, or method used to derive the circuit, would be useful! $\endgroup$ – glS Jun 19 '18 at 19:43
  • 1
    $\begingroup$ I know of no sources that explain how to design such circuits in a comprehensive manner. The sources I used when learning about quantum computing were the book by Nielsen and Chuang, and the lecture notes that can be found here: homepages.cwi.nl/~rdewolf/qcnotes.pdf, but these sources do not specifically focus on the design of quantum circuits. $\endgroup$ – arriopolis Jun 19 '18 at 19:47
  • 2
    $\begingroup$ I did try to elaborate on how the circuit works a little more. Hope this helps in designing circuits similar to this one! :) $\endgroup$ – arriopolis Jun 19 '18 at 19:55
  • $\begingroup$ Is it possible without auxiliaries? $\endgroup$ – user1271772 Jun 19 '18 at 20:21
  • 1
    $\begingroup$ Interesting question, but I don't think so. Whenever one writes out the matrix representation of a Toffoli gate acting on a four qubit system, the determinant of this matrix is $+1$. However, the determinant of the matrix representation of the $CCCNOT$-gate acting on $4$ qubits is $-1$, so it cannot be constructed by consecutive applications of the Toffoli gate. With this auxiliary qubit, the difference is that the matrix representation of the $CCCNOT$-gate becomes $+1$. $\endgroup$ – arriopolis Jun 19 '18 at 20:31

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.