# How to implement a Fredkin gate using Toffoli and CNOTs?

Inspired by a question Toffoli using Fredkin, I tried to do "inverse" task, i.e. to implement Fredkin gate (or controlled swap). In the end I implemented it with three Toffoli gates.

Firstly, I started with swap gate without control qubit which is implemented with CNOTs followingly:

Then I realized that I need control qubit, or in other words that I have to control each CNOT gate. As controlled CNOT is Toffoli gate (CCNOT gate), I came to this circuit

As matrix representation of Toffoli gate controlled by qubits $$|q_0\rangle$$ and $$|q_1\rangle$$ is $$$$CCNOT_{01} = \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}$$$$

matrix of Toffoli gate controlled by qubits $$|q_0\rangle$$ and $$|q_2\rangle$$ is $$$$CCNOT_{02} = \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 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{pmatrix}$$$$

and finnaly, matrix of Fredking gate is $$$$F = \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 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{pmatrix}$$$$

Since $$F=CCNOT_{01} CCNOT_{02} CCNOT_{01}$$, the circuit is designed corectly.

Unfortunatelly, implementation of Toffoli gate requires many CNOT gates and single qubit rotation gates.

My question: Is this implementation of Fredkin gate the most efficient one?

• "My question: Is this implementation of Fredkin gate the most efficient one?" -- Most efficient in terms of what? Toffoli gates? Two-qubit gates? Sth. else? Have you e.g. checked out Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate? – Norbert Schuch Dec 27 '19 at 20:54
• @NorbertSchuch: I meant if is it possible to implement it with less gates (CNOTs and rotations) behind Toffoli gates. – Martin Vesely Dec 27 '19 at 20:56
• I still don't understand. What is your figure of merit? E.g., you can get Fredkin with one Toffoli + 2 CNOTs. – Norbert Schuch Dec 27 '19 at 20:57
• @NorbertSchuch: It was answer to your question in terms of what. I will have a look at the paper you sent me. Thanks. – Martin Vesely Dec 27 '19 at 21:02
• Yes, and I could not properly understand your question. Are you trying to minimize the number of Toffoli gates, or the number of CNOTs and rotations in addition to a given number of Toffoli gates? – Norbert Schuch Dec 27 '19 at 21:11

Based on paper Five Two-Bit Quantum Gates are Sucient to Implement the Quantum Fredkin Gate provided by Norbert Schuch, I realized that there is a more efficient implementation in terms of number of gates. Here is a result:

Matrix of CNOT acting on $$|q_1\rangle$$ controlled by $$|q_2\rangle$$ is

$$$$CNOT_{2}= \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0\\ \end{pmatrix}$$$$

It can be verified that $$(I \otimes CNOT_2)CCNOT(I \otimes CNOT_2)$$ is matrix describing Fredkin gate.

• What is noteworthy is that your question contains all the ingredients for this answer! (Basically, once you understand that two CNOTs are a SWAP + a CNOT, you're there. All the rest is just putting a control on that. – Norbert Schuch Dec 27 '19 at 23:27
• @NorbertSchuch: I see, thanks. It is enough to control only the middle CNOT. In case $|q_0\rangle$ is $|0\rangle$, left and right CNOT cancel each other as Toffoli is in this case just $I$. Only in case $|q_0\rangle$ is $|1\rangle$ the middle CNOT works and all three gates implement swap gate. – Martin Vesely Dec 28 '19 at 7:50
• Just note that design of Fredkin gate is an excercise no. 4.25 on pg. 182 in Nielsen and Chuang. – Martin Vesely Dec 29 '19 at 20:39