Improve synthesis of controlled circuits with controlled gates within

[alexanderivrii]

What should we add?

Consider the following example (inspired by https://arxiv.org/pdf/2412.07372):

inner = QuantumCircuit(5)
inner.append(MCXGate(4), [0, 1, 2, 3, 4])
controlled_inner_gate = inner.to_gate().control(2)
qc1 = QuantumCircuit(15)
qc1.append(controlled_inner_gate, [0, 1, 2, 3, 4, 5, 6])
qct1 = transpile(qc1, basis_gates=["cx", "u"])
print(qct1.count_ops())

qc2 = QuantumCircuit(15)
qc2.append(MCXGate(6), [0, 1, 2, 3, 4, 5, 6])
qct2 = transpile(qc2, basis_gates=["cx", "u"])
print(qct2.count_ops())

Conceptually, both qc1 and qc2 are exactly the same, each containing a single MCX gate with 6 control qubits. However, the output is very different: for qc1 we have OrderedDict({'u': 1272, 'cx': 1142}), and for qc2 we have OrderedDict({'u': 40, 'cx': 30}). The reason is that for qc2 we directly synthesis the controlled-MCX gate over 6 qubits and internally use the synthesis algorithm that uses available idle qubits. On the other hand, for qc1, we first synthesize the MCX gate over 4 qubits, obtain a decomposition, control each gate with two controls, and decompose each of these controlled gates.

We should either improve the synthesis of controlled/annotated gates directly, or do a reduction inside the OptimizeAnnotated pass and include the latter in the transpiler flow.