quantrs2_circuit/routing/
mod.rs

1//! Circuit routing algorithms for mapping logical qubits to physical qubits
2//!
3//! This module implements various routing algorithms including SABRE and lookahead
4//! routing for quantum circuits with limited connectivity.
5
6mod coupling_map;
7mod lookahead;
8mod routing_pass;
9mod sabre;
10mod swap_network;
11
12pub use coupling_map::{CouplingMap, Distance};
13pub use lookahead::{LookaheadConfig, LookaheadRouter};
14pub use routing_pass::{RoutedCircuit, RoutingPassType, RoutingResult, RoutingStatistics};
15pub use sabre::{SabreConfig, SabreRouter};
16pub use swap_network::{SwapLayer, SwapNetwork};
17
18use crate::builder::Circuit;
19use quantrs2_core::error::QuantRS2Result;
20use std::collections::HashMap;
21
22/// Routing strategy for quantum circuits
23#[derive(Debug, Clone, Copy, PartialEq, Eq)]
24pub enum RoutingStrategy {
25    /// SABRE (SWAP-based `BidiREctional`) routing
26    Sabre,
27    /// Lookahead routing with configurable depth
28    Lookahead { depth: usize },
29    /// Basic greedy routing
30    Basic,
31    /// Stochastic routing with multiple trials
32    Stochastic { trials: usize },
33}
34
35/// Main router interface
36pub struct CircuitRouter {
37    strategy: RoutingStrategy,
38    coupling_map: CouplingMap,
39}
40
41impl CircuitRouter {
42    /// Create a new router with the specified strategy and coupling map
43    #[must_use]
44    pub const fn new(strategy: RoutingStrategy, coupling_map: CouplingMap) -> Self {
45        Self {
46            strategy,
47            coupling_map,
48        }
49    }
50
51    /// Create a router for a specific backend
52    #[must_use]
53    pub fn for_backend(backend: &str) -> Self {
54        let coupling_map = match backend {
55            "ibm_lagos" => CouplingMap::ibm_lagos(),
56            "ibm_nairobi" => CouplingMap::ibm_nairobi(),
57            "google_sycamore" => CouplingMap::google_sycamore(),
58            _ => CouplingMap::linear(5), // Default to 5-qubit linear
59        };
60
61        Self {
62            strategy: RoutingStrategy::Sabre,
63            coupling_map,
64        }
65    }
66
67    /// Route a circuit to the physical device layout
68    pub fn route<const N: usize>(&self, circuit: &Circuit<N>) -> QuantRS2Result<RoutedCircuit<N>> {
69        match self.strategy {
70            RoutingStrategy::Sabre => {
71                let config = SabreConfig::default();
72                let router = SabreRouter::new(self.coupling_map.clone(), config);
73                router.route(circuit)
74            }
75            RoutingStrategy::Lookahead { depth } => {
76                let config = LookaheadConfig::new(depth);
77                let router = LookaheadRouter::new(self.coupling_map.clone(), config);
78                router.route(circuit)
79            }
80            RoutingStrategy::Basic => {
81                // Use SABRE with basic config for now
82                let config = SabreConfig::basic();
83                let router = SabreRouter::new(self.coupling_map.clone(), config);
84                router.route(circuit)
85            }
86            RoutingStrategy::Stochastic { trials } => {
87                // Run multiple trials and pick the best
88                let mut best_result = None;
89                let mut best_cost = f64::INFINITY;
90
91                for _ in 0..trials {
92                    let config = SabreConfig::stochastic();
93                    let router = SabreRouter::new(self.coupling_map.clone(), config);
94                    let result = router.route(circuit)?;
95                    let cost = result.total_cost();
96
97                    if cost < best_cost {
98                        best_cost = cost;
99                        best_result = Some(result);
100                    }
101                }
102
103                best_result.ok_or_else(|| {
104                    quantrs2_core::error::QuantRS2Error::RoutingError(
105                        "Failed to find valid routing".to_string(),
106                    )
107                })
108            }
109        }
110    }
111
112    /// Get the coupling map
113    #[must_use]
114    pub const fn coupling_map(&self) -> &CouplingMap {
115        &self.coupling_map
116    }
117}
118
119/// Utilities for analyzing routing complexity
120pub mod analysis {
121    use super::{Circuit, CouplingMap};
122    use crate::dag::{circuit_to_dag, CircuitDag};
123
124    /// Analyze routing complexity for a circuit
125    pub struct RoutingAnalyzer {
126        coupling_map: CouplingMap,
127    }
128
129    impl RoutingAnalyzer {
130        #[must_use]
131        pub const fn new(coupling_map: CouplingMap) -> Self {
132            Self { coupling_map }
133        }
134
135        /// Estimate the number of SWAPs needed
136        #[must_use]
137        pub fn estimate_swaps<const N: usize>(&self, circuit: &Circuit<N>) -> usize {
138            let dag = circuit_to_dag(circuit);
139            let mut swap_count = 0;
140
141            // Simple heuristic: count non-adjacent two-qubit gates
142            for node in dag.nodes() {
143                if node.gate.qubits().len() == 2 {
144                    let q1 = node.gate.qubits()[0];
145                    let q2 = node.gate.qubits()[1];
146
147                    if !self
148                        .coupling_map
149                        .are_connected(q1.id() as usize, q2.id() as usize)
150                    {
151                        // Estimate distance-based swaps
152                        let distance = self
153                            .coupling_map
154                            .distance(q1.id() as usize, q2.id() as usize);
155                        swap_count += distance.saturating_sub(1);
156                    }
157                }
158            }
159
160            swap_count
161        }
162
163        /// Calculate interaction graph density
164        #[must_use]
165        pub fn interaction_density<const N: usize>(&self, circuit: &Circuit<N>) -> f64 {
166            let mut interactions = std::collections::HashSet::new();
167
168            for gate in circuit.gates() {
169                if gate.qubits().len() == 2 {
170                    let q1 = gate.qubits()[0].id() as usize;
171                    let q2 = gate.qubits()[1].id() as usize;
172                    interactions.insert((q1.min(q2), q1.max(q2)));
173                }
174            }
175
176            let max_interactions = (N * (N - 1)) / 2;
177            if max_interactions == 0 {
178                0.0
179            } else {
180                interactions.len() as f64 / max_interactions as f64
181            }
182        }
183    }
184}
185
186#[cfg(test)]
187mod tests {
188    use super::*;
189    use quantrs2_core::gate::{multi::CNOT, single::Hadamard};
190    use quantrs2_core::qubit::QubitId;
191
192    #[test]
193    fn test_basic_routing() {
194        let coupling_map = CouplingMap::linear(3);
195        let router = CircuitRouter::new(RoutingStrategy::Basic, coupling_map);
196
197        let mut circuit = Circuit::<3>::new();
198        circuit
199            .add_gate(Hadamard { target: QubitId(0) })
200            .expect("add H gate to circuit");
201        circuit
202            .add_gate(CNOT {
203                control: QubitId(0),
204                target: QubitId(2),
205            })
206            .expect("add CNOT gate to circuit");
207
208        let result = router.route(&circuit);
209        assert!(result.is_ok());
210    }
211}
quantrs2_circuit/routing/mod.rs

quantrs2_circuit/routing/
mod.rs
