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

Question

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.

.

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

Answer 1

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

IBMQ.load_account()
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