quantrs2_circuit/
topology.rs

1//! Enhanced topological sorting and dependency analysis for quantum circuits.
2//!
3//! This module provides advanced topological analysis capabilities including
4//! multiple sorting strategies, dependency chains, and critical path analysis.
5use crate::builder::Circuit;
6use crate::commutation::CommutationAnalyzer;
7use crate::dag::{circuit_to_dag, CircuitDag, DagNode};
8use quantrs2_core::{gate::GateOp, qubit::QubitId};
9use std::collections::{HashMap, HashSet, VecDeque};
10/// Result of topological analysis
11#[derive(Debug, Clone)]
12pub struct TopologicalAnalysis {
13    /// Standard topological order
14    pub topological_order: Vec<usize>,
15    /// Reverse topological order
16    pub reverse_order: Vec<usize>,
17    /// Layers of gates that can be executed in parallel
18    pub parallel_layers: Vec<Vec<usize>>,
19    /// Critical path through the circuit
20    pub critical_path: Vec<usize>,
21    /// Gate priorities based on criticality
22    pub gate_priorities: HashMap<usize, f64>,
23    /// Dependency chains for each qubit
24    pub qubit_chains: HashMap<u32, Vec<usize>>,
25    /// Circuit depth
26    pub depth: usize,
27    /// Circuit width (max parallel gates)
28    pub width: usize,
29}
30/// Strategy for topological sorting
31#[derive(Debug, Clone, Copy, PartialEq, Eq)]
32pub enum TopologicalStrategy {
33    /// Standard Kahn's algorithm
34    Standard,
35    /// Prioritize gates on critical path
36    CriticalPath,
37    /// Minimize circuit depth
38    MinDepth,
39    /// Maximize parallelism
40    MaxParallel,
41    /// Prioritize by gate type
42    GateTypePriority,
43    /// Custom priority function
44    Custom,
45}
46/// Advanced topological analyzer
47pub struct TopologicalAnalyzer {
48    /// Commutation analyzer for optimization
49    commutation_analyzer: CommutationAnalyzer,
50}
51impl TopologicalAnalyzer {
52    /// Create a new topological analyzer
53    #[must_use]
54    pub fn new() -> Self {
55        Self {
56            commutation_analyzer: CommutationAnalyzer::new(),
57        }
58    }
59    /// Perform comprehensive topological analysis
60    #[must_use]
61    pub fn analyze<const N: usize>(&self, circuit: &Circuit<N>) -> TopologicalAnalysis {
62        let dag = circuit_to_dag(circuit);
63        let topological_order =
64            Self::topological_sort_with_priorities(&dag, TopologicalStrategy::Standard);
65        let reverse_order = Self::reverse_topological_sort(&dag);
66        let parallel_layers = self.find_parallel_layers(&dag);
67        let critical_path = dag.critical_path();
68        let gate_priorities = Self::calculate_gate_priorities(&dag, &critical_path);
69        let qubit_chains = Self::find_qubit_chains(&dag);
70        let depth = dag.max_depth() + 1;
71        let width = parallel_layers
72            .iter()
73            .map(std::vec::Vec::len)
74            .max()
75            .unwrap_or(0);
76        TopologicalAnalysis {
77            topological_order,
78            reverse_order,
79            parallel_layers,
80            critical_path,
81            gate_priorities,
82            qubit_chains,
83            depth,
84            width,
85        }
86    }
87    /// Perform topological sort with specific strategy
88    #[must_use]
89    pub fn sort_with_strategy<const N: usize>(
90        &self,
91        circuit: &Circuit<N>,
92        strategy: TopologicalStrategy,
93    ) -> Vec<usize> {
94        let dag = circuit_to_dag(circuit);
95        Self::topological_sort_with_priorities(&dag, strategy)
96    }
97    /// Topological sort with priority-based tie breaking
98    fn topological_sort_with_priorities(
99        dag: &CircuitDag,
100        strategy: TopologicalStrategy,
101    ) -> Vec<usize> {
102        let nodes = dag.nodes();
103        let n = nodes.len();
104        if n == 0 {
105            return Vec::new();
106        }
107        let mut in_degree = vec![0; n];
108        for node in nodes {
109            in_degree[node.id] = node.predecessors.len();
110        }
111        let priority_fn: Box<dyn Fn(usize) -> f64> = match strategy {
112            TopologicalStrategy::Standard => Box::new(|id| -(id as f64)),
113            TopologicalStrategy::CriticalPath => {
114                let critical_set: HashSet<_> = dag.critical_path().into_iter().collect();
115                Box::new(move |id| {
116                    if critical_set.contains(&id) {
117                        1000.0
118                    } else {
119                        0.0
120                    }
121                })
122            }
123            TopologicalStrategy::MinDepth => Box::new(move |id| -(nodes[id].depth as f64)),
124            TopologicalStrategy::MaxParallel => Box::new(move |id| {
125                let parallel_count = dag.parallel_nodes(id).len();
126                parallel_count as f64
127            }),
128            TopologicalStrategy::GateTypePriority => Box::new(move |id| {
129                let gate = &nodes[id].gate;
130                match gate.qubits().len() {
131                    1 => 100.0,
132                    2 => 50.0,
133                    _ => 0.0,
134                }
135            }),
136            TopologicalStrategy::Custom => Box::new(|_| 0.0),
137        };
138        let mut ready_nodes = Vec::new();
139        for i in 0..n {
140            if in_degree[i] == 0 {
141                ready_nodes.push((priority_fn(i), i));
142            }
143        }
144        let mut sorted = Vec::new();
145        while !ready_nodes.is_empty() {
146            ready_nodes.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap_or(std::cmp::Ordering::Equal));
147            let (_, node_id) = ready_nodes.remove(0);
148            sorted.push(node_id);
149            for &succ in &nodes[node_id].successors {
150                in_degree[succ] -= 1;
151                if in_degree[succ] == 0 {
152                    ready_nodes.push((priority_fn(succ), succ));
153                }
154            }
155        }
156        sorted
157    }
158    /// Reverse topological sort
159    fn reverse_topological_sort(dag: &CircuitDag) -> Vec<usize> {
160        let nodes = dag.nodes();
161        let n = nodes.len();
162        if n == 0 {
163            return Vec::new();
164        }
165        let mut out_degree = vec![0; n];
166        for node in nodes {
167            out_degree[node.id] = node.successors.len();
168        }
169        let mut queue = VecDeque::new();
170        for i in 0..n {
171            if out_degree[i] == 0 {
172                queue.push_back(i);
173            }
174        }
175        let mut sorted = Vec::new();
176        while let Some(node_id) = queue.pop_front() {
177            sorted.push(node_id);
178            for &pred in &nodes[node_id].predecessors {
179                out_degree[pred] -= 1;
180                if out_degree[pred] == 0 {
181                    queue.push_back(pred);
182                }
183            }
184        }
185        sorted.reverse();
186        sorted
187    }
188    /// Find layers of gates that can be executed in parallel
189    fn find_parallel_layers(&self, dag: &CircuitDag) -> Vec<Vec<usize>> {
190        let max_depth = dag.max_depth();
191        let mut layers = Vec::new();
192        for depth in 0..=max_depth {
193            let layer = dag.nodes_at_depth(depth);
194            if !layer.is_empty() {
195                layers.push(layer);
196            }
197        }
198        self.optimize_parallel_layers(dag, layers)
199    }
200    /// Optimize parallel layers using commutation
201    fn optimize_parallel_layers(
202        &self,
203        dag: &CircuitDag,
204        mut layers: Vec<Vec<usize>>,
205    ) -> Vec<Vec<usize>> {
206        let nodes = dag.nodes();
207        for i in 0..layers.len() {
208            if i + 1 < layers.len() {
209                let mut gates_to_move = Vec::new();
210                for &gate_id in &layers[i + 1] {
211                    let gate = &nodes[gate_id].gate;
212                    let can_move = layers[i].iter().all(|&other_id| {
213                        let other_gate = &nodes[other_id].gate;
214                        self.commutation_analyzer
215                            .gates_commute(gate.as_ref(), other_gate.as_ref())
216                    });
217                    if can_move {
218                        gates_to_move.push(gate_id);
219                    }
220                }
221                for gate_id in gates_to_move {
222                    layers[i + 1].retain(|&x| x != gate_id);
223                    layers[i].push(gate_id);
224                }
225            }
226        }
227        layers.retain(|layer| !layer.is_empty());
228        layers
229    }
230    /// Calculate gate priorities based on criticality
231    fn calculate_gate_priorities(dag: &CircuitDag, critical_path: &[usize]) -> HashMap<usize, f64> {
232        let mut priorities = HashMap::new();
233        let nodes = dag.nodes();
234        let critical_set: HashSet<_> = critical_path.iter().copied().collect();
235        for node in nodes {
236            let mut priority = 0.0;
237            if critical_set.contains(&node.id) {
238                priority += 100.0;
239            }
240            priority += (nodes.len() - node.depth) as f64;
241            priority += node.successors.len() as f64 * 10.0;
242            match node.gate.qubits().len() {
243                1 => priority += 5.0,
244                2 => priority += 3.0,
245                _ => priority += 1.0,
246            }
247            priorities.insert(node.id, priority);
248        }
249        priorities
250    }
251    /// Find dependency chains for each qubit
252    fn find_qubit_chains(dag: &CircuitDag) -> HashMap<u32, Vec<usize>> {
253        let mut chains = HashMap::new();
254        let nodes = dag.nodes();
255        let mut qubit_nodes: HashMap<u32, Vec<usize>> = HashMap::new();
256        for node in nodes {
257            for qubit in node.gate.qubits() {
258                qubit_nodes.entry(qubit.id()).or_default().push(node.id);
259            }
260        }
261        for (qubit, mut node_ids) in qubit_nodes {
262            node_ids.sort_by_key(|&id| nodes[id].depth);
263            chains.insert(qubit, node_ids);
264        }
265        chains
266    }
267    /// Find the longest dependency chain in the circuit
268    #[must_use]
269    pub fn find_longest_chain<const N: usize>(&self, circuit: &Circuit<N>) -> Vec<usize> {
270        let dag = circuit_to_dag(circuit);
271        dag.critical_path()
272    }
273    /// Find independent gate sets
274    #[must_use]
275    pub fn find_independent_sets<const N: usize>(&self, circuit: &Circuit<N>) -> Vec<Vec<usize>> {
276        let dag = circuit_to_dag(circuit);
277        let nodes = dag.nodes();
278        let mut independent_sets = Vec::new();
279        let mut remaining: HashSet<usize> = (0..nodes.len()).collect();
280        while !remaining.is_empty() {
281            let mut current_set = Vec::new();
282            let mut to_remove = Vec::new();
283            for &node_id in &remaining {
284                let is_independent = current_set
285                    .iter()
286                    .all(|&other_id| dag.are_independent(node_id, other_id));
287                if is_independent {
288                    current_set.push(node_id);
289                    to_remove.push(node_id);
290                }
291            }
292            for node_id in to_remove {
293                remaining.remove(&node_id);
294            }
295            if !current_set.is_empty() {
296                independent_sets.push(current_set);
297            }
298        }
299        independent_sets
300    }
301    /// Compute the dependency matrix
302    #[must_use]
303    pub fn dependency_matrix<const N: usize>(&self, circuit: &Circuit<N>) -> Vec<Vec<bool>> {
304        let dag = circuit_to_dag(circuit);
305        let n = dag.nodes().len();
306        let mut matrix = vec![vec![false; n]; n];
307        for i in 0..n {
308            for j in 0..n {
309                if i != j {
310                    matrix[i][j] = !dag.paths_between(j, i).is_empty();
311                }
312            }
313        }
314        matrix
315    }
316}
317impl Default for TopologicalAnalyzer {
318    fn default() -> Self {
319        Self::new()
320    }
321}
322/// Extension methods for circuits
323impl<const N: usize> Circuit<N> {
324    /// Perform topological analysis
325    #[must_use]
326    pub fn topological_analysis(&self) -> TopologicalAnalysis {
327        let analyzer = TopologicalAnalyzer::new();
328        analyzer.analyze(self)
329    }
330    /// Get topological order with specific strategy
331    #[must_use]
332    pub fn topological_sort(&self, strategy: TopologicalStrategy) -> Vec<usize> {
333        let analyzer = TopologicalAnalyzer::new();
334        analyzer.sort_with_strategy(self, strategy)
335    }
336}
337#[cfg(test)]
338mod tests {
339    use super::*;
340    use quantrs2_core::gate::multi::CNOT;
341    use quantrs2_core::gate::single::{Hadamard, PauliX};
342    #[test]
343    fn test_topological_analysis() {
344        let mut circuit = Circuit::<3>::new();
345        circuit
346            .add_gate(Hadamard { target: QubitId(0) })
347            .expect("Failed to add Hadamard gate to qubit 0");
348        circuit
349            .add_gate(Hadamard { target: QubitId(1) })
350            .expect("Failed to add Hadamard gate to qubit 1");
351        circuit
352            .add_gate(CNOT {
353                control: QubitId(0),
354                target: QubitId(1),
355            })
356            .expect("Failed to add CNOT gate from qubit 0 to qubit 1");
357        circuit
358            .add_gate(PauliX { target: QubitId(2) })
359            .expect("Failed to add PauliX gate to qubit 2");
360        circuit
361            .add_gate(CNOT {
362                control: QubitId(1),
363                target: QubitId(2),
364            })
365            .expect("Failed to add CNOT gate from qubit 1 to qubit 2");
366        let analysis = circuit.topological_analysis();
367        assert_eq!(analysis.topological_order.len(), 5);
368        assert!(analysis.depth > 0);
369        assert!(analysis.width > 0);
370        assert!(!analysis.critical_path.is_empty());
371    }
372    #[test]
373    fn test_parallel_layers() {
374        let mut circuit = Circuit::<4>::new();
375        circuit
376            .add_gate(Hadamard { target: QubitId(0) })
377            .expect("Failed to add Hadamard gate to qubit 0");
378        circuit
379            .add_gate(Hadamard { target: QubitId(1) })
380            .expect("Failed to add Hadamard gate to qubit 1");
381        circuit
382            .add_gate(Hadamard { target: QubitId(2) })
383            .expect("Failed to add Hadamard gate to qubit 2");
384        circuit
385            .add_gate(Hadamard { target: QubitId(3) })
386            .expect("Failed to add Hadamard gate to qubit 3");
387        let analyzer = TopologicalAnalyzer::new();
388        let analysis = analyzer.analyze(&circuit);
389        assert_eq!(analysis.parallel_layers.len(), 1);
390        assert_eq!(analysis.parallel_layers[0].len(), 4);
391    }
392    #[test]
393    fn test_qubit_chains() {
394        let mut circuit = Circuit::<2>::new();
395        circuit
396            .add_gate(Hadamard { target: QubitId(0) })
397            .expect("Failed to add first Hadamard gate to qubit 0");
398        circuit
399            .add_gate(PauliX { target: QubitId(0) })
400            .expect("Failed to add PauliX gate to qubit 0");
401        circuit
402            .add_gate(Hadamard { target: QubitId(0) })
403            .expect("Failed to add second Hadamard gate to qubit 0");
404        let analysis = circuit.topological_analysis();
405        assert_eq!(analysis.qubit_chains[&0].len(), 3);
406    }
407    #[test]
408    fn test_sorting_strategies() {
409        let mut circuit = Circuit::<3>::new();
410        circuit
411            .add_gate(CNOT {
412                control: QubitId(0),
413                target: QubitId(1),
414            })
415            .expect("Failed to add first CNOT gate");
416        circuit
417            .add_gate(Hadamard { target: QubitId(2) })
418            .expect("Failed to add Hadamard gate to qubit 2");
419        circuit
420            .add_gate(CNOT {
421                control: QubitId(1),
422                target: QubitId(2),
423            })
424            .expect("Failed to add second CNOT gate");
425        let analyzer = TopologicalAnalyzer::new();
426        let standard = analyzer.sort_with_strategy(&circuit, TopologicalStrategy::Standard);
427        let critical = analyzer.sort_with_strategy(&circuit, TopologicalStrategy::CriticalPath);
428        let gate_type =
429            analyzer.sort_with_strategy(&circuit, TopologicalStrategy::GateTypePriority);
430        assert_eq!(standard.len(), 3);
431        assert_eq!(critical.len(), 3);
432        assert_eq!(gate_type.len(), 3);
433    }
434}
quantrs2_circuit/topology.rs

quantrs2_circuit/
topology.rs
