7
$\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$
6
  • 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$ Dec 27, 2019 at 20:54
  • $\begingroup$ @NorbertSchuch: I meant if is it possible to implement it with less gates (CNOTs and rotations) behind Toffoli gates. $\endgroup$ Dec 27, 2019 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$ Dec 27, 2019 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$ Dec 27, 2019 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$ Dec 27, 2019 at 21:11

1 Answer 1

7
$\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$
3
  • 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$ Dec 27, 2019 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$ Dec 28, 2019 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$ Dec 29, 2019 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.