Environment

• Qiskit Terra version: 0.25.1 and main
• Python version: 3.11
• Operating system: Linux

What is happening?

The MergeAdjacentBarriers pass can take a large amount of time as it scales linearly with the number of instructions. This scaling seems less than ideal, especially as the number of barriers in a typical circuit is much lower than other gates. This pass gets run internally by BarrierBeforeFinalMeasurements which is part of all the preset pass managers when routing is run so making this pass as quick as possible is important.

How can we reproduce the issue?

Run MergeAdjacentBarriers on a large circuit with > 100k gates.

What should happen?

The time to execute a utility pass like this should scale with the number of barriers not total gates.

Any suggestions?

The core of the issue is that the pass is rebuilding the complete DAG to merge the barriers here: https://github.com/Qiskit/qiskit/blob/main/qiskit/transpiler/passes/utils/merge_adjacent_barriers.py#L76-L86 this is because if there is a partially overlapping set of qubits between two barriers there historically wasn't a good mechanism to replace multiple barriers with a single node wider than either of the two it's replacing. However, we have the DAGCircuit.replace_block_with_op now which I think can be used to replace multiple barriers in place.