ruqu_core/
circuit_analyzer.rs

1//! Circuit analysis utilities for simulation backend selection.
2//!
3//! Provides detailed structural analysis of quantum circuits to enable
4//! intelligent routing to the optimal simulation backend. This module
5//! complements [`crate::backend`] by exposing lower-level classification
6//! and structural queries that advanced users or future optimisation passes
7//! may need independently.
8
9use crate::circuit::QuantumCircuit;
10use crate::gate::Gate;
11use crate::types::QubitIndex;
12use std::collections::HashSet;
13
14// ---------------------------------------------------------------------------
15// Gate classification
16// ---------------------------------------------------------------------------
17
18/// Detailed gate classification for routing decisions.
19///
20/// Every [`Gate`] variant maps to exactly one `GateClass`, making it easy to
21/// partition a circuit by gate type without pattern-matching on every variant.
22#[derive(Debug, Clone, Copy, PartialEq, Eq)]
23pub enum GateClass {
24    /// Clifford gate (H, S, Sdg, X, Y, Z, CNOT, CZ, SWAP).
25    Clifford,
26    /// Non-Clifford unitary (T, Tdg, rotations, custom unitary).
27    NonClifford,
28    /// Measurement operation.
29    Measurement,
30    /// Reset operation.
31    Reset,
32    /// Barrier (scheduling hint, no physical effect).
33    Barrier,
34}
35
36/// Classify a single gate for backend routing.
37///
38/// # Example
39///
40/// ```
41/// use ruqu_core::gate::Gate;
42/// use ruqu_core::circuit_analyzer::{classify_gate, GateClass};
43///
44/// assert_eq!(classify_gate(&Gate::H(0)), GateClass::Clifford);
45/// assert_eq!(classify_gate(&Gate::T(0)), GateClass::NonClifford);
46/// assert_eq!(classify_gate(&Gate::Measure(0)), GateClass::Measurement);
47/// ```
48pub fn classify_gate(gate: &Gate) -> GateClass {
49    match gate {
50        Gate::H(_)
51        | Gate::X(_)
52        | Gate::Y(_)
53        | Gate::Z(_)
54        | Gate::S(_)
55        | Gate::Sdg(_)
56        | Gate::CNOT(_, _)
57        | Gate::CZ(_, _)
58        | Gate::SWAP(_, _) => GateClass::Clifford,
59
60        Gate::T(_)
61        | Gate::Tdg(_)
62        | Gate::Rx(_, _)
63        | Gate::Ry(_, _)
64        | Gate::Rz(_, _)
65        | Gate::Phase(_, _)
66        | Gate::Rzz(_, _, _)
67        | Gate::Unitary1Q(_, _) => GateClass::NonClifford,
68
69        Gate::Measure(_) => GateClass::Measurement,
70        Gate::Reset(_) => GateClass::Reset,
71        Gate::Barrier => GateClass::Barrier,
72    }
73}
74
75// ---------------------------------------------------------------------------
76// Clifford analysis
77// ---------------------------------------------------------------------------
78
79/// Check if a circuit is entirely Clifford-compatible.
80///
81/// A circuit is Clifford-compatible when every gate is either a Clifford
82/// unitary, a measurement, a reset, or a barrier. Such circuits can be
83/// simulated in polynomial time using the stabilizer formalism.
84///
85/// # Example
86///
87/// ```
88/// use ruqu_core::circuit::QuantumCircuit;
89/// use ruqu_core::circuit_analyzer::is_clifford_circuit;
90///
91/// let mut circ = QuantumCircuit::new(3);
92/// circ.h(0).cnot(0, 1).cnot(1, 2);
93/// assert!(is_clifford_circuit(&circ));
94///
95/// circ.t(0);
96/// assert!(!is_clifford_circuit(&circ));
97/// ```
98pub fn is_clifford_circuit(circuit: &QuantumCircuit) -> bool {
99    circuit.gates().iter().all(|g| {
100        let class = classify_gate(g);
101        class == GateClass::Clifford
102            || class == GateClass::Measurement
103            || class == GateClass::Reset
104            || class == GateClass::Barrier
105    })
106}
107
108/// Count the number of non-Clifford gates in a circuit.
109///
110/// This is the primary cost metric for stabilizer-based simulation with
111/// magic-state injection: each non-Clifford gate requires exponentially
112/// more resources to handle exactly.
113pub fn count_non_clifford(circuit: &QuantumCircuit) -> usize {
114    circuit
115        .gates()
116        .iter()
117        .filter(|g| classify_gate(g) == GateClass::NonClifford)
118        .count()
119}
120
121// ---------------------------------------------------------------------------
122// Entanglement and connectivity analysis
123// ---------------------------------------------------------------------------
124
125/// Analyze the entanglement structure of a circuit.
126///
127/// Returns the set of qubit pairs that are directly entangled by at least
128/// one two-qubit gate. Pairs are returned with the smaller index first.
129///
130/// # Example
131///
132/// ```
133/// use ruqu_core::circuit::QuantumCircuit;
134/// use ruqu_core::circuit_analyzer::entanglement_pairs;
135///
136/// let mut circ = QuantumCircuit::new(4);
137/// circ.cnot(0, 2).cz(1, 3);
138/// let pairs = entanglement_pairs(&circ);
139/// assert!(pairs.contains(&(0, 2)));
140/// assert!(pairs.contains(&(1, 3)));
141/// assert_eq!(pairs.len(), 2);
142/// ```
143pub fn entanglement_pairs(circuit: &QuantumCircuit) -> HashSet<(QubitIndex, QubitIndex)> {
144    let mut pairs = HashSet::new();
145    for gate in circuit.gates() {
146        let qubits = gate.qubits();
147        if qubits.len() == 2 {
148            let (a, b) = if qubits[0] < qubits[1] {
149                (qubits[0], qubits[1])
150            } else {
151                (qubits[1], qubits[0])
152            };
153            pairs.insert((a, b));
154        }
155    }
156    pairs
157}
158
159/// Check if all two-qubit gates act on nearest-neighbor qubits.
160///
161/// A circuit with only nearest-neighbor interactions maps efficiently to
162/// linear qubit topologies and is a good candidate for Matrix Product State
163/// (MPS) tensor-network simulation.
164pub fn is_nearest_neighbor(circuit: &QuantumCircuit) -> bool {
165    circuit.gates().iter().all(|gate| {
166        let qubits = gate.qubits();
167        if qubits.len() == 2 {
168            let dist = if qubits[0] > qubits[1] {
169                qubits[0] - qubits[1]
170            } else {
171                qubits[1] - qubits[0]
172            };
173            dist <= 1
174        } else {
175            true
176        }
177    })
178}
179
180// ---------------------------------------------------------------------------
181// Bond dimension estimation
182// ---------------------------------------------------------------------------
183
184/// Estimate the maximum bond dimension needed for MPS simulation.
185///
186/// Scans every possible bipartition of the qubit register (cuts between
187/// position `k-1` and `k` for `k` in `1..n`) and counts how many two-qubit
188/// gates straddle each cut. The bond dimension grows exponentially with the
189/// number of entangling gates across the worst-case cut, capped at 2^20
190/// (roughly 1 million) as a practical limit.
191///
192/// This is a rough *upper bound*; cancellations and limited entanglement
193/// growth mean the actual bond dimension required may be much lower.
194pub fn estimate_bond_dimension(circuit: &QuantumCircuit) -> usize {
195    let n = circuit.num_qubits();
196    let mut max_entanglement_across_cut = 0usize;
197
198    // For each possible bipartition cut position.
199    for cut in 1..n {
200        let mut gates_crossing_cut = 0usize;
201        for gate in circuit.gates() {
202            let qubits = gate.qubits();
203            if qubits.len() == 2 {
204                let (lo, hi) = if qubits[0] < qubits[1] {
205                    (qubits[0], qubits[1])
206                } else {
207                    (qubits[1], qubits[0])
208                };
209                if lo < cut && hi >= cut {
210                    gates_crossing_cut += 1;
211                }
212            }
213        }
214        if gates_crossing_cut > max_entanglement_across_cut {
215            max_entanglement_across_cut = gates_crossing_cut;
216        }
217    }
218
219    // Bond dimension is 2^(gates across cut), bounded to avoid overflow.
220    let exponent = max_entanglement_across_cut.min(20) as u32;
221    2usize.saturating_pow(exponent)
222}
223
224// ---------------------------------------------------------------------------
225// Circuit summary
226// ---------------------------------------------------------------------------
227
228/// Summary of circuit characteristics for display and diagnostics.
229#[derive(Debug, Clone)]
230pub struct CircuitSummary {
231    /// Number of qubits in the register.
232    pub num_qubits: u32,
233    /// Circuit depth (longest qubit timeline).
234    pub depth: u32,
235    /// Total number of gates (including measurements and barriers).
236    pub total_gates: usize,
237    /// Number of Clifford gates.
238    pub clifford_count: usize,
239    /// Number of non-Clifford unitary gates.
240    pub non_clifford_count: usize,
241    /// Number of measurement gates.
242    pub measurement_count: usize,
243    /// Whether the circuit contains only Clifford gates (plus measurements/resets).
244    pub is_clifford_only: bool,
245    /// Whether all two-qubit gates are nearest-neighbor.
246    pub is_nearest_neighbor: bool,
247    /// Estimated maximum MPS bond dimension.
248    pub estimated_bond_dim: usize,
249    /// Human-readable state-vector memory requirement.
250    pub state_vector_memory: String,
251}
252
253/// Generate a comprehensive summary of a circuit.
254///
255/// Collects all structural statistics in a single pass and returns them
256/// in a [`CircuitSummary`] suitable for logging or display.
257///
258/// # Example
259///
260/// ```
261/// use ruqu_core::circuit::QuantumCircuit;
262/// use ruqu_core::circuit_analyzer::summarize_circuit;
263///
264/// let mut circ = QuantumCircuit::new(4);
265/// circ.h(0).cnot(0, 1).t(2).measure(3);
266/// let summary = summarize_circuit(&circ);
267/// assert_eq!(summary.num_qubits, 4);
268/// assert_eq!(summary.clifford_count, 2);
269/// assert_eq!(summary.non_clifford_count, 1);
270/// assert_eq!(summary.measurement_count, 1);
271/// ```
272pub fn summarize_circuit(circuit: &QuantumCircuit) -> CircuitSummary {
273    let num_qubits = circuit.num_qubits();
274    let total_gates = circuit.gate_count();
275    let depth = circuit.depth();
276
277    let mut clifford_count = 0;
278    let mut non_clifford_count = 0;
279    let mut measurement_count = 0;
280
281    for gate in circuit.gates() {
282        match classify_gate(gate) {
283            GateClass::Clifford => clifford_count += 1,
284            GateClass::NonClifford => non_clifford_count += 1,
285            GateClass::Measurement => measurement_count += 1,
286            _ => {}
287        }
288    }
289
290    let state_vector_memory = format_sv_memory(num_qubits);
291
292    CircuitSummary {
293        num_qubits,
294        depth,
295        total_gates,
296        clifford_count,
297        non_clifford_count,
298        measurement_count,
299        is_clifford_only: non_clifford_count == 0,
300        is_nearest_neighbor: is_nearest_neighbor(circuit),
301        estimated_bond_dim: estimate_bond_dimension(circuit),
302        state_vector_memory,
303    }
304}
305
306/// Format the state-vector memory requirement for display.
307fn format_sv_memory(num_qubits: u32) -> String {
308    let bytes = (1u128 << num_qubits) * 16;
309    if bytes >= 1 << 40 {
310        format!("{:.1} TiB", bytes as f64 / (1u128 << 40) as f64)
311    } else if bytes >= 1 << 30 {
312        format!("{:.1} GiB", bytes as f64 / (1u128 << 30) as f64)
313    } else if bytes >= 1 << 20 {
314        format!("{:.1} MiB", bytes as f64 / (1u128 << 20) as f64)
315    } else {
316        format!("{} bytes", bytes)
317    }
318}
319
320// ---------------------------------------------------------------------------
321// Tests
322// ---------------------------------------------------------------------------
323
324#[cfg(test)]
325mod tests {
326    use super::*;
327    use crate::circuit::QuantumCircuit;
328
329    #[test]
330    fn classify_all_gate_types() {
331        assert_eq!(classify_gate(&Gate::H(0)), GateClass::Clifford);
332        assert_eq!(classify_gate(&Gate::X(0)), GateClass::Clifford);
333        assert_eq!(classify_gate(&Gate::Y(0)), GateClass::Clifford);
334        assert_eq!(classify_gate(&Gate::Z(0)), GateClass::Clifford);
335        assert_eq!(classify_gate(&Gate::S(0)), GateClass::Clifford);
336        assert_eq!(classify_gate(&Gate::Sdg(0)), GateClass::Clifford);
337        assert_eq!(classify_gate(&Gate::CNOT(0, 1)), GateClass::Clifford);
338        assert_eq!(classify_gate(&Gate::CZ(0, 1)), GateClass::Clifford);
339        assert_eq!(classify_gate(&Gate::SWAP(0, 1)), GateClass::Clifford);
340
341        assert_eq!(classify_gate(&Gate::T(0)), GateClass::NonClifford);
342        assert_eq!(classify_gate(&Gate::Tdg(0)), GateClass::NonClifford);
343        assert_eq!(classify_gate(&Gate::Rx(0, 1.0)), GateClass::NonClifford);
344        assert_eq!(classify_gate(&Gate::Ry(0, 1.0)), GateClass::NonClifford);
345        assert_eq!(classify_gate(&Gate::Rz(0, 1.0)), GateClass::NonClifford);
346        assert_eq!(classify_gate(&Gate::Phase(0, 1.0)), GateClass::NonClifford);
347        assert_eq!(classify_gate(&Gate::Rzz(0, 1, 1.0)), GateClass::NonClifford);
348
349        assert_eq!(classify_gate(&Gate::Measure(0)), GateClass::Measurement);
350        assert_eq!(classify_gate(&Gate::Reset(0)), GateClass::Reset);
351        assert_eq!(classify_gate(&Gate::Barrier), GateClass::Barrier);
352    }
353
354    #[test]
355    fn clifford_circuit_detection() {
356        let mut circ = QuantumCircuit::new(4);
357        circ.h(0).cnot(0, 1).s(2).cz(2, 3).measure(0);
358        assert!(is_clifford_circuit(&circ));
359
360        circ.t(0);
361        assert!(!is_clifford_circuit(&circ));
362    }
363
364    #[test]
365    fn non_clifford_count() {
366        let mut circ = QuantumCircuit::new(3);
367        circ.h(0).t(0).t(1).rx(2, 0.5);
368        assert_eq!(count_non_clifford(&circ), 3);
369    }
370
371    #[test]
372    fn entanglement_pair_tracking() {
373        let mut circ = QuantumCircuit::new(5);
374        circ.cnot(0, 3).cz(1, 4).swap(0, 3);
375        let pairs = entanglement_pairs(&circ);
376        assert!(pairs.contains(&(0, 3)));
377        assert!(pairs.contains(&(1, 4)));
378        // Duplicate pair (0,3) should not increase count.
379        assert_eq!(pairs.len(), 2);
380    }
381
382    #[test]
383    fn nearest_neighbor_detection() {
384        let mut circ = QuantumCircuit::new(4);
385        circ.cnot(0, 1).cnot(1, 2).cnot(2, 3);
386        assert!(is_nearest_neighbor(&circ));
387
388        circ.cnot(0, 3);
389        assert!(!is_nearest_neighbor(&circ));
390    }
391
392    #[test]
393    fn bond_dimension_empty_circuit() {
394        let circ = QuantumCircuit::new(5);
395        assert_eq!(estimate_bond_dimension(&circ), 1);
396    }
397
398    #[test]
399    fn bond_dimension_linear_chain() {
400        let mut circ = QuantumCircuit::new(4);
401        // Single CNOT across cut at position 2: only one gate crosses.
402        circ.cnot(1, 2);
403        // Expected: 2^1 = 2
404        assert_eq!(estimate_bond_dimension(&circ), 2);
405    }
406
407    #[test]
408    fn bond_dimension_multiple_crossings() {
409        let mut circ = QuantumCircuit::new(4);
410        // Three gates cross the cut between qubit 1 and qubit 2.
411        circ.cnot(0, 2).cnot(1, 3).cnot(0, 3);
412        // Cut at position 2: all three gates cross -> 2^3 = 8
413        assert_eq!(estimate_bond_dimension(&circ), 8);
414    }
415
416    #[test]
417    fn summary_basic() {
418        let mut circ = QuantumCircuit::new(4);
419        circ.h(0).t(1).cnot(0, 1).measure(0).measure(1);
420        let summary = summarize_circuit(&circ);
421
422        assert_eq!(summary.num_qubits, 4);
423        assert_eq!(summary.total_gates, 5);
424        assert_eq!(summary.clifford_count, 2); // H + CNOT
425        assert_eq!(summary.non_clifford_count, 1); // T
426        assert_eq!(summary.measurement_count, 2);
427        assert!(!summary.is_clifford_only);
428        assert!(summary.is_nearest_neighbor);
429    }
430
431    #[test]
432    fn summary_clifford_only_flag() {
433        let mut circ = QuantumCircuit::new(2);
434        circ.h(0).cnot(0, 1);
435        let summary = summarize_circuit(&circ);
436        assert!(summary.is_clifford_only);
437    }
438
439    #[test]
440    fn summary_memory_string() {
441        let circ = QuantumCircuit::new(10);
442        let summary = summarize_circuit(&circ);
443        // 2^10 * 16 = 16384 bytes
444        assert_eq!(summary.state_vector_memory, "16384 bytes");
445    }
446}
ruqu_core/circuit_analyzer.rs

ruqu_core/
circuit_analyzer.rs
