2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ "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? $\endgroup$ – Norbert Schuch Dec 27 '19 at 20:54
  • $\begingroup$ @NorbertSchuch: I meant if is it possible to implement it with less gates (CNOTs and rotations) behind Toffoli gates. $\endgroup$ – Martin Vesely Dec 27 '19 at 20:56
  • $\begingroup$ I still don't understand. What is your figure of merit? E.g., you can get Fredkin with one Toffoli + 2 CNOTs. $\endgroup$ – Norbert Schuch Dec 27 '19 at 20:57
  • $\begingroup$ @NorbertSchuch: It was answer to your question in terms of what. I will have a look at the paper you sent me. Thanks. $\endgroup$ – Martin Vesely Dec 27 '19 at 21:02
  • $\begingroup$ 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? $\endgroup$ – Norbert Schuch Dec 27 '19 at 21:11
1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Norbert Schuch Dec 27 '19 at 23:27
  • 1
    $\begingroup$ @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. $\endgroup$ – Martin Vesely Dec 28 '19 at 7:50
  • $\begingroup$ Just note that design of Fredkin gate is an excercise no. 4.25 on pg. 182 in Nielsen and Chuang. $\endgroup$ – Martin Vesely Dec 29 '19 at 20:39

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.