7

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:

Swap gate

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

Fredking gate

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

matrix of Toffoli gate controlled by qubits $|q_0\rangle$ and $|q_2\rangle$ is \begin{equation} 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} \end{equation}

and finnaly, matrix of Fredking gate is \begin{equation} 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} \end{equation}

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?

glS
  • 24,708
  • 5
  • 34
  • 108
Martin Vesely
  • 13,891
  • 4
  • 28
  • 65

1 Answers1

7

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:

Fredkin Gate

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

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

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

Martin Vesely
  • 13,891
  • 4
  • 28
  • 65
  • 2
    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
  • 1
    @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 07: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