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).

Answer 1

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]])

Answer 2

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$, $i\in \{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

1. We apply SWAP gate to $q_0$ and $q_1$ resulting in state $q_1q_0q_2q_3q_4q_5q_6$.
2. We apply SWAP gate to $q_0$ and $q_2$ resulting in state $q_1q_2q_0q_3q_4q_5q_6$.
3. We apply SWAP gate to $q_4$ and $q_5$ resulting in state $q_1q_2q_0q_3q_5q_4q_6$.
4. 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$.
5. We apply SWAP gate to $q_5'$ and $q_4$ resulting in state $q_1q_2q_0q_3q_4q_5'q_6$.
6. We apply SWAP gate to $q_0$ and $q_2$ resulting in state $q_1q_0q_2q_3q_4q_5'q_6$.
7. 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