Skip to main content

faultscope_core/
dem.rs

1use std::collections::{HashMap, HashSet};
2use std::sync::{Arc, OnceLock};
3
4mod assembly;
5mod bitset;
6mod event_plan;
7mod fallback_path;
8mod indexed_parity;
9mod measurement_plan;
10mod product_path;
11
12use assembly::{
13    assemble_dem_edge_refs, coalesce_sibling_dem_edge_refs, materialize_generated_dem_edges,
14    DemFlipMasks,
15};
16use event_plan::collect_dem_event_plan_from_program_with_options;
17pub use event_plan::{
18    collect_dem_event_plan, collect_dem_event_plan_with_options, DemEventPlan, DemGenerationOptions,
19};
20use fallback_path::generate_fallback_dem_flip_masks_from_plan;
21use measurement_plan::{
22    compile_dem_measurement_plan, compile_dem_measurement_plan_with_optional_declarations,
23    DemMeasurementPlan,
24};
25use product_path::{
26    generate_indexed_product_dem_flip_masks_from_plan, supports_product_reference_fast_path,
27};
28
29use crate::dem_canonical::parity_support_len;
30use crate::dem_problem::{compile_graphlike_problem_from_edge_views, GraphlikeSourceEdge};
31use crate::dem_sampling::{DemHotspotEstimator, DemProgramEdge, DemProgramEdgeMetadata};
32use crate::program::{ExpandedOperation, ExpandedProgram, ExpansionMode};
33use crate::{
34    Circuit, Detector, DetectorErrorEdge, DetectorErrorModel, GraphlikeDecodingProblem,
35    LogicalObservable, NpError, NpResult, Operation,
36};
37
38/// Detector error model generator based on single-error propagation.
39///
40/// The generator is pure Rust core logic. It can infer detector and observable
41/// declarations from circuit operations or use declarations supplied by the
42/// caller.
43#[derive(Debug, Clone, PartialEq)]
44pub struct DetectorErrorModelGenerator {
45    pub circuit: Arc<Circuit>,
46    pub detectors: Vec<Detector>,
47    pub observables: Vec<LogicalObservable>,
48    event_plan: Arc<DemEventPlan>,
49    measurement_plan: DemMeasurementPlan,
50}
51
52/// A circuit whose targets have been validated and whose DEM event plan is
53/// guaranteed to be derived from that exact circuit.
54///
55/// This type is intentionally opaque.  It lets trusted adapters carry the
56/// validation result across API boundaries without allowing callers to pair a
57/// circuit with an unrelated event plan.
58#[doc(hidden)]
59#[derive(Debug)]
60pub struct ValidatedDemCircuit {
61    circuit: Arc<Circuit>,
62    event_plan: OnceLock<Arc<DemEventPlan>>,
63}
64
65impl ValidatedDemCircuit {
66    /// Validate a circuit once and retain it for DEM compilation.
67    #[doc(hidden)]
68    pub fn new(circuit: Circuit) -> NpResult<Self> {
69        circuit.validate()?;
70        Ok(Self {
71            circuit: Arc::new(circuit),
72            event_plan: OnceLock::new(),
73        })
74    }
75
76    /// Borrow the validated circuit.
77    #[doc(hidden)]
78    pub fn circuit(&self) -> &Circuit {
79        &self.circuit
80    }
81
82    /// Return shared ownership of the validated circuit.
83    fn shared_circuit(&self) -> Arc<Circuit> {
84        Arc::clone(&self.circuit)
85    }
86
87    /// Return the event plan derived from this circuit, compiling it once.
88    #[doc(hidden)]
89    pub fn event_plan(&self) -> NpResult<Arc<DemEventPlan>> {
90        if let Some(event_plan) = self.event_plan.get() {
91            return Ok(Arc::clone(event_plan));
92        }
93
94        let event_plan = Arc::new(collect_dem_event_plan(&self.circuit.operations)?);
95        let _ = self.event_plan.set(event_plan);
96        Ok(Arc::clone(
97            self.event_plan
98                .get()
99                .expect("DEM event plan must be initialized after set"),
100        ))
101    }
102
103    /// Return an event plan compiled with explicit disjoint-channel options.
104    #[doc(hidden)]
105    pub fn event_plan_with_options(
106        &self,
107        options: DemGenerationOptions,
108    ) -> NpResult<Arc<DemEventPlan>> {
109        if options == DemGenerationOptions::default() {
110            return self.event_plan();
111        }
112        Ok(Arc::new(collect_dem_event_plan_with_options(
113            &self.circuit.operations,
114            options,
115        )?))
116    }
117}
118
119impl DemEventPlan {
120    /// Materialize public detector declarations from the indexed IR.
121    #[doc(hidden)]
122    pub fn inferred_detectors(&self) -> Vec<Detector> {
123        detectors_from_program(&self.program)
124    }
125
126    /// Materialize public observable declarations from the indexed IR.
127    #[doc(hidden)]
128    pub fn inferred_observables(&self) -> Vec<LogicalObservable> {
129        observables_from_program(&self.program)
130    }
131}
132
133impl DetectorErrorModelGenerator {
134    /// Create a generator for `circuit`.
135    ///
136    /// If `detectors` or `observables` are `None`, declarations are inferred
137    /// from `Operation::Detector` and `Operation::ObservableInclude` entries in
138    /// the circuit.
139    pub fn new(
140        circuit: Circuit,
141        detectors: Option<Vec<Detector>>,
142        observables: Option<Vec<LogicalObservable>>,
143    ) -> NpResult<Self> {
144        Self::new_with_options(
145            circuit,
146            detectors,
147            observables,
148            DemGenerationOptions::default(),
149        )
150    }
151
152    /// Create a generator with explicit disjoint-channel handling options.
153    pub fn new_with_options(
154        circuit: Circuit,
155        detectors: Option<Vec<Detector>>,
156        observables: Option<Vec<LogicalObservable>>,
157        options: DemGenerationOptions,
158    ) -> NpResult<Self> {
159        circuit.validate()?;
160        let (circuit, program) = crate::program::expand_circuit(&circuit)?;
161        let measurement_plan = compile_dem_measurement_plan_with_optional_declarations(
162            &program,
163            detectors.as_deref(),
164            observables.as_deref(),
165        )?;
166        let detectors = detectors.unwrap_or_else(|| detectors_from_program(&program));
167        let observables = observables.unwrap_or_else(|| observables_from_program(&program));
168        validate_detector_ids(&detectors)?;
169        validate_observable_ids(&observables)?;
170        validate_observables_for_n_qubits(circuit.n_qubits, &observables)?;
171        let event_plan = collect_dem_event_plan_from_program_with_options(program, options)?;
172        Ok(Self {
173            circuit: Arc::new(circuit),
174            detectors,
175            observables,
176            event_plan: Arc::new(event_plan),
177            measurement_plan,
178        })
179    }
180
181    /// Create a generator using a precompiled event plan for this circuit.
182    pub fn new_with_event_plan(
183        circuit: Circuit,
184        detectors: Vec<Detector>,
185        observables: Vec<LogicalObservable>,
186        event_plan: DemEventPlan,
187    ) -> NpResult<Self> {
188        Self::new_with_shared_event_plan(
189            Arc::new(circuit),
190            detectors,
191            observables,
192            Arc::new(event_plan),
193        )
194    }
195
196    /// Create a generator using shared circuit and event-plan ownership.
197    pub fn new_with_shared_event_plan(
198        circuit: Arc<Circuit>,
199        detectors: Vec<Detector>,
200        observables: Vec<LogicalObservable>,
201        event_plan: Arc<DemEventPlan>,
202    ) -> NpResult<Self> {
203        Self::new_with_shared_event_plan_options(
204            circuit,
205            Some(detectors),
206            Some(observables),
207            event_plan,
208        )
209    }
210
211    /// Create a generator from a shared integer event plan, inferring omitted
212    /// declarations directly from that plan without a string round trip.
213    #[doc(hidden)]
214    pub fn new_with_shared_event_plan_options(
215        circuit: Arc<Circuit>,
216        detectors: Option<Vec<Detector>>,
217        observables: Option<Vec<LogicalObservable>>,
218        event_plan: Arc<DemEventPlan>,
219    ) -> NpResult<Self> {
220        circuit.validate()?;
221        crate::program::validate_expanded_program_targets(circuit.n_qubits, &event_plan.program)?;
222        Self::new_with_prevalidated_shared_event_plan_options(
223            circuit,
224            detectors,
225            observables,
226            event_plan,
227        )
228    }
229
230    /// Create a generator from a circuit carrying proof that validation and
231    /// event-plan binding have already been performed.
232    #[doc(hidden)]
233    pub fn new_with_validated_dem_circuit_options(
234        circuit: &ValidatedDemCircuit,
235        detectors: Option<Vec<Detector>>,
236        observables: Option<Vec<LogicalObservable>>,
237    ) -> NpResult<Self> {
238        Self::new_with_validated_dem_circuit_generation_options(
239            circuit,
240            detectors,
241            observables,
242            DemGenerationOptions::default(),
243        )
244    }
245
246    /// Create a generator from a validated circuit with explicit
247    /// disjoint-channel handling options.
248    #[doc(hidden)]
249    pub fn new_with_validated_dem_circuit_generation_options(
250        circuit: &ValidatedDemCircuit,
251        detectors: Option<Vec<Detector>>,
252        observables: Option<Vec<LogicalObservable>>,
253        options: DemGenerationOptions,
254    ) -> NpResult<Self> {
255        let event_plan = circuit.event_plan_with_options(options)?;
256        Self::new_with_prevalidated_shared_event_plan_options(
257            circuit.shared_circuit(),
258            detectors,
259            observables,
260            event_plan,
261        )
262    }
263
264    fn new_with_prevalidated_shared_event_plan_options(
265        circuit: Arc<Circuit>,
266        detectors: Option<Vec<Detector>>,
267        observables: Option<Vec<LogicalObservable>>,
268        event_plan: Arc<DemEventPlan>,
269    ) -> NpResult<Self> {
270        let measurement_plan = compile_dem_measurement_plan_with_optional_declarations(
271            &event_plan.program,
272            detectors.as_deref(),
273            observables.as_deref(),
274        )?;
275        let detectors = detectors.unwrap_or_else(|| detectors_from_program(&event_plan.program));
276        let observables =
277            observables.unwrap_or_else(|| observables_from_program(&event_plan.program));
278        validate_detector_ids(&detectors)?;
279        validate_observable_ids(&observables)?;
280        validate_observables_for_n_qubits(circuit.n_qubits, &observables)?;
281        Ok(Self {
282            circuit,
283            detectors,
284            observables,
285            event_plan,
286            measurement_plan,
287        })
288    }
289
290    /// Generate a typed detector error model.
291    pub fn generate(&self) -> NpResult<DetectorErrorModel> {
292        Ok(self.generate_lazy()?.materialize())
293    }
294
295    /// Generate detector/observable edge structure while deferring metadata clones.
296    pub fn generate_lazy(&self) -> NpResult<LazyDetectorErrorModel> {
297        let edges = self.generate_edge_refs()?;
298        let (edges, edge_overrides) = coalesce_sibling_dem_edge_refs(&self.event_plan, edges);
299        Ok(LazyDetectorErrorModel {
300            detectors: self.detectors.clone(),
301            observables: self.observables.clone(),
302            event_plan: self.event_plan.clone(),
303            edges,
304            edge_overrides,
305        })
306    }
307
308    fn generate_edge_refs(&self) -> NpResult<Vec<GeneratedDemEdgeRef>> {
309        // Constructors validate the circuit, compiled plan, and observables.
310        // Keep repeated generation scan-free so validation remains a boundary
311        // cost instead of scaling with every generated model.
312        generate_dem_edge_refs_from_compiled_plan(
313            self.circuit.n_qubits,
314            &self.event_plan.program,
315            &self.measurement_plan,
316            &self.event_plan,
317        )
318    }
319}
320
321pub fn generate_dem_edges(
322    n_qubits: usize,
323    operations: &[Operation],
324    detectors: &[Detector],
325    observables: &[LogicalObservable],
326) -> NpResult<Vec<DetectorErrorEdge>> {
327    generate_dem_edges_with_options(
328        n_qubits,
329        operations,
330        detectors,
331        observables,
332        DemGenerationOptions::default(),
333    )
334}
335
336/// Generate DEM edges with explicit disjoint-channel handling options.
337pub fn generate_dem_edges_with_options(
338    n_qubits: usize,
339    operations: &[Operation],
340    detectors: &[Detector],
341    observables: &[LogicalObservable],
342    options: DemGenerationOptions,
343) -> NpResult<Vec<DetectorErrorEdge>> {
344    crate::model::validate_operations(n_qubits, operations)?;
345    validate_observables_for_n_qubits(n_qubits, observables)?;
346    let program = crate::program::expand_operations(operations, ExpansionMode::Dem)?;
347    let event_plan = collect_dem_event_plan_from_program_with_options(program, options)?;
348    let measurement_plan =
349        compile_dem_measurement_plan(&event_plan.program, detectors, observables)?;
350    generate_dem_edges_from_compiled_plan(
351        n_qubits,
352        &event_plan.program,
353        &measurement_plan,
354        &event_plan,
355    )
356}
357
358/// Generate DEM edges from a precompiled integer event plan.
359pub fn generate_dem_edges_from_event_plan(
360    n_qubits: usize,
361    detectors: &[Detector],
362    observables: &[LogicalObservable],
363    event_plan: &DemEventPlan,
364) -> NpResult<Vec<DetectorErrorEdge>> {
365    crate::program::validate_expanded_program_targets(n_qubits, &event_plan.program)?;
366    validate_observables_for_n_qubits(n_qubits, observables)?;
367    let measurement_plan =
368        compile_dem_measurement_plan(&event_plan.program, detectors, observables)?;
369    generate_dem_edges_from_compiled_plan(
370        n_qubits,
371        &event_plan.program,
372        &measurement_plan,
373        event_plan,
374    )
375}
376
377fn generate_dem_edges_from_compiled_plan(
378    n_qubits: usize,
379    program: &ExpandedProgram,
380    measurement_plan: &DemMeasurementPlan,
381    event_plan: &DemEventPlan,
382) -> NpResult<Vec<DetectorErrorEdge>> {
383    let edges =
384        generate_dem_edge_refs_from_compiled_plan(n_qubits, program, measurement_plan, event_plan)?;
385    let (edges, edge_overrides) = coalesce_sibling_dem_edge_refs(event_plan, edges);
386    Ok(materialize_generated_dem_edges(
387        event_plan,
388        edges,
389        &edge_overrides,
390    ))
391}
392
393fn generate_dem_edge_refs_from_compiled_plan(
394    n_qubits: usize,
395    program: &ExpandedProgram,
396    measurement_plan: &DemMeasurementPlan,
397    event_plan: &DemEventPlan,
398) -> NpResult<Vec<GeneratedDemEdgeRef>> {
399    let flip_masks = generate_dem_flip_masks_from_compiled_plan(
400        n_qubits,
401        program,
402        measurement_plan,
403        event_plan,
404    )?;
405    Ok(assemble_dem_edge_refs(
406        event_plan.fault_events.len(),
407        flip_masks,
408    ))
409}
410
411fn generate_dem_flip_masks_from_compiled_plan(
412    n_qubits: usize,
413    program: &ExpandedProgram,
414    measurement_plan: &DemMeasurementPlan,
415    event_plan: &DemEventPlan,
416) -> NpResult<DemFlipMasks> {
417    if supports_product_reference_fast_path(n_qubits, &program.operations) {
418        return generate_indexed_product_dem_flip_masks_from_plan(
419            n_qubits,
420            &program.operations,
421            measurement_plan,
422            event_plan,
423        );
424    }
425    generate_fallback_dem_flip_masks_from_plan(
426        n_qubits,
427        &program.operations,
428        measurement_plan,
429        event_plan,
430    )
431}
432
433/// Infer detector declarations from detector operations in a circuit.
434pub fn detectors_from_circuit(circuit: &Circuit) -> Vec<Detector> {
435    let program = match crate::program::expand_operations(&circuit.operations, ExpansionMode::Dem) {
436        Ok(program) => program,
437        Err(_) => return Vec::new(),
438    };
439    detectors_from_program(&program)
440}
441
442fn detectors_from_program(program: &ExpandedProgram) -> Vec<Detector> {
443    let mut detectors = Vec::new();
444    let mut detector_coords = program.detector_coords.iter();
445    for operation in &program.operations {
446        let ExpandedOperation::Detector {
447            detector_id,
448            measurement_ids,
449        } = operation
450        else {
451            continue;
452        };
453        detectors.push(Detector {
454            id: *detector_id,
455            measurement_keys: measurement_ids
456                .iter()
457                .map(|measurement_id| program.measurement_keys[*measurement_id].clone())
458                .collect(),
459            coords: detector_coords.next().cloned().unwrap_or_default(),
460        });
461    }
462    detectors
463}
464
465/// Infer logical observable declarations from observable include operations.
466pub fn observables_from_circuit(circuit: &Circuit) -> Vec<LogicalObservable> {
467    let program = match crate::program::expand_operations(&circuit.operations, ExpansionMode::Dem) {
468        Ok(program) => program,
469        Err(_) => return Vec::new(),
470    };
471    observables_from_program(&program)
472}
473
474fn observables_from_program(program: &ExpandedProgram) -> Vec<LogicalObservable> {
475    let mut measurement_ids_by_observable = HashMap::<i64, Vec<usize>>::new();
476    for operation in &program.operations {
477        let ExpandedOperation::ObservableInclude {
478            observable_id,
479            measurement_ids,
480        } = operation
481        else {
482            continue;
483        };
484        measurement_ids_by_observable
485            .entry(*observable_id)
486            .or_default()
487            .extend(measurement_ids);
488    }
489    let mut observable_ids = measurement_ids_by_observable
490        .keys()
491        .copied()
492        .collect::<Vec<_>>();
493    observable_ids.sort_unstable();
494    observable_ids
495        .into_iter()
496        .map(|observable_id| LogicalObservable {
497            id: observable_id,
498            measurement_keys: measurement_ids_by_observable
499                .remove(&observable_id)
500                .unwrap_or_default()
501                .into_iter()
502                .map(|measurement_id| program.measurement_keys[measurement_id].clone())
503                .collect(),
504            pauli_qubits: Vec::new(),
505            pauli: String::new(),
506        })
507        .collect()
508}
509
510fn validate_detector_ids(detectors: &[Detector]) -> NpResult<()> {
511    let mut seen = HashSet::new();
512    for detector in detectors {
513        if !seen.insert(detector.id) {
514            return Err(NpError::new("detector ids must be unique"));
515        }
516    }
517    Ok(())
518}
519
520fn validate_observable_ids(observables: &[LogicalObservable]) -> NpResult<()> {
521    let mut seen = HashSet::new();
522    for observable in observables {
523        if !seen.insert(observable.id) {
524            return Err(NpError::new("logical observable ids must be unique"));
525        }
526    }
527    Ok(())
528}
529
530fn validate_observables_for_n_qubits(
531    n_qubits: usize,
532    observables: &[LogicalObservable],
533) -> NpResult<()> {
534    for observable in observables {
535        observable.validate_for_n_qubits(n_qubits)?;
536    }
537    Ok(())
538}
539
540#[derive(Debug, Clone, PartialEq)]
541struct GeneratedDemEdgeRef {
542    event_index: usize,
543    detectors: Vec<i64>,
544    observables: Vec<i64>,
545}
546
547#[derive(Debug, Clone, PartialEq)]
548struct GeneratedDemEdgeOverride {
549    probability: f64,
550    event: crate::DemEvent,
551}
552
553#[derive(Debug, Clone, PartialEq)]
554pub struct LazyDetectorErrorModel {
555    pub detectors: Vec<Detector>,
556    pub observables: Vec<LogicalObservable>,
557    pub event_plan: Arc<DemEventPlan>,
558    edges: Vec<GeneratedDemEdgeRef>,
559    edge_overrides: HashMap<usize, GeneratedDemEdgeOverride>,
560}
561
562impl LazyDetectorErrorModel {
563    /// Test whether parity-reduced lazy DEM edges satisfy graphlike constraints.
564    pub fn is_graphlike(&self) -> bool {
565        self.edges.iter().all(|edge| {
566            let detector_count = parity_support_len(&edge.detectors);
567            detector_count <= 2
568                && (detector_count != 0 || parity_support_len(&edge.observables) == 0)
569        })
570    }
571
572    /// Compile directly into the compact graphlike representation without
573    /// materializing location labels, events, or tag dictionaries.
574    pub fn compile_graphlike_problem(&self) -> NpResult<GraphlikeDecodingProblem> {
575        compile_graphlike_problem_from_edge_views(
576            &self.detectors,
577            &self.observables,
578            self.edges.len(),
579            || {
580                self.edges
581                    .iter()
582                    .enumerate()
583                    .map(|(edge_index, edge)| GraphlikeSourceEdge {
584                        probability: self
585                            .edge_overrides
586                            .get(&edge_index)
587                            .map(|override_| override_.probability)
588                            .unwrap_or(self.event_plan.fault_events[edge.event_index].probability),
589                        detectors: &edge.detectors,
590                        observables: &edge.observables,
591                        original_edge_index: edge_index,
592                    })
593            },
594        )
595    }
596
597    /// Consume a lazy DEM into the metadata-free sampling representation.
598    #[doc(hidden)]
599    pub fn into_sampling_estimator(self) -> DemHotspotEstimator {
600        let Self {
601            detectors,
602            observables,
603            event_plan,
604            edges,
605            edge_overrides,
606        } = self;
607        let program_edges = edges
608            .into_iter()
609            .enumerate()
610            .map(|(edge_index, edge)| DemProgramEdge {
611                probability: edge_overrides
612                    .get(&edge_index)
613                    .map(|override_| override_.probability)
614                    .unwrap_or(event_plan.fault_events[edge.event_index].probability),
615                detectors: edge.detectors,
616                observables: edge.observables,
617            })
618            .collect();
619        DemHotspotEstimator::from_compact_sampling_parts(
620            detectors.into_iter().map(|detector| detector.id).collect(),
621            observables
622                .into_iter()
623                .map(|observable| observable.id)
624                .collect(),
625            program_edges,
626        )
627    }
628
629    /// Compile the lazy integer DEM directly into a sampler without
630    /// materializing location labels or tag dictionaries.
631    pub fn compile_hotspot_estimator(&self) -> DemHotspotEstimator {
632        let mut edges = Vec::with_capacity(self.edges.len());
633        let mut edge_metadata = Vec::with_capacity(self.edges.len());
634        for (edge_index, edge) in self.edges.iter().enumerate() {
635            let event = &self.event_plan.fault_events[edge.event_index];
636            let location = &self.event_plan.program.noise_locations[event.noise_id];
637            edges.push(DemProgramEdge {
638                probability: self
639                    .edge_overrides
640                    .get(&edge_index)
641                    .map(|override_| override_.probability)
642                    .unwrap_or(event.probability),
643                detectors: edge.detectors.clone(),
644                observables: edge.observables.clone(),
645            });
646            edge_metadata.push(DemProgramEdgeMetadata {
647                location_id: location.location_id,
648                event: self
649                    .edge_overrides
650                    .get(&edge_index)
651                    .map(|override_| override_.event.clone())
652                    .unwrap_or_else(|| event.event.clone()),
653            });
654        }
655        DemHotspotEstimator::from_program_parts(
656            self.detectors.iter().map(|detector| detector.id).collect(),
657            self.observables
658                .iter()
659                .map(|observable| observable.id)
660                .collect(),
661            edges,
662            edge_metadata,
663            self.event_plan.program.location_catalog.clone(),
664        )
665    }
666
667    pub fn materialize(&self) -> DetectorErrorModel {
668        DetectorErrorModel {
669            detectors: self.detectors.clone(),
670            observables: self.observables.clone(),
671            edges: self
672                .edges
673                .iter()
674                .enumerate()
675                .map(|(edge_index, edge)| {
676                    let event = &self.event_plan.fault_events[edge.event_index];
677                    let location = &self.event_plan.program.noise_locations[event.noise_id];
678                    let catalog = &self.event_plan.program.location_catalog;
679                    DetectorErrorEdge {
680                        probability: self
681                            .edge_overrides
682                            .get(&edge_index)
683                            .map(|override_| override_.probability)
684                            .unwrap_or(event.probability),
685                        detectors: edge.detectors.clone(),
686                        observables: edge.observables.clone(),
687                        location_id: catalog.label(location.location_id).to_string(),
688                        event: self
689                            .edge_overrides
690                            .get(&edge_index)
691                            .map(|override_| override_.event.clone())
692                            .unwrap_or_else(|| event.event.clone()),
693                        tags: catalog.tags(location.location_id).clone(),
694                    }
695                })
696                .collect(),
697        }
698    }
699}
700
701#[cfg(test)]
702mod tests;