One or more of the the following people are requested to review this:

• @Qiskit/terra-core

Pull Request Test Coverage Report for Build 6312989890

• 7 of 7 (100.0%) changed or added relevant lines in 1 file are covered.
• 4 unchanged lines in 1 file lost coverage.
• Overall coverage increased (+0.01%) to 87.026%

Totals
Change from base Build 6301697315:	0.01%
Covered Lines:	74066
Relevant Lines:	85108

💛 - Coveralls

Fundamentally, unless we can "jump" to only the barriers, I don't see how we could implement this as linear in the number of barriers rather than the number of all operations, because we have to inspect each operation to find the barriers. The current setup is the construction-space improvement we could have expected, though.

This is true, I'm also thinking shorter term we might be able to rely on filter_nodes in the next rustworkx release (Qiskit/rustworkx#886) to more quickly get the list of barriers even with a linear search. Although I'm not clear if the repeated python function call overhead would defeat any potential gains from a faster iteration there, we'll have to test it.

filter_nodes would still linear in total node count, though - it's just a (potential) reduction in the constant-time factors because we spend less time in Python space looking at the nodes, right?

Yeah exactly, it's still linear time overhead just hopefully a bit faster by doing more work in rust.

I can give filter_nodes a try and see if there's a noticeable improvement, but it probably makes sense to leave that to a follow-up PR.

This is somewhat off-topic, but we could reimplement MergeAdjacentBarriers using CollectAndCollapse pass, where the collection function would look for nodes named "barrier" and the collapsing function would create a bigger barrier out of multiple small ones. The code would be something along the following lines (note: the argument split_blocks=True splits barriers into groups of barriers with pairwise disjoint supports, i.e. does not merge barriers over disjoint qubits).

from qiskit.circuit import QuantumCircuit
from qiskit.circuit.library import Barrier
from functools import partial

from qiskit.transpiler.passes import MergeAdjacentBarriers
from qiskit.transpiler.passes.optimization.collect_and_collapse import (
    CollectAndCollapse,
    collect_using_filter_function,
    collapse_to_operation,
)

class CollectBarriers(CollectAndCollapse):

    def __init__(self):
        collect_function = partial(
            collect_using_filter_function,
            filter_function=_is_barrier,
            split_blocks=True,  # important: avoid merging non-intersecting barriers
            min_block_size=2,
        )
        collapse_function = partial(
            collapse_to_operation, collapse_function=_collapse_to_barrier
        )
        super().__init__(
            collect_function=collect_function,
            collapse_function=collapse_function,
        )

def _is_barrier(node):
    return node.op.name == "barrier"

def _collapse_to_barrier(circuit):
    """
    We have a quantum circuit consisting only of barriers.
    We want to merge these into a single barrier.
    We only need to know how many qubits there are.
    """
    qubits = set()
    for node in circuit:
        for q in node.qubits:
            qubits.add(q)
    return Barrier(len(qubits))

Under the hood this probably does a bit more work than MergeAdjacentBarriers, so I don't think this actually improves performance (would be fun to check this though).