# Which method of executing a multi-control gate is more efficient?

I am interested in executing multi-control gates and I have found two methods to do so as explained below.

1. The first is taken from Nielsen and Chuang (2010) from their Figure 4.10. This method requires an additional n-1 ancillary (or work as they call it) qubits along with $$2(n-1)$$ Toffoli gates and a single $$CU$$ gate where $$n$$ is the number of control qubits.
1. The second method from Barenco et al. (1995) (on their page 17) uses a total of $$2^{n}-1$$ $$V$$ gates and $$2^{n}-2$$ CNOT gates where $$n$$ is the number of control qubits and $$V^4=U$$ in this example. It seems to me that the Nielsen method uses fewer gates but has the disadvantage of requiring additional ancillary qubits. So which of these methods is more efficient? Or, are there other method I should consider using? In case it helps, I am looking to use one of these methods on my qiskit circuit to be run on the actual quantum hardware.

As many things in life, the answer is "it depends".

If you backend have support of Toffoli gates (that is, in Qiskit language, they are part of their basis gate set), then option 1 is better. If, like in most of the IBM backends at the moment, you only have CXs, then option 2 seems better. Let alone topology considerations like the coupling map.

If a method for decomposing a MCU is general enough, then it should be a task for the circuit compiler. The compiler should™ be smart enough for factor in all the elements (the target basis, the backend connectivity map, etc.) and give you the best decomposition (submit an issue if you think the compiler can do a better job). For example:

from qiskit import QuantumCircuit, transpile
from qiskit.circuit.library.standard_gates import C3XGate
qc = QuantumCircuit(4)
qc.append(C3XGate(), [0, 1, 2, 3])
print(qc)

q_0: ──■──
│
q_1: ──■──
│
q_2: ──■──
┌─┴─┐
q_3: ┤ X ├
└───┘


With optimization_level=3 should give you the best result, considering a ['u', 'cx'] basis:

transpiled = transpile(qc, basis_gates=['u', 'cx'], optimization_level=3)
print('depth:', transpiled.depth())
print('gates:', sum(transpiled.count_ops().values()))

depth: 35
gates: 42


If you also add a coupling map:

transpiled = transpile(qc, basis_gates=['u', 'cx'], coupling_map=[[0,1], [1,2], [2,3]], optimization_level=3)
print('depth:', transpiled.depth())
print('gates:', sum(transpiled.count_ops().values()))

depth: 79
gates: 127


If you have a concrete backend:

from qiskit import IBMQ

provider = IBMQ.get_provider(hub='ibm-q')
backend = provider.get_backend('ibmq_16_melbourne')
transpiled = transpile(qc, backend=backend, optimization_level=3)
print('depth:', transpiled.depth())
print('gates:', sum(transpiled.count_ops().values()))

depth: 48
gates: 68

• Okay, this is helpful. Follow up question, I am confused regarding the difference between what you call the "Qiskit language" and the "IBM backends." To run on the IBM quantum machines one must use the Qiskit language, so I would have thought that these things would be the same. When you say Qiskit language, are you referring specifically to the simulators? – thespaceman Oct 23 at 19:11
• You dont need Qiskit to run in the IBM backends. You could use quantum-computing.ibm.com, for example. Also, Qiskit supports multiple backends, with different basis gates and coupling maps. For example honeywell github.com/qiskit-community/qiskit-honeywell-provider – luciano Oct 23 at 19:16
• Okay, if I am using Qiskit to run on the IBM backends then do you recommend that I use method 1 in my post? – thespaceman Oct 23 at 19:21
• The method to choose should be automatically selected by the Qiskit transpiler in that scenario. I extended the answer with examples on that. – luciano Oct 25 at 14:11
• yeap.. welcome to the current state of practical quantum computing :) – luciano Oct 26 at 20:53