MCXVChain with dirty ancilla is not optimal.

[adjs]

Environment

• Qiskit Terra version: 0.23.2
• Python version: 3.8.10
• Operating system: Ubuntu 20.04.5 LTS

What is happening?

The number of cx operations in the MCXVChain gate with dirty_ancilla=True and k controls is higher than 8k -6 [Lemma 7, https://arxiv.org/pdf/1501.06911.pdf].

How can we reproduce the issue?

from qiskit import transpile
from qiskit.circuit.library.standard_gates import MCXVChain

k = 10
qc = MCXVChain(k, True).definition
tqc = transpile(qc, basis_gates=['u', 'cx'])
print(tqc.count_ops()['cx'])

prints 98 instead of 10*8-6=74.

What should happen?

MCXVChain with dirty_ancilla=True and k controls should use 8k-6 cx gates.

Any suggestions?

No response

[ShellyGarion]

closed by #9687