@anedumla noticed that theorem 5 in https://arxiv.org/abs/1501.06911 bounds the amount of CNOTs needed to decompose a SU(2) gate when (n-1)-controlled.

The bound of resulting CNOTs in the decomposition grows linearly with respect to the amount of controlled qubits. However, the decomposition of MCX groups exponentially:

number_of_qubits = []
result = []
boundery = []
for k in range(1, 10):
    n = k+1
    circuit = QuantumCircuit(k+1)
    circuit.append(XGate().control(k), list(range(k+1)))
    unroller = Unroller(basis_gates)
    qc = unroller(circuit)
    number_of_qubits.append(n)
    result.append(qc.count_ops()['cx'])
    boundery.append(28*n-88)

What is the expected enhancement?

A non-ancilla decomposition of QuantumCircuit.mcx() should result in a linear amount of CNOTs. https://arxiv.org/abs/1501.06911 refers to https://arxiv.org/abs/quant-ph/9503016 for calculating A-B-C, that can be precomputed.

In it's generic form, Theorem 5 can be applied any multi-controlled-W, where W \in SU(2). Therefore, I assume is can be generalised to fix the example #5840 by creating a possible decomposition.