2
$\begingroup$

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

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

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]])
$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.