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

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

• Can you specify what you mean by a generalised way? Aug 2, 2020 at 12:49
• If control qubits are 1st,2nd and target qubit is 4th then how I can make toffoli gate in matrix form?
– 김동민
Aug 2, 2020 at 12:51
• are you asking how to find the matrix representation of a Toffoli between an arbitrary triple of qubits, or something else?
– glS
Aug 3, 2020 at 12:19

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


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 and $$j+1. 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