# 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? Oct 23 '20 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 Oct 23 '20 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? Oct 23 '20 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. Oct 25 '20 at 14:11
• This is really helpful, thanks! Follow up, I ran the C3X example on ibmq_valencia and found that number of ('cnot','u') = ($30$,$27$). Using the imbq error rate data I find that this circuit results in a ~$20$% failure rate at best. It seems that the multi-control gates represent a major challenge considering the number of 'CNOT' gates that they require. If you have any further comments on optimizing these multi-control circuits I am all ears, but it seems to me that these types of circuits need further advances in the technology before they are practical. Oct 26 '20 at 17:38