How can I implement an n-bit Toffoli gate?

Question

I want to create a Toffoli gate controlled by n qubits, and implement it in QISKit. Can this be done? If so, how?

Answer 1

A simple way to do this is illustrated in Figure 4.10 of Nielsen & Chuang.

Where U can be any single-qubit rotation (in this case, an X gate).

This circuit works like this: We want to apply U to the target qubit only if the AND of all control qubits is 1. A normal Toffoli gives us the AND of 2 qubits. So by chaining a few Toffolis, we can get c1.c2.c3.c4.c5, with the catch that some "work" (or ancilla) qubits have been introduced to store intermediate results. After applying the final CU, we get the final result in target. Now we can clean up the intermediate work qubits by undoing their computations, returning them to the |0> state. This model of reversible computation is known as the "compute-copy-uncompute" method, and was first proposed by Charlie Bennett in 1973.

Here is the QISKit code to construct the circuit and visualize it:

from qiskit import QuantumRegister, QuantumCircuit

n = 5  # must be >= 2

ctrl = QuantumRegister(n, 'ctrl')
anc = QuantumRegister(n-1, 'anc')
tgt = QuantumRegister(1, 'tgt')

circ = QuantumCircuit(ctrl, anc, tgt)

# compute
circ.ccx(ctrl[0], ctrl[1], anc[0])
for i in range(2, n):
    circ.ccx(ctrl[i], anc[i-2], anc[i-1])

# copy
circ.cx(anc[n-2], tgt[0])

# uncompute
for i in range(n-1, 1, -1):
    circ.ccx(ctrl[i], anc[i-2], anc[i-1])
circ.ccx(ctrl[0], ctrl[1], anc[0])    

from qiskit.tools.visualization import circuit_drawer
circuit_drawer(circ)

Yields:

Answer 2

I want to add a method that does not use ancilla qubits, but does require gates more complicated than just controlled-not. I believe this method was first presented by Barenco et. al. in this paper, Lemma 7.5:

Where $V^2=U$. In your case you are interested in a "control-n not" gate, so you need to find some $V$ such that $V^2=X$. A solution that works is $$ V = \frac{1}{2} \begin{pmatrix} 1+i & 1-i \\ 1-i & 1+i \\ \end{pmatrix} \ . $$

This is a recursive definition, so the "control-n not" gate is defined in terms of the "control n-1 not" gate. This would continue until you reach the two qubit gate CNOT.

This implementation is a little difficult, however, a simpler one exists if one does not mind collecting a relative phase (see Lemma 7.9 of the same paper).

To implement a gate such as $V$ in QISKIT, you will need to use the advanced single qubit gates.

Answer 3

Qiskit's QuantumCircuit has mct method to build multiple-control Toffoli gate with several modes: basic, basic-dirty-ancilla, advanced, noancilla. For instance Toffoli gate with 3 control qubits:

from qiskit import QuantumCircuit, QuantumRegister

controls = QuantumRegister(3, "c_qb")
target = QuantumRegister(1, "t_qb")
circuit = QuantumCircuit(controls, target)

circuit.mct(controls, target[0], None, mode='advanced')

print(circuit)

Output:

c_qb_0: |0>──────■────────■────────────────■──────────────────────────────────■──────────────────────────────────■────────────────────
                 │      ┌─┴─┐            ┌─┴─┐                                │                                  │                    
c_qb_1: |0>──────┼──────┤ X ├──────■─────┤ X ├──────■────────■────────────────┼─────────────────■────────────────┼────────────────────
                 │      └───┘      │     └───┘      │      ┌─┴─┐            ┌─┴─┐             ┌─┴─┐            ┌─┴─┐                  
c_qb_2: |0>──────┼─────────────────┼────────────────┼──────┤ X ├──────■─────┤ X ├──────■──────┤ X ├──────■─────┤ X ├──────■───────────
           ┌───┐ │-pi/4 ┌───┐┌───┐ │pi/4 ┌───┐┌───┐ │-pi/4 ├───┤┌───┐ │pi/4 ├───┤┌───┐ │-pi/4 ├───┤┌───┐ │pi/4 ├───┤┌───┐ │-pi/4 ┌───┐
t_qb_0: |0>┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├┤ H ├─■─────┤ H ├┤ H ├─■──────┤ H ├
           └───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘

Answer 4

EDIT: You can simply use mct gate: https://qiskit.org/documentation/stubs/qiskit.circuit.QuantumCircuit.mct.html

As of Qiskit 'qiskit': '0.19.6', this process is much simpler. You can create your custom gate, and assign to it N amount of controlled qubits: https://qiskit.org/documentation/stubs/qiskit.circuit.ControlledGate.html

Here's an example for the N toffoli gate or cNx:

number_qubits = 10
N = number_qubits - 1

cnx_circ = QuantumCircuit(1, name="X")
cnx_circ.x(0)
cnx = cnx_circ.to_gate().control(N)

It should look something like this when applied to a circuit:

Answer 5

You can use MCXGate:

def toffoli_general(qr, control, target):
    qr.append(MCXGate(num_ctrl_qubits=len(control)), control + [target])

With for example

qr = QuantumCircuit(5)
toffoli_general(qr, [0, 1, 2, 3], 4)
qr.draw('mpl')

with qr you quantum circuit. control a list of register and control a the register number