Barrier replacement introduces cycle with disjoint coupling map

[mtreinish]

Environment

• Qiskit Terra version: main (0.24.0
• Python version: 3.10
• Operating system: Linux

What is happening?

In some circumstances after #9840 when targeting backends with disjoint coupling maps if there is a barrier spanning multiple connected components on the target backend the SabreLayout pass will raise an error: DAGCircuitError: 'Replacing the specified node block would introduce a cycle'. This is caused by the pass attempting to recombine the barriers after re-assembling the combined circuit after splitting it to solve the layout and routing for the circuit, the cycle check was left on to catch this exact case where combining the barriers on re-assembly would result in an invalid dag.

How can we reproduce the issue?

import numpy as np
import rustworkx as rx

from qiskit import transpile
from qiskit.providers import BackendV2, Options
from qiskit.transpiler import Target, InstructionProperties
from qiskit.circuit.library import XGate, SXGate, RZGate, CZGate
from qiskit.circuit import Measure, Delay, Parameter

class FakeMultiChip(BackendV2):
    """Fake multi chip backend."""

    def __init__(self, degree=3):
        super().__init__(name='multi_chip')
        graph = rx.generators.directed_heavy_hex_graph(degree, bidirectional=False)
        num_qubits = len(graph) * 3
        rng = np.random.default_rng(seed=12345678942)
        rz_props = {}
        x_props = {}
        sx_props = {}
        measure_props = {}
        delay_props = {}
        self._target = Target("Fake multi-chip backend", num_qubits=num_qubits)
        for i in range(num_qubits):
            qarg = (i,)
            rz_props[qarg] = InstructionProperties(error=0.0, duration=0.0)
            x_props[qarg] = InstructionProperties(
                error=rng.uniform(1e-6, 1e-4), duration=rng.uniform(1e-8, 9e-7)
            )
            sx_props[qarg] = InstructionProperties(
                error=rng.uniform(1e-6, 1e-4), duration=rng.uniform(1e-8, 9e-7)
            )
            measure_props[qarg] = InstructionProperties(
                error=rng.uniform(1e-3, 1e-1), duration=rng.uniform(1e-8, 9e-7)
            )
            delay_props[qarg] = None
        self._target.add_instruction(XGate(), x_props)
        self._target.add_instruction(SXGate(), sx_props)
        self._target.add_instruction(RZGate(Parameter("theta")), rz_props)
        self._target.add_instruction(Measure(), measure_props)
        self._target.add_instruction(Delay(Parameter("t")), delay_props)
        cz_props = {}
        for i in range(3):
            for root_edge in graph.edge_list():
                offset = i * len(graph)
                edge = (root_edge[0] + offset, root_edge[1] + offset)
                cz_props[edge] = InstructionProperties(
                    error=rng.uniform(1e-5, 5e-3), duration=rng.uniform(1e-8, 9e-7)
                )
        self._target.add_instruction(CZGate(), cz_props)

    @property
    def target(self):
        return self._target
    
    @property
    def max_circuits(self):
        return None

    @classmethod
    def _default_options(cls):
        return Options(shots=1024)

    def run(self, circuit, **kwargs):
        raise NotImplementedError    

qc = QuantumCircuit(42)
qc.h(0)
qc.h(10)
qc.h(20)
qc.cx(0, 1)
qc.cx(0, 2)
qc.cx(0, 3)
qc.cx(0, 4)
qc.cx(0, 5)
qc.cx(0, 6)
qc.cx(0, 7)
qc.cx(0, 8)
qc.cx(0, 9)
qc.ecr(10, 11)
qc.ecr(10, 12)
qc.ecr(10, 13)
qc.ecr(10, 14)
qc.ecr(10, 15)
qc.ecr(10, 16)
qc.ecr(10, 17)
qc.ecr(10, 18)
qc.ecr(10, 19)
qc.cy(20, 21)
qc.cy(20, 22)
qc.cy(20, 23)
qc.cy(20, 24)
qc.cy(20, 25)
qc.cy(20, 26)
qc.cy(20, 27)
qc.cy(20, 28)
qc.cy(20, 29)
qc.h(30)
qc.cx(30, 31)
qc.cx(30, 32)
qc.cx(30, 33)
qc.h(34)
qc.cx(34, 35)
qc.cx(34, 36)
qc.cx(34, 37)
qc.h(38)
qc.cx(38, 39)
qc.cx(39, 40)
qc.cx(39, 41)
qc.measure_all()
res = transpile(qc, backend, seed_transpiler=42)

What should happen?

The transpile() call should not error. The root cause is the barrier spanning across the connected components would result in a cycle in the dag.

Any suggestions?

I was worried about this #9840 but I don't have a good solution. The first thought is on encountering a cycle we keep the dag split and just drop the UUID label which doesn't seem great. My bigger concern is that this means doing routing on the split dags is not valid and we need to apply the layout first and then run routing on the full circuit to be able to reliably do it. This has a performance overhead, but would only apply if the number of connected components > 1 so it might be worth it. We already take this hit if there is any classical data shared between components in the circuit so it might just be worth it to expand https://github.com/Qiskit/qiskit-terra/blob/33704ea61f6a3fa60612cbe4463894d2859fe9ec/qiskit/transpiler/passes/layout/sabre_layout.py to be for all circuits with > 1 connected component.