[Routing] Add initial mapping strategy for circuit with small # of qubits.

[ammareltigani]

Summarize the task Currently LineInitialMapper is the only initial mapping (placement) strategy Cirq offers for routing. Adding more strategies like graph monomorphism could improve routing performance on deep circuits with a small # of qubits (graph monomorphism scales exponentially with the # of qubits).

Acceptance criteria - when is the task considered done? The task is complete once a graph monomorphism initial mapping strategy is added and is benchmarked for comparison with TKET's implementation here https://github.com/CQCL/tket/tree/develop/tket/src/Placement

Related #5838 #5831

[sefunmi4]

I'm interested in taking on this issue. Will create a branch to start testing out LineInitialMapper. Open to collaborating on the project, feel free to reach out for updates

[sefunmi4]

I’ve been doing some research on graph monomorphisms and mapping strategies and wanted to share my understanding, plus a couple of implementation questions.

My current understanding

A graph monomorphism here means finding an injective, edge-preserving mapping from the circuit interaction graph (logical qubits + two-qubit gates) into the device graph (physical qubits + couplings).

• Pros: guarantees that logical interactions map to valid device edges, which can significantly reduce the number of SWAPs and improve circuit fidelity.
• Cons: Subgraph isomorphism is NP-complete, so methods like VF2 backtracking can be computationally expensive for large or dense graphs.

Alternative approaches

• Greedy line placement (current default): extremely fast, but not optimal.
• VF2-style backtracking: prunes invalid mappings with degree/neighborhood checks; slower but finds higher-quality embeddings.
• Dynamic programming: effective for circuits with repeating structure (bounded treewidth), though memory-heavy.
• Topological sort / order-driven heuristics: aligns placement with gate execution order; very fast but can incur more SWAPs.
• Constraint solvers (ILP/SAT): yield optimal mappings but scale poorly.
• Learning-based mappers: adaptive and noise-aware, but harder to guarantee consistency.

Each has different trade-offs depending on circuit size, depth, and structure.

Open questions

1. Would it make sense to support dynamic mapper selection based on circuit/device conditions?
   • VF2 for small/deep circuits
   • greedy/topological for large/shallow
   • DP for structured ansätze

From what I can tell, route_circuit_cqc.py (doc) could be a natural place to plug in this dynamic mapper since it currently defaults to LineInitialMapper.

2. Once a new mapper is added, should I:
   • update the routing_transformer.ipynb notebook optional arguments (under initial_mapper: Optional[AbstractInitialMapper])?
   • or leave the docs unchanged, assuming LineInitialMapper stays the default if nothing is provided?