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
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.
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$.
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 $\mathrm{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 $\mathrm{CCCNOT}$-gate, acting on four qubits, is given by the following $16 \times 16$ matrix: $$\mathrm{CCCNOT} = \begin{bmatrix} I_{14} & 0 \\ 0 & X \end{bmatrix}$$ Hence, we can determine its determinant: $$\det(\mathrm{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): $$\mathrm{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(\mathrm{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 $\mathrm{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 $\mathrm{CCCNOT}$-gate on a $5$-qubit system: $$\mathrm{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(\mathrm{CCCNOT} \otimes I_2) = 1$$ Hence, the determinant of the $\mathrm{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.
