How to make Toffoli gate using matrix form in multi qubits system?

Question

I wonder that there is generalized form to make Toffoli gate in multi-qubits system even if the two control qubits and one target qubit are not adjacent. In Wikipedia there is one way to make Toffoli gate with Hadamard, T gate and CNOTs, but I want to know how to make it for any case (i.e generalized version).

Stefano · Accepted Answer

The matrix form of a Toffoli gate with control qubits $q_a$ and $q_b$ and a target qubit $q_x$ applied on a $n$-sized qubit register may be described as
$$
T = left[ begin{array}{ccccc} 
t_{1,1} &  & cdots & & t_{1,2^n}
 & ddots & & 
vdots & & t_{i,j} & &  vdots 
& & & ddots & 
t_{2^n,1} & & cdots & &  t_{2^n,2^n} 
end{array} right]
$$
with $t_{i,j} in left { 0,1 right }$ defined by
$$
t_{i,j} = left { begin{array}{rlcl}
  1  & mbox{if } (i-1) land M neq M & { and } & j = i 
1  & mbox{if } (i-1) land M = M & { and } & j = delta_i + i 
 0  & mbox{otherwise}
end{array} right. 
$$
where $land$ represents the bitwise AND operator, $M = 2^{n-a} + 2^{n-b}$ and
$$
delta_i = left { begin{array}{rl}
 (2^{n-x})  & mbox{if } 2^{n-x} land (i-1) = 0  
-(2^{n-x})  & mbox{otherwise}
end{array} right. 
$$
The matrix $T$ is an identiy matrix with some rows/cols switched to implement the controlled NOT gate: $M$ represents the mask used to identify the rows to be remapped and $delta_i$ represents the shift applied to remap them.
I have prepared a short pyhton code snippet to calulate $T$
import numpy as np
def T(n,a,b,x) :
    m = 2**(n-a)+2**(n-b)
    d = lambda i : 2**(n-x) if (2**(n-x)) & i == 0 else -(2**(n-x))
    T = np.array([([0] * 2**n)] * 2**n)
    for i in range(2**n) :
        for j in range(2**n) :
            T[i][j] = 1 if (i & m == m and j == d(i) + i) or (i & m != m and j == i) else 0
    return T

For example, the Toffoli matrix T(4,3,2,1) is
array([[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
       [0, 0, 0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
       [0, 0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]])

vasjain · Answer

My understanding of the OP's question is that there is some restriction imposed that a gates can only act on Adjacent Qubits. While this isn't necessary, we can still work with this restriction using SWAP gates to make non-adjacent qubit adjacent.
If the Control qubits are $i$ and $j$; and target qubit is $k$. Such that $i+1<j$ and $j+1<k$. Then we can use SWAP gates to bring these qubits closer.
If there is a distance between $i$ and $j$ i.e $j-i-1>0$, then we can use $j-i-1$ SWAP gates to bring the states of these qubits closer and apply the gate. Then another $j-i-1$ SWAP gate can be used to transfer the state back to its original position. This system is described for 2 qubits but can work for 3 qubits in case of a Toffoli Gate.
Example: We have 7 qubits $q_i$, $iin {0,1,2,3,4,5,6}$. We need to apply a $Toffoli$ Gate to $q_5$ with $q_0$ and $q_3$ as control.
Then the original state of the system is $q_0q_1q_2q_3q_4q_5q_6$.
We can apply the $CCNOT$ gate as follows

We apply SWAP gate to $q_0$ and $q_1$ resulting in state $q_1q_0q_2q_3q_4q_5q_6$.
We apply SWAP gate to $q_0$ and $q_2$ resulting in state $q_1q_2q_0q_3q_4q_5q_6$.
We apply SWAP gate to $q_4$ and $q_5$ resulting in state $q_1q_2q_0q_3q_5q_4q_6$.
We apply CCNOT gate on $q_0,q_3,q_5$ and now $q_5 rightarrow q_5' $ resulting in state $q_1q_2q_0q_3q_5'q_4q_6$.
We apply SWAP gate to $q_5'$ and $q_4$ resulting in state $q_1q_2q_0q_3q_4q_5'q_6$.
We apply SWAP gate to $q_0$ and $q_2$ resulting in state $q_1q_0q_2q_3q_4q_5'q_6$.
We apply SWAP gate to $q_0$ and $q_1$ resulting in state $q_0q_1q_2q_3q_4q_5'q_6$.

In this manner you can apply $CCNOT$ gate to non-adjacent qubits using $SWAP$ gates.
Note: Just to be clear SWAP gates do not switch qubits but they are unitaries whose effect is that the state of the 2 qubits is swapped.
To know more about SWAP Gates see this

How to make Toffoli gate using matrix form in multi qubits system?

2 Answers

Add your own answers!

Ask a Question