cirq.RouterCQC does not respect 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 .

[mhucka]

Discussed in Cirq Cynq 2026-03-18: @alejogoogle we're having a little bit of trouble interpreting the diagrams:

1. In the first diagram ("Needed connectivity"), it is not clear what is the intended relationship to the second diagram ("Willow patch to connect to"). Can you describe specifically the desired mapping between those two?

2. Can you please clarify what "I checked that my connectivity graph is built properly, here is the drawing of the graph" means? The graph in the diagram does not map in an obvious way to either the first or second diagrams.

Basically, we were unable to fill in the missing details, and need more information.

[mhucka]

From offline discussions, it sounds like this issue has been resolved.

[NoureldinYosri]

what was the verdict? from what I know Alejo is using an internal router instead of the cirq one

[alejogoogle]

Yes, am using an internal router instead. I don't think the cirq router is working as intended, but the internal router could work as a reference goal

…

On Wed, Apr 15, 2026 at 11:02 AM Noureldin ***@***.***> wrote: *NoureldinYosri* left a comment (quantumlib/Cirq#7892) <#7892 (comment)> what was the verdict? from what I know Alejo is using an internal router instead of the cirq one — Reply to this email directly, view it on GitHub <#7892 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AWGJUYGPOZ4CSV5CGUESVH34V66BHAVCNFSM6AAAAACU62W72GVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHM2DENJTHE2TCNBSGI> . You are receiving this because you were mentioned.Message ID: <quantumlib/Cirq/issues/7892/4253951422 ***@***.***>

-- *Alejo Grajales Dau* | Quantum Hardware Engineer *Google Quantum AI* ***@***.***

[mhucka]

@alejogoogle In that case, could you please provide the additional information requested in my earlier comment? It's hard to figure out what is being requested in this issue.