cirq.RouterCQC is not respecting the connectivity graph when routing a circuit

[alejogoogle]

Describe the issue

See MWE colab. I am trying to route a circuit that requires triangular connectivity into the Willow chip.

Needed connectivity

Willow patch to connect to

After routing, the routed circuit is using only a 3x3 square lattice of qubits, instead of the full diamond I expected

I checked that my connectivity graph is built properly, here is the drawing of the graph

[Vivek1106-04]

@alejogoogle @NoureldinYosri recently i have worked RouteCQC , so i did some work to find out the root cause for this issue

The "3×3 Square Lattice" Is NOT a Bug

The observation that the router appears to force circuits into a 3×3 square lattice is expected behavior caused by the default LineInitialMapper.

LineInitialMapper greedily assigns logical qubits starting from the center of the device graph, prioritizing high-degree nodes and their neighbors. On Willow/Diamond-style topologies, the central region naturally forms a compact cluster of roughly nine qubits. This compact placement visually resembles a 3×3 grid.

Importantly, during verification:

• The router respects the actual device connectivity.
• No artificial edges are introduced.
• No rectangular lattice is enforced internally.

The grid-like appearance is therefore only a side effect of compact placement symmetry and not incorrect routing behavior.

---

Real Issue: RouteCQC Crashes on Sparse Topologies

To test whether routing correctly handles missing edges (a normal requirement for Willow-like hardware), I forced a configuration where two interacting qubits are mapped onto non-adjacent physical qubits that require routing around a gap.

Expected behavior:

• The router should insert SWAP operations.
• Routing should follow the available path in the device graph.

Actual behavior:

• RouteCQC crashes instead of routing.

This indicates the router fails when the initial placement produces a disconnected interaction — a common situation for sparse quantum hardware graphs.

---

Minimal Reproduction

import cirq
import networkx as nx

def reproduce_crash():
    # U-shaped graph (Willow subset):
    # (0,0)--(0,1)--(1,1)--(1,0)
    # NOTE: No edge between (0,0) and (1,0)

    q00, q01 = cirq.GridQubit(0, 0), cirq.GridQubit(0, 1)
    q10, q11 = cirq.GridQubit(1, 0), cirq.GridQubit(1, 1)

    device_graph = nx.Graph()
    device_graph.add_edges_from([
        (q00, q01),
        (q01, q11),
        (q11, q10),
    ])

    # Circuit requiring interaction across the gap
    lq0, lq1 = cirq.LineQubit(0), cirq.LineQubit(1)
    circuit = cirq.Circuit(cirq.CNOT(lq0, lq1))

    # Force mapping to disconnected endpoints
    mapper = cirq.HardCodedInitialMapper({
        lq0: q00,
        lq1: q10,
    })

    print(f"Is (0,0)-(1,0) connected? {device_graph.has_edge(q00, q10)}")

    router = cirq.RouteCQC(device_graph)
    routed = router(circuit, initial_mapper=mapper)  #  Crashes here

reproduce_crash()

Output:

Is (0,0)-(1,0) connected? False
IndexError: list index out of range

I would like to dig deeper into this , can i get additional information , thank you .