# How can I implement an n-bit Toffoli gate?

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

• Thanks for the Q&A. Good to see you here Ali! – James Wootton May 29 '18 at 7:57

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:

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 this case, one wants that $$V^2=X$$, and hence $$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 qubit gate is defined in terms of the control n-1 qubit 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.

• Has anyone worked on implementing this gate on Cirq? – Enrique Segura Jun 22 '19 at 1:25

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)

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 ├
└───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘└───┘       └───┘└───┘        └───┘