1use std::collections::HashMap;
2use std::sync::Arc;
3
4use crate::dem_canonical::{canonical_id_order, parity_canonicalize};
5use crate::labels::LocationCatalogBuilder;
6use crate::{
7 convert_detector_batch, for_each_bernoulli_event, packed_corrections_to_masks,
8 validate_decoder_detector_ids, validate_decoder_observable_ids, word_count,
9 CorrectionMaskBatch, DemBatch, DemEvent, DemHotspotEstimate, DemLocationGroup, DetectorBatch,
10 DetectorBatchFormat, DetectorBatchView, DetectorErrorEdge, DetectorErrorModel, LocationCatalog,
11 LocationId, Mask, NpError, NpResult, PackedObservableShotBatch, SmallRng,
12};
13
14#[derive(Debug, Clone, PartialEq)]
15pub(crate) struct DemProgramEdge {
16 pub(crate) probability: f64,
17 pub(crate) detectors: Vec<i64>,
18 pub(crate) observables: Vec<i64>,
19}
20
21#[derive(Debug, Clone, PartialEq)]
22pub(crate) struct DemProgramEdgeMetadata {
23 pub(crate) location_id: LocationId,
24 pub(crate) event: DemEvent,
25}
26
27#[derive(Debug, Clone, PartialEq)]
28pub(crate) struct DemProgramLocationGroup {
29 pub(crate) location_id: LocationId,
30 pub(crate) edge_indices: Vec<usize>,
31 pub(crate) total_probability: f64,
32}
33
34struct CompiledDemEdges {
35 edges: Vec<DemProgramEdge>,
36 metadata: Option<Vec<DemProgramEdgeMetadata>>,
37 catalog: LocationCatalog,
38 location_groups: Vec<DemProgramLocationGroup>,
39}
40
41#[derive(Debug, Clone, PartialEq)]
47pub struct DemHotspotEstimator {
48 pub detector_ids: Vec<i64>,
53 pub observable_ids: Vec<i64>,
58 canonical_detector_ids: Arc<[i64]>,
59 canonical_observable_ids: Arc<[i64]>,
60 edges: Vec<DemProgramEdge>,
61 edge_metadata: Option<Vec<DemProgramEdgeMetadata>>,
62 location_catalog: LocationCatalog,
63 location_groups: Vec<DemProgramLocationGroup>,
64 hotspot_layout_identity: Arc<()>,
65}
66
67#[derive(Debug, Clone, PartialEq)]
68pub struct PackedDemShotBatch {
69 pub shots: usize,
70 pub detector_data: Vec<u8>,
71 pub detector_byte_count: usize,
72 pub observable_ids: Vec<i64>,
73 pub observable_data: Vec<u8>,
74 pub observable_byte_count: usize,
75}
76
77#[derive(Debug, Clone, PartialEq)]
78pub struct DetectorEventDemShotBatch {
79 pub shots: usize,
80 pub offsets: Vec<usize>,
81 pub events: Vec<usize>,
82 pub observable_ids: Vec<i64>,
83 pub observable_data: Vec<u8>,
84 pub observable_byte_count: usize,
85}
86
87#[derive(Debug, Clone, PartialEq)]
89pub struct DemAttributionTrace {
90 shots: usize,
91 edge_event_masks: Vec<Mask>,
92 sampler_identity: Arc<()>,
93}
94
95impl DemAttributionTrace {
96 pub fn shots(&self) -> usize {
97 self.shots
98 }
99
100 pub fn edge_event_masks(&self) -> &[Mask] {
101 &self.edge_event_masks
102 }
103
104 fn matches_sampler(&self, identity: &Arc<()>) -> bool {
105 Arc::ptr_eq(&self.sampler_identity, identity)
106 }
107}
108
109#[derive(Debug, Clone, PartialEq)]
111pub enum DemObservableBatch {
112 Masks(CorrectionMaskBatch),
113 Packed(PackedObservableShotBatch),
114}
115
116impl DemObservableBatch {
117 pub fn observable_ids(&self) -> &[i64] {
118 match self {
119 Self::Masks(batch) => &batch.observable_ids,
120 Self::Packed(batch) => &batch.observable_ids,
121 }
122 }
123
124 pub fn shots(&self) -> usize {
125 match self {
126 Self::Masks(batch) => batch.shots,
127 Self::Packed(batch) => batch.shots,
128 }
129 }
130
131 pub fn as_masks(&self) -> NpResult<CorrectionMaskBatch> {
132 match self {
133 Self::Masks(batch) => Ok(batch.clone()),
134 Self::Packed(batch) => packed_corrections_to_masks(batch.clone()),
135 }
136 }
137
138 pub fn as_packed(&self) -> NpResult<PackedObservableShotBatch> {
139 match self {
140 Self::Masks(batch) => crate::mask_corrections_to_packed(batch.clone()),
141 Self::Packed(batch) => Ok(batch.clone()),
142 }
143 }
144}
145
146#[derive(Debug, Clone, PartialEq)]
148pub struct DemSamplingResult {
149 syndrome: DetectorBatch,
150 observables: DemObservableBatch,
151 detail_detector_ids: Vec<i64>,
152 detail_detector_masks: Vec<Mask>,
153 all_mask: Mask,
154 attribution: Option<DemAttributionTrace>,
155 sampler_identity: Arc<()>,
156}
157
158impl DemSamplingResult {
159 pub fn shots(&self) -> usize {
160 self.syndrome.shots()
161 }
162
163 pub fn syndrome(&self) -> DetectorBatchView<'_> {
164 self.syndrome.view()
165 }
166
167 pub fn syndrome_batch(&self) -> &DetectorBatch {
168 &self.syndrome
169 }
170
171 pub fn observables(&self) -> &DemObservableBatch {
172 &self.observables
173 }
174
175 pub fn detail_detector_ids(&self) -> &[i64] {
176 &self.detail_detector_ids
177 }
178
179 pub fn detail_detector_masks(&self) -> &[Mask] {
180 &self.detail_detector_masks
181 }
182
183 pub fn detector_detail_mask(&self, detector_id: i64) -> Option<&Mask> {
184 self.detail_detector_ids
185 .iter()
186 .position(|id| *id == detector_id)
187 .and_then(|index| self.detail_detector_masks.get(index))
188 }
189
190 pub fn all_mask(&self) -> &Mask {
191 &self.all_mask
192 }
193
194 pub fn attribution(&self) -> Option<&DemAttributionTrace> {
195 self.attribution.as_ref()
196 }
197
198 pub fn into_dem_batch(self) -> NpResult<DemBatch> {
199 let masks = convert_detector_batch(self.syndrome.view(), DetectorBatchFormat::Masks)?;
200 let DetectorBatch::Masks {
201 detector_ids,
202 masks,
203 shots,
204 } = masks
205 else {
206 unreachable!("Masks conversion returns Masks storage")
207 };
208 let detectors = detector_ids.into_iter().zip(masks).collect();
209 let observable_masks = self.observables.as_masks()?;
210 let observables = observable_masks
211 .observable_ids
212 .into_iter()
213 .zip(observable_masks.masks)
214 .collect::<HashMap<_, _>>();
215 let mut loss_mask = Mask::zero(word_count(shots));
216 for observable in observables.values() {
217 loss_mask.or_assign(observable);
218 }
219 loss_mask.and_assign(&self.all_mask);
220 Ok(DemBatch::new(
221 shots,
222 self.all_mask,
223 detectors,
224 observables,
225 self.attribution.map(|trace| trace.edge_event_masks),
226 loss_mask,
227 self.sampler_identity,
228 ))
229 }
230}
231
232#[derive(Debug, Clone, PartialEq)]
237pub struct CompiledDemSamplingPlan {
238 detector_ids: Vec<i64>,
239 observable_ids: Vec<i64>,
240 format: DetectorBatchFormat,
241 detail_detector_ids: Vec<i64>,
242 record_attribution: bool,
243 sampler_identity: Arc<()>,
244 edges: Vec<CompiledSamplingEdge>,
245 detector_byte_count: usize,
246 observable_byte_count: usize,
247}
248
249#[derive(Debug, Clone, PartialEq)]
250struct CompiledSamplingEdge {
251 probability: f64,
252 detector_columns: Vec<usize>,
253 packed_detector_columns: Vec<(usize, u8)>,
254 detail_detector_columns: Vec<usize>,
255 observable_mask_columns: Vec<usize>,
256 observable_columns: Vec<(usize, u8)>,
257}
258
259#[derive(Debug, Clone, PartialEq)]
261pub struct CompiledDemLogicalCountPlan {
262 observable_ids: Vec<i64>,
263 edges: Vec<CompiledLogicalCountEdge>,
264 single_observable_flip_edge_count: usize,
265}
266
267#[derive(Debug, Clone, PartialEq)]
268struct CompiledLogicalCountEdge {
269 probability: f64,
270 observable_columns: Vec<usize>,
271 single_observable_flip: bool,
272}
273
274impl DemHotspotEstimator {
275 pub(crate) fn from_compact_sampling_parts(
276 detector_ids: Vec<i64>,
277 observable_ids: Vec<i64>,
278 edges: Vec<DemProgramEdge>,
279 ) -> Self {
280 let (detector_ids, observable_ids, edges) =
281 canonicalize_program_parts(detector_ids, observable_ids, edges)
282 .expect("generated DEM declarations must have unique ids");
283 Self {
284 canonical_detector_ids: Arc::from(detector_ids.as_slice()),
285 canonical_observable_ids: Arc::from(observable_ids.as_slice()),
286 detector_ids,
287 observable_ids,
288 edges,
289 edge_metadata: None,
290 location_catalog: LocationCatalog::default(),
291 location_groups: Vec::new(),
292 hotspot_layout_identity: Arc::new(()),
293 }
294 }
295
296 pub(crate) fn from_program_parts(
297 detector_ids: Vec<i64>,
298 observable_ids: Vec<i64>,
299 edges: Vec<DemProgramEdge>,
300 edge_metadata: Vec<DemProgramEdgeMetadata>,
301 location_catalog: LocationCatalog,
302 ) -> Self {
303 debug_assert_eq!(edges.len(), edge_metadata.len());
304 let (detector_ids, observable_ids, edges) =
305 canonicalize_program_parts(detector_ids, observable_ids, edges)
306 .expect("generated DEM declarations must have unique ids");
307 let location_groups =
308 build_dem_program_location_groups(&edges, &edge_metadata, location_catalog.len());
309 Self {
310 canonical_detector_ids: Arc::from(detector_ids.as_slice()),
311 canonical_observable_ids: Arc::from(observable_ids.as_slice()),
312 detector_ids,
313 observable_ids,
314 edges,
315 edge_metadata: Some(edge_metadata),
316 location_catalog,
317 location_groups,
318 hotspot_layout_identity: Arc::new(()),
319 }
320 }
321
322 pub fn new(dem: DetectorErrorModel) -> NpResult<Self> {
324 let detector_ids = dem.detectors.iter().map(|detector| detector.id).collect();
325 let observable_ids = dem
326 .observables
327 .iter()
328 .map(|observable| observable.id)
329 .collect();
330 Self::from_parts(detector_ids, observable_ids, dem.edges)
331 }
332
333 pub fn from_parts(
335 detector_ids: Vec<i64>,
336 observable_ids: Vec<i64>,
337 edges: Vec<DetectorErrorEdge>,
338 ) -> NpResult<Self> {
339 let compiled = compile_dem_edges(edges, true)?;
340 let (detector_ids, observable_ids, edges) =
341 canonicalize_program_parts(detector_ids, observable_ids, compiled.edges)?;
342 Ok(Self {
343 canonical_detector_ids: Arc::from(detector_ids.as_slice()),
344 canonical_observable_ids: Arc::from(observable_ids.as_slice()),
345 detector_ids,
346 observable_ids,
347 edges,
348 edge_metadata: compiled.metadata,
349 location_catalog: compiled.catalog,
350 location_groups: compiled.location_groups,
351 hotspot_layout_identity: Arc::new(()),
352 })
353 }
354
355 pub fn from_sampling_parts(
357 detector_ids: Vec<i64>,
358 observable_ids: Vec<i64>,
359 edges: Vec<DetectorErrorEdge>,
360 ) -> NpResult<Self> {
361 let compiled = compile_dem_edges(edges, false)?;
362 debug_assert!(compiled.metadata.is_none());
363 debug_assert!(compiled.catalog.is_empty());
364 let (detector_ids, observable_ids, edges) =
365 canonicalize_program_parts(detector_ids, observable_ids, compiled.edges)?;
366 Ok(Self {
367 canonical_detector_ids: Arc::from(detector_ids.as_slice()),
368 canonical_observable_ids: Arc::from(observable_ids.as_slice()),
369 detector_ids,
370 observable_ids,
371 edges,
372 edge_metadata: None,
373 location_catalog: LocationCatalog::default(),
374 location_groups: Vec::new(),
375 hotspot_layout_identity: Arc::new(()),
376 })
377 }
378
379 pub fn edge_count(&self) -> usize {
381 self.edges.len()
382 }
383
384 pub fn detector_ids(&self) -> &[i64] {
386 self.canonical_detector_ids.as_ref()
387 }
388
389 pub fn observable_ids(&self) -> &[i64] {
391 self.canonical_observable_ids.as_ref()
392 }
393
394 pub fn edge(&self, edge_index: usize) -> Option<DetectorErrorEdge> {
396 self.edges.get(edge_index).map(|edge| {
397 materialize_dem_edge(
398 edge,
399 self.edge_metadata
400 .as_ref()
401 .and_then(|metadata| metadata.get(edge_index)),
402 &self.location_catalog,
403 )
404 })
405 }
406
407 pub fn edges(&self) -> Vec<DetectorErrorEdge> {
409 self.edges
410 .iter()
411 .enumerate()
412 .map(|(edge_index, edge)| {
413 materialize_dem_edge(
414 edge,
415 self.edge_metadata
416 .as_ref()
417 .and_then(|metadata| metadata.get(edge_index)),
418 &self.location_catalog,
419 )
420 })
421 .collect()
422 }
423
424 pub fn location_groups(&self) -> Vec<DemLocationGroup> {
426 self.location_groups
427 .iter()
428 .map(|group| DemLocationGroup {
429 location_id: self.location_catalog.label(group.location_id).to_string(),
430 edge_indices: group.edge_indices.clone(),
431 total_probability: group.total_probability,
432 })
433 .collect()
434 }
435
436 pub fn run_batch(
438 &self,
439 shots: usize,
440 seed: Option<u64>,
441 return_edge_events: bool,
442 ) -> NpResult<DemBatch> {
443 if shots == 0 {
444 return Err(NpError::new("shots must be positive"));
445 }
446 let mut rng = SmallRng::new(seed.unwrap_or(0x95f2_04dc_4291_a715));
447 Ok(self.run_batch_with_rng(shots, &mut rng, return_edge_events))
448 }
449
450 pub fn run_batch_with_rng(
452 &self,
453 shots: usize,
454 rng: &mut SmallRng,
455 return_edge_events: bool,
456 ) -> DemBatch {
457 self.compile_decoder_sampling_plan(
458 self.detector_ids(),
459 self.observable_ids(),
460 DetectorBatchFormat::Masks,
461 &[],
462 return_edge_events,
463 )
464 .expect("canonical DEM layouts compile")
465 .run_sampling_result_with_rng(shots, rng)
466 .expect("canonical DEM sampling cannot fail")
467 .into_dem_batch()
468 .expect("canonical DEM batches materialize")
469 }
470
471 pub fn run_packed_shot_batch_with_rng(
472 &self,
473 shots: usize,
474 rng: &mut SmallRng,
475 detector_ids: &[i64],
476 observable_ids: &[i64],
477 ) -> NpResult<PackedDemShotBatch> {
478 Ok(self
479 .compile_sampling_plan(detector_ids, observable_ids)?
480 .run_packed_shot_batch_with_rng(shots, rng))
481 }
482
483 pub fn run_detector_event_shot_batch_with_rng(
484 &self,
485 shots: usize,
486 rng: &mut SmallRng,
487 detector_ids: &[i64],
488 observable_ids: &[i64],
489 ) -> NpResult<DetectorEventDemShotBatch> {
490 Ok(compile_dem_sampling_plan(DemSamplingPlanSpec {
491 sampling_detector_ids: self.detector_ids(),
492 sampling_observable_ids: self.observable_ids(),
493 edges: &self.edges,
494 detector_ids,
495 observable_ids,
496 format: DetectorBatchFormat::Events,
497 detail_detector_ids: &[],
498 record_attribution: false,
499 sampler_identity: &self.hotspot_layout_identity,
500 sampler_name: "detector-event DEM sampler",
501 })?
502 .run_detector_event_shot_batch_with_rng(shots, rng))
503 }
504
505 pub fn compile_sampling_plan(
507 &self,
508 detector_ids: &[i64],
509 observable_ids: &[i64],
510 ) -> NpResult<CompiledDemSamplingPlan> {
511 compile_dem_sampling_plan(DemSamplingPlanSpec {
512 sampling_detector_ids: self.detector_ids(),
513 sampling_observable_ids: self.observable_ids(),
514 edges: &self.edges,
515 detector_ids,
516 observable_ids,
517 format: DetectorBatchFormat::Packed,
518 detail_detector_ids: &[],
519 record_attribution: false,
520 sampler_identity: &self.hotspot_layout_identity,
521 sampler_name: "packed DEM sampler",
522 })
523 }
524
525 pub fn compile_decoder_sampling_plan(
527 &self,
528 detector_ids: &[i64],
529 observable_ids: &[i64],
530 format: DetectorBatchFormat,
531 detail_detector_ids: &[i64],
532 record_attribution: bool,
533 ) -> NpResult<CompiledDemSamplingPlan> {
534 compile_dem_sampling_plan(DemSamplingPlanSpec {
535 sampling_detector_ids: self.detector_ids(),
536 sampling_observable_ids: self.observable_ids(),
537 edges: &self.edges,
538 detector_ids,
539 observable_ids,
540 format,
541 detail_detector_ids,
542 record_attribution,
543 sampler_identity: &self.hotspot_layout_identity,
544 sampler_name: "decoder DEM sampler",
545 })
546 }
547
548 pub fn compile_logical_count_plan(&self) -> CompiledDemLogicalCountPlan {
550 CompiledDemLogicalCountPlan::new(self.observable_ids(), &self.edges)
551 }
552
553 pub fn estimate_default(
555 &self,
556 shots: usize,
557 seed: Option<u64>,
558 baseline: Option<f64>,
559 top_k: usize,
560 ) -> NpResult<DemHotspotEstimate> {
561 let batch = self.run_batch(shots, seed, true)?;
562 self.estimate_from_loss(&batch, &batch.loss_mask, baseline, top_k)
563 }
564
565 pub fn estimate_from_loss(
570 &self,
571 batch: &DemBatch,
572 loss_mask: &Mask,
573 baseline: Option<f64>,
574 top_k: usize,
575 ) -> NpResult<DemHotspotEstimate> {
576 if !batch.matches_hotspot_layout(&self.hotspot_layout_identity) {
577 return Err(NpError::new(
578 "hotspot batch layout does not match the current DEM estimator",
579 ));
580 }
581 if batch.shots() == 0 {
582 return Err(NpError::new(
583 "DEM hotspot estimation requires shots to be positive",
584 ));
585 }
586 if !batch.records_edge_events() {
587 return Err(NpError::new(
588 "DEM hotspot estimation requires recorded event masks",
589 ));
590 }
591 crate::hotspot::validate_loss_mask_width("DEM hotspot", batch.shots(), loss_mask)?;
592 Ok(crate::hotspot::compute_dem_estimate(
593 crate::hotspot::DemEstimateProgram {
594 edges: &self.edges,
595 edge_metadata: self.edge_metadata.as_deref().unwrap_or(&[]),
596 location_groups: &self.location_groups,
597 catalog: &self.location_catalog,
598 },
599 batch,
600 loss_mask,
601 baseline,
602 top_k,
603 ))
604 }
605
606 pub fn estimate_from_attribution(
608 &self,
609 trace: &DemAttributionTrace,
610 loss_mask: &Mask,
611 baseline: Option<f64>,
612 top_k: usize,
613 ) -> NpResult<DemHotspotEstimate> {
614 if !trace.matches_sampler(&self.hotspot_layout_identity) {
615 return Err(NpError::new(
616 "hotspot attribution trace does not match the current DEM estimator",
617 ));
618 }
619 if trace.shots == 0 {
620 return Err(NpError::new(
621 "DEM hotspot estimation requires shots to be positive",
622 ));
623 }
624 if trace.edge_event_masks.len() != self.edges.len() {
625 return Err(NpError::new(format!(
626 "hotspot attribution trace has {} edge masks; expected {}",
627 trace.edge_event_masks.len(),
628 self.edges.len()
629 )));
630 }
631 crate::hotspot::validate_loss_mask_width("DEM hotspot", trace.shots, loss_mask)?;
632 let all_mask = Mask::all(trace.shots);
633 Ok(crate::hotspot::compute_dem_estimate_from_trace(
634 crate::hotspot::DemEstimateProgram {
635 edges: &self.edges,
636 edge_metadata: self.edge_metadata.as_deref().unwrap_or(&[]),
637 location_groups: &self.location_groups,
638 catalog: &self.location_catalog,
639 },
640 trace.shots,
641 &all_mask,
642 &trace.edge_event_masks,
643 loss_mask,
644 baseline,
645 top_k,
646 ))
647 }
648}
649
650struct DemSamplingPlanSpec<'a> {
651 sampling_detector_ids: &'a [i64],
652 sampling_observable_ids: &'a [i64],
653 edges: &'a [DemProgramEdge],
654 detector_ids: &'a [i64],
655 observable_ids: &'a [i64],
656 format: DetectorBatchFormat,
657 detail_detector_ids: &'a [i64],
658 record_attribution: bool,
659 sampler_identity: &'a Arc<()>,
660 sampler_name: &'a str,
661}
662
663fn compile_dem_sampling_plan(spec: DemSamplingPlanSpec<'_>) -> NpResult<CompiledDemSamplingPlan> {
664 let DemSamplingPlanSpec {
665 sampling_detector_ids,
666 sampling_observable_ids,
667 edges,
668 detector_ids,
669 observable_ids,
670 format,
671 detail_detector_ids,
672 record_attribution,
673 sampler_identity,
674 sampler_name,
675 } = spec;
676 validate_decoder_detector_ids(detector_ids)?;
677 validate_decoder_detector_ids(detail_detector_ids)?;
678 validate_decoder_observable_ids(observable_ids)?;
679 let sampling_detector_index = sampling_detector_ids
680 .iter()
681 .copied()
682 .enumerate()
683 .map(|(index, id)| (id, index))
684 .collect::<HashMap<_, _>>();
685 for detector_id in detector_ids {
686 if !sampling_detector_index.contains_key(detector_id) {
687 return Err(NpError::new(format!(
688 "{sampler_name} requested detector id {detector_id}, but it is not declared by the DEM"
689 )));
690 }
691 }
692 for detector_id in detail_detector_ids {
693 if !sampling_detector_index.contains_key(detector_id) {
694 return Err(NpError::new(format!(
695 "{sampler_name} requested detail detector id {detector_id}, but it is not declared by the DEM"
696 )));
697 }
698 }
699 let detector_index = detector_ids
700 .iter()
701 .copied()
702 .enumerate()
703 .map(|(index, id)| (id, index))
704 .collect::<HashMap<_, _>>();
705 let detail_detector_index = detail_detector_ids
706 .iter()
707 .copied()
708 .enumerate()
709 .map(|(index, id)| (id, index))
710 .collect::<HashMap<_, _>>();
711
712 let sampling_observable_index = sampling_observable_ids
713 .iter()
714 .copied()
715 .enumerate()
716 .map(|(index, id)| (id, index))
717 .collect::<HashMap<_, _>>();
718 for observable_id in observable_ids {
719 if !sampling_observable_index.contains_key(observable_id) {
720 return Err(NpError::new(format!(
721 "{sampler_name} requested observable id {observable_id}, but it is not declared by the DEM"
722 )));
723 }
724 }
725 let observable_index = observable_ids
726 .iter()
727 .copied()
728 .enumerate()
729 .map(|(index, id)| (id, index))
730 .collect::<HashMap<_, _>>();
731
732 let compiled_edges = edges
733 .iter()
734 .map(|edge| {
735 let detector_columns = edge
736 .detectors
737 .iter()
738 .filter_map(|detector_id| detector_index.get(detector_id).copied())
739 .collect::<Vec<_>>();
740 let packed_detector_columns = detector_columns
741 .iter()
742 .map(|column| (column >> 3, 1u8 << (column & 7)))
743 .collect();
744 let detail_detector_columns = edge
745 .detectors
746 .iter()
747 .filter_map(|detector_id| detail_detector_index.get(detector_id).copied())
748 .collect();
749 let mut observable_mask_columns = Vec::with_capacity(edge.observables.len());
750 let mut observable_columns = Vec::with_capacity(edge.observables.len());
751 for observable_id in &edge.observables {
752 let column = packed_column_for_id(*observable_id, &observable_index)?;
753 observable_mask_columns.push(column);
754 observable_columns.push((column >> 3, 1u8 << (column & 7)));
755 }
756 Ok(CompiledSamplingEdge {
757 probability: edge.probability,
758 detector_columns,
759 packed_detector_columns,
760 detail_detector_columns,
761 observable_mask_columns,
762 observable_columns,
763 })
764 })
765 .collect::<NpResult<Vec<_>>>()?;
766
767 Ok(CompiledDemSamplingPlan {
768 detector_ids: detector_ids.to_vec(),
769 observable_ids: observable_ids.to_vec(),
770 format,
771 detail_detector_ids: detail_detector_ids.to_vec(),
772 record_attribution,
773 sampler_identity: sampler_identity.clone(),
774 edges: compiled_edges,
775 detector_byte_count: detector_ids.len().div_ceil(8),
776 observable_byte_count: observable_ids.len().div_ceil(8),
777 })
778}
779
780impl CompiledDemSamplingPlan {
781 pub fn detector_ids(&self) -> &[i64] {
783 &self.detector_ids
784 }
785
786 pub fn observable_ids(&self) -> &[i64] {
788 &self.observable_ids
789 }
790
791 pub fn format(&self) -> DetectorBatchFormat {
792 self.format
793 }
794
795 pub fn detail_detector_ids(&self) -> &[i64] {
796 &self.detail_detector_ids
797 }
798
799 pub fn records_attribution(&self) -> bool {
800 self.record_attribution
801 }
802
803 pub fn run_sampling_result_with_rng(
806 &self,
807 shots: usize,
808 rng: &mut SmallRng,
809 ) -> NpResult<DemSamplingResult> {
810 let words = word_count(shots);
811 let detector_len = shots
812 .checked_mul(self.detector_byte_count)
813 .ok_or_else(|| NpError::new("DEM detector batch length overflowed usize"))?;
814 let observable_len = shots
815 .checked_mul(self.observable_byte_count)
816 .ok_or_else(|| NpError::new("DEM observable batch length overflowed usize"))?;
817
818 let mut detector_masks = (self.format == DetectorBatchFormat::Masks)
819 .then(|| vec![Mask::zero(words); self.detector_ids.len()]);
820 let mut detector_data =
821 (self.format == DetectorBatchFormat::Packed).then(|| vec![0u8; detector_len]);
822 let mut event_counts =
823 (self.format == DetectorBatchFormat::Events).then(|| vec![0usize; shots]);
824 let mut raw_events = Vec::<(usize, usize)>::new();
825
826 let mut observable_masks = (self.format == DetectorBatchFormat::Masks)
827 .then(|| vec![Mask::zero(words); self.observable_ids.len()]);
828 let mut observable_data =
829 (self.format != DetectorBatchFormat::Masks).then(|| vec![0u8; observable_len]);
830 let mut detail_detector_masks = vec![Mask::zero(words); self.detail_detector_ids.len()];
831 let mut trace_masks = self
832 .record_attribution
833 .then(|| Vec::with_capacity(self.edges.len()));
834 let mut count_overflowed = false;
835
836 for edge in &self.edges {
837 let mut trace_mask = self.record_attribution.then(|| Mask::zero(words));
838 for_each_bernoulli_event(rng, shots, edge.probability, |shot, _| {
839 let shot_word = shot >> 6;
840 let shot_bit = 1u64 << (shot & 63);
841 if let Some(mask) = &mut trace_mask {
842 mask.words[shot_word] |= shot_bit;
843 }
844 if let Some(masks) = &mut detector_masks {
845 for detector in &edge.detector_columns {
846 masks[*detector].words[shot_word] ^= shot_bit;
847 }
848 } else if let Some(data) = &mut detector_data {
849 let row = shot * self.detector_byte_count;
850 for (byte, bit) in &edge.packed_detector_columns {
851 data[row + byte] ^= bit;
852 }
853 } else if let Some(counts) = &mut event_counts {
854 match counts[shot].checked_add(edge.detector_columns.len()) {
855 Some(count) => counts[shot] = count,
856 None => count_overflowed = true,
857 }
858 raw_events.extend(
859 edge.detector_columns
860 .iter()
861 .copied()
862 .map(|detector| (shot, detector)),
863 );
864 }
865
866 if let Some(masks) = &mut observable_masks {
867 for observable in &edge.observable_mask_columns {
868 masks[*observable].words[shot_word] ^= shot_bit;
869 }
870 } else if let Some(data) = &mut observable_data {
871 let row = shot * self.observable_byte_count;
872 for (byte, bit) in &edge.observable_columns {
873 data[row + byte] ^= bit;
874 }
875 }
876 for detector in &edge.detail_detector_columns {
877 detail_detector_masks[*detector].words[shot_word] ^= shot_bit;
878 }
879 });
880 if let (Some(masks), Some(mask)) = (&mut trace_masks, trace_mask) {
881 masks.push(mask);
882 }
883 }
884 if count_overflowed {
885 return Err(NpError::new("DEM detector event count overflowed usize"));
886 }
887
888 let syndrome = match self.format {
889 DetectorBatchFormat::Masks => DetectorBatch::Masks {
890 detector_ids: self.detector_ids.clone(),
891 masks: detector_masks.expect("Masks plan allocates mask-major syndrome"),
892 shots,
893 },
894 DetectorBatchFormat::Packed => DetectorBatch::Packed {
895 detector_ids: self.detector_ids.clone(),
896 data: detector_data.expect("Packed plan allocates packed syndrome"),
897 shots,
898 detector_byte_count: self.detector_byte_count,
899 },
900 DetectorBatchFormat::Events => {
901 let counts = event_counts.expect("Events plan allocates event counts");
902 let mut offsets = crate::decoder::empty_detector_event_offsets(shots)?;
903 for count in counts {
904 let next = offsets
905 .last()
906 .copied()
907 .expect("offset zero is present")
908 .checked_add(count)
909 .ok_or_else(|| {
910 NpError::new("DEM detector event offset overflowed usize")
911 })?;
912 offsets.push(next);
913 }
914 let mut events = vec![0usize; offsets.last().copied().unwrap_or(0)];
915 let mut next = offsets.clone();
916 for (shot, detector) in raw_events {
917 events[next[shot]] = detector;
918 next[shot] += 1;
919 }
920 DetectorBatch::Events {
921 detector_ids: self.detector_ids.clone(),
922 offsets,
923 events,
924 shots,
925 }
926 }
927 };
928 syndrome.validate_shape()?;
929
930 let observables = if self.format == DetectorBatchFormat::Masks {
931 DemObservableBatch::Masks(CorrectionMaskBatch::new(
932 self.observable_ids.clone(),
933 observable_masks.expect("Masks plan allocates mask-major observables"),
934 shots,
935 )?)
936 } else {
937 DemObservableBatch::Packed(PackedObservableShotBatch::new(
938 self.observable_ids.clone(),
939 observable_data.expect("non-Masks plan allocates packed observables"),
940 shots,
941 )?)
942 };
943 let all_mask = Mask::all(shots);
944 let attribution = trace_masks.map(|edge_event_masks| DemAttributionTrace {
945 shots,
946 edge_event_masks,
947 sampler_identity: self.sampler_identity.clone(),
948 });
949 Ok(DemSamplingResult {
950 syndrome,
951 observables,
952 detail_detector_ids: self.detail_detector_ids.clone(),
953 detail_detector_masks,
954 all_mask,
955 attribution,
956 sampler_identity: self.sampler_identity.clone(),
957 })
958 }
959
960 pub fn run_packed_shot_batch_with_rng(
962 &self,
963 shots: usize,
964 rng: &mut SmallRng,
965 ) -> PackedDemShotBatch {
966 let mut detector_data = vec![0; shots * self.detector_byte_count];
967 let mut observable_data = vec![0; shots * self.observable_byte_count];
968
969 for columns in &self.edges {
970 for_each_bernoulli_event(rng, shots, columns.probability, |shot, _| {
971 let detector_row = shot * self.detector_byte_count;
972 for (byte_index, bit_mask) in &columns.packed_detector_columns {
973 detector_data[detector_row + byte_index] ^= bit_mask;
974 }
975 let observable_row = shot * self.observable_byte_count;
976 for (byte_index, bit_mask) in &columns.observable_columns {
977 observable_data[observable_row + byte_index] ^= bit_mask;
978 }
979 });
980 }
981
982 PackedDemShotBatch {
983 shots,
984 detector_data,
985 detector_byte_count: self.detector_byte_count,
986 observable_ids: self.observable_ids.clone(),
987 observable_data,
988 observable_byte_count: self.observable_byte_count,
989 }
990 }
991
992 pub fn run_detector_event_shot_batch_with_rng(
994 &self,
995 shots: usize,
996 rng: &mut SmallRng,
997 ) -> DetectorEventDemShotBatch {
998 let mut observable_data = vec![0; shots * self.observable_byte_count];
999 let mut event_counts = vec![0usize; shots];
1000 let mut raw_events = Vec::<(usize, usize)>::new();
1001
1002 for columns in &self.edges {
1003 for_each_bernoulli_event(rng, shots, columns.probability, |shot, _| {
1004 event_counts[shot] += columns.detector_columns.len();
1005 raw_events.extend(
1006 columns
1007 .detector_columns
1008 .iter()
1009 .copied()
1010 .map(|detector| (shot, detector)),
1011 );
1012 let observable_row = shot * self.observable_byte_count;
1013 for (byte_index, bit_mask) in &columns.observable_columns {
1014 observable_data[observable_row + byte_index] ^= bit_mask;
1015 }
1016 });
1017 }
1018
1019 let mut offsets = Vec::with_capacity(shots + 1);
1020 offsets.push(0);
1021 for count in event_counts {
1022 offsets.push(offsets.last().copied().unwrap_or(0) + count);
1023 }
1024
1025 let mut events = vec![0usize; offsets.last().copied().unwrap_or(0)];
1026 let mut next = offsets.clone();
1027 for (shot, detector) in raw_events {
1028 let index = next[shot];
1029 events[index] = detector;
1030 next[shot] += 1;
1031 }
1032
1033 DetectorEventDemShotBatch {
1034 shots,
1035 offsets,
1036 events,
1037 observable_ids: self.observable_ids.clone(),
1038 observable_data,
1039 observable_byte_count: self.observable_byte_count,
1040 }
1041 }
1042}
1043
1044impl CompiledDemLogicalCountPlan {
1045 fn new(observable_ids: &[i64], edges: &[DemProgramEdge]) -> Self {
1046 let compiled_observable_ids = observable_ids.to_vec();
1047 let observable_index = id_index(observable_ids);
1048 let compiled_edges = edges
1049 .iter()
1050 .map(|edge| {
1051 let observable_columns = edge
1052 .observables
1053 .iter()
1054 .map(|observable_id| {
1055 *observable_index
1056 .get(observable_id)
1057 .expect("canonical DEM layout must include every edge observable")
1058 })
1059 .collect::<Vec<_>>();
1060 let single_observable_flip = observable_columns
1061 .iter()
1062 .filter(|column| **column == 0)
1063 .count()
1064 % 2
1065 != 0;
1066 CompiledLogicalCountEdge {
1067 probability: edge.probability,
1068 observable_columns,
1069 single_observable_flip,
1070 }
1071 })
1072 .collect::<Vec<_>>();
1073 let single_observable_flip_edge_count = compiled_edges
1074 .iter()
1075 .filter(|edge| edge.single_observable_flip)
1076 .count();
1077 Self {
1078 observable_ids: compiled_observable_ids,
1079 edges: compiled_edges,
1080 single_observable_flip_edge_count,
1081 }
1082 }
1083
1084 pub fn observable_ids(&self) -> &[i64] {
1086 &self.observable_ids
1087 }
1088
1089 pub fn sample_logical_error_count_with_rng(&self, shots: usize, rng: &mut SmallRng) -> usize {
1091 if self.observable_ids.len() == 1 {
1092 return self.sample_single_observable_count(shots, rng);
1093 }
1094 let words = word_count(shots);
1095 let mut observable_words = vec![0u64; self.observable_ids.len() * words];
1096 let mut event_words = vec![0u64; words];
1097
1098 for edge in &self.edges {
1099 fill_bernoulli_words(&mut event_words, shots, edge.probability, rng);
1100 for observable_column in &edge.observable_columns {
1101 let start = observable_column * words;
1102 for (observable, event) in observable_words[start..start + words]
1103 .iter_mut()
1104 .zip(&event_words)
1105 {
1106 *observable ^= event;
1107 }
1108 }
1109 }
1110
1111 (0..words)
1112 .map(|word| {
1113 (0..self.observable_ids.len())
1114 .fold(0u64, |loss, observable| {
1115 loss | observable_words[observable * words + word]
1116 })
1117 .count_ones() as usize
1118 })
1119 .sum()
1120 }
1121
1122 fn sample_single_observable_count(&self, shots: usize, rng: &mut SmallRng) -> usize {
1123 if self.single_observable_flip_edge_count <= 1 {
1124 let mut errors = 0usize;
1125 for edge in &self.edges {
1126 if edge.probability <= 0.0 {
1127 continue;
1128 }
1129 if edge.probability >= 1.0 {
1130 if edge.single_observable_flip {
1131 errors += shots;
1132 }
1133 continue;
1134 }
1135 if edge.single_observable_flip {
1136 for_each_bernoulli_event(rng, shots, edge.probability, |_, _| errors += 1);
1137 } else {
1138 for_each_bernoulli_event(rng, shots, edge.probability, |_, _| {});
1139 }
1140 }
1141 return errors;
1142 }
1143
1144 const STACK_WORDS: usize = 8;
1145 let words = word_count(shots);
1146 if words <= STACK_WORDS {
1147 let mut logical_words = [0u64; STACK_WORDS];
1148 sample_single_observable_words(&self.edges, shots, rng, &mut logical_words[..words]);
1149 logical_words[..words]
1150 .iter()
1151 .map(|word| word.count_ones() as usize)
1152 .sum()
1153 } else {
1154 let mut logical_words = vec![0u64; words];
1155 sample_single_observable_words(&self.edges, shots, rng, &mut logical_words);
1156 logical_words
1157 .iter()
1158 .map(|word| word.count_ones() as usize)
1159 .sum()
1160 }
1161 }
1162}
1163
1164fn sample_single_observable_words(
1165 edges: &[CompiledLogicalCountEdge],
1166 shots: usize,
1167 rng: &mut SmallRng,
1168 logical_words: &mut [u64],
1169) {
1170 for edge in edges {
1171 if edge.probability <= 0.0 {
1172 continue;
1173 }
1174 if edge.probability >= 1.0 {
1175 if edge.single_observable_flip {
1176 for word in logical_words.iter_mut() {
1177 *word ^= u64::MAX;
1178 }
1179 let remainder = shots % 64;
1180 if remainder != 0 {
1181 *logical_words.last_mut().expect("non-empty shot mask") &=
1182 (1u64 << remainder) - 1;
1183 }
1184 }
1185 continue;
1186 }
1187 if edge.single_observable_flip {
1188 for_each_bernoulli_event(rng, shots, edge.probability, |shot, _| {
1189 logical_words[shot / 64] ^= 1u64 << (shot % 64);
1190 });
1191 } else {
1192 for_each_bernoulli_event(rng, shots, edge.probability, |_, _| {});
1193 }
1194 }
1195}
1196
1197fn fill_bernoulli_words(words: &mut [u64], shots: usize, probability: f64, rng: &mut SmallRng) {
1198 words.fill(0);
1199 if probability <= 0.0 {
1200 return;
1201 }
1202 if probability >= 1.0 {
1203 words.fill(u64::MAX);
1204 if let (Some(last), remainder) = (words.last_mut(), shots % 64) {
1205 if remainder != 0 {
1206 *last &= (1u64 << remainder) - 1;
1207 }
1208 }
1209 return;
1210 }
1211 for_each_bernoulli_event(rng, shots, probability, |shot, _| {
1212 words[shot / 64] |= 1u64 << (shot % 64);
1213 });
1214}
1215
1216fn packed_column_for_id(id: i64, index: &HashMap<i64, usize>) -> NpResult<usize> {
1217 index.get(&id).copied().ok_or_else(|| {
1218 NpError::new(format!(
1219 "packed DEM sampler edge references unknown id {id}"
1220 ))
1221 })
1222}
1223
1224fn canonicalize_program_parts(
1225 detector_ids: Vec<i64>,
1226 observable_ids: Vec<i64>,
1227 mut edges: Vec<DemProgramEdge>,
1228) -> NpResult<(Vec<i64>, Vec<i64>, Vec<DemProgramEdge>)> {
1229 let detector_ids = canonical_id_order(
1230 &detector_ids,
1231 edges.iter().map(|edge| edge.detectors.as_slice()),
1232 "detector ids must be unique",
1233 )?;
1234 let observable_ids = canonical_id_order(
1235 &observable_ids,
1236 edges.iter().map(|edge| edge.observables.as_slice()),
1237 "logical observable ids must be unique",
1238 )?;
1239 for edge in &mut edges {
1240 parity_canonicalize(&mut edge.detectors);
1241 parity_canonicalize(&mut edge.observables);
1242 }
1243 Ok((detector_ids, observable_ids, edges))
1244}
1245
1246fn id_index(ids: &[i64]) -> HashMap<i64, usize> {
1247 ids.iter()
1248 .copied()
1249 .enumerate()
1250 .map(|(index, id)| (id, index))
1251 .collect()
1252}
1253
1254fn compile_dem_edges(
1255 edges: Vec<DetectorErrorEdge>,
1256 preserve_metadata: bool,
1257) -> NpResult<CompiledDemEdges> {
1258 let mut catalog = preserve_metadata.then(|| LocationCatalogBuilder::with_capacity(edges.len()));
1259 let mut compiled = Vec::with_capacity(edges.len());
1260 let mut metadata = preserve_metadata.then(|| Vec::with_capacity(edges.len()));
1261 for edge in edges {
1262 edge.validate()?;
1263 let DetectorErrorEdge {
1264 probability,
1265 detectors,
1266 observables,
1267 location_id,
1268 event,
1269 tags,
1270 } = edge;
1271 if let (Some(catalog), Some(metadata)) = (&mut catalog, &mut metadata) {
1272 metadata.push(DemProgramEdgeMetadata {
1273 location_id: catalog.intern(location_id, tags),
1274 event,
1275 });
1276 }
1277 compiled.push(DemProgramEdge {
1278 probability,
1279 detectors,
1280 observables,
1281 });
1282 }
1283 let catalog = catalog
1284 .map(LocationCatalogBuilder::finish)
1285 .unwrap_or_default();
1286 let groups = metadata
1287 .as_deref()
1288 .map(|metadata| build_dem_program_location_groups(&compiled, metadata, catalog.len()))
1289 .unwrap_or_default();
1290 Ok(CompiledDemEdges {
1291 edges: compiled,
1292 metadata,
1293 catalog,
1294 location_groups: groups,
1295 })
1296}
1297
1298fn build_dem_program_location_groups(
1299 edges: &[DemProgramEdge],
1300 edge_metadata: &[DemProgramEdgeMetadata],
1301 location_count: usize,
1302) -> Vec<DemProgramLocationGroup> {
1303 let mut group_indices = vec![None; location_count];
1304 let mut groups = Vec::with_capacity(location_count);
1305 for (edge_index, metadata) in edge_metadata.iter().enumerate() {
1306 let location_index = metadata.location_id.index();
1307 let group_index = match group_indices[location_index] {
1308 Some(group_index) => group_index,
1309 None => {
1310 let group_index = groups.len();
1311 group_indices[location_index] = Some(group_index);
1312 groups.push(DemProgramLocationGroup {
1313 location_id: metadata.location_id,
1314 edge_indices: Vec::new(),
1315 total_probability: 0.0,
1316 });
1317 group_index
1318 }
1319 };
1320 let group = &mut groups[group_index];
1321 group.edge_indices.push(edge_index);
1322 group.total_probability += edges[edge_index].probability;
1323 }
1324 groups
1325}
1326
1327fn materialize_dem_edge(
1328 edge: &DemProgramEdge,
1329 metadata: Option<&DemProgramEdgeMetadata>,
1330 catalog: &LocationCatalog,
1331) -> DetectorErrorEdge {
1332 let (location_id, event, tags) = match metadata {
1333 Some(metadata) => (
1334 catalog.label(metadata.location_id).to_string(),
1335 metadata.event.clone(),
1336 catalog.tags(metadata.location_id).clone(),
1337 ),
1338 None => (String::new(), DemEvent::Bool(false), HashMap::new()),
1339 };
1340 DetectorErrorEdge {
1341 probability: edge.probability,
1342 detectors: edge.detectors.clone(),
1343 observables: edge.observables.clone(),
1344 location_id,
1345 event,
1346 tags,
1347 }
1348}
1349
1350#[cfg(test)]
1351mod tests {
1352 use super::*;
1353
1354 fn edge(probability: f64, detectors: Vec<i64>, observables: Vec<i64>) -> DetectorErrorEdge {
1355 DetectorErrorEdge {
1356 probability,
1357 detectors,
1358 observables,
1359 location_id: "test".to_string(),
1360 event: crate::DemEvent::Pauli("X".to_string()),
1361 tags: HashMap::new(),
1362 }
1363 }
1364
1365 #[test]
1366 fn sampling_only_edges_keep_metadata_out_of_the_hot_representation() {
1367 let simulator = DemHotspotEstimator::from_sampling_parts(
1368 vec![1],
1369 vec![2],
1370 vec![edge(0.25, vec![1], vec![2])],
1371 )
1372 .unwrap();
1373
1374 assert!(simulator.edge_metadata.is_none());
1375 assert!(simulator.location_catalog.is_empty());
1376 let materialized = simulator.edge(0).unwrap();
1377 assert_eq!(materialized.probability, 0.25);
1378 assert_eq!(materialized.detectors, vec![1]);
1379 assert_eq!(materialized.observables, vec![2]);
1380 assert!(materialized.location_id.is_empty());
1381 assert_eq!(materialized.event, DemEvent::Bool(false));
1382 assert!(materialized.tags.is_empty());
1383 }
1384
1385 fn packed_reference(
1386 batch: &DemBatch,
1387 detector_ids: &[i64],
1388 observable_ids: &[i64],
1389 ) -> (Vec<u8>, Vec<u8>) {
1390 let detector_bytes = detector_ids.len().div_ceil(8);
1391 let observable_bytes = observable_ids.len().div_ceil(8);
1392 let mut detectors = vec![0u8; batch.shots() * detector_bytes];
1393 let mut observables = vec![0u8; batch.shots() * observable_bytes];
1394 for shot in 0..batch.shots() {
1395 for (column, detector_id) in detector_ids.iter().enumerate() {
1396 if batch.detectors[detector_id].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1397 detectors[shot * detector_bytes + column / 8] |= 1u8 << (column % 8);
1398 }
1399 }
1400 for (column, observable_id) in observable_ids.iter().enumerate() {
1401 if batch.observables[observable_id].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1402 observables[shot * observable_bytes + column / 8] |= 1u8 << (column % 8);
1403 }
1404 }
1405 }
1406 (detectors, observables)
1407 }
1408
1409 fn mask_batch_parts(batch: DetectorBatch) -> (Vec<i64>, Vec<Mask>, usize) {
1410 let DetectorBatch::Masks {
1411 detector_ids,
1412 masks,
1413 shots,
1414 } = batch
1415 else {
1416 unreachable!("requested Masks conversion")
1417 };
1418 (detector_ids, masks, shots)
1419 }
1420
1421 #[test]
1422 fn negotiated_sampling_formats_preserve_syndrome_truth_rng_detail_and_attribution() {
1423 let simulator = DemHotspotEstimator::from_parts(
1424 vec![10, 20, 30],
1425 vec![7, 9],
1426 vec![
1427 edge(0.0, vec![10], vec![7]),
1428 edge(0.13, vec![20, 30], vec![9]),
1429 edge(0.71, vec![10, 30], vec![7, 9]),
1430 edge(1.0, vec![20], vec![]),
1431 edge(0.37, vec![10, 20], vec![7]),
1432 ],
1433 )
1434 .unwrap();
1435 let detector_ids = [30, 10, 20];
1436 let observable_ids = [9, 7];
1437 let detail_ids = [20, 10];
1438 type ExpectedSampling = (
1439 Vec<Mask>,
1440 CorrectionMaskBatch,
1441 Vec<Mask>,
1442 Vec<Mask>,
1443 u64,
1444 Option<DemHotspotEstimate>,
1445 );
1446
1447 for shots in [0, 1, 7, 8, 63, 64, 65, 129] {
1448 let mut expected: Option<ExpectedSampling> = None;
1449 for format in DetectorBatchFormat::STABLE_ORDER {
1450 let plan = simulator
1451 .compile_decoder_sampling_plan(
1452 &detector_ids,
1453 &observable_ids,
1454 format,
1455 &detail_ids,
1456 true,
1457 )
1458 .unwrap();
1459 assert_eq!(plan.format(), format);
1460 assert_eq!(plan.detail_detector_ids(), detail_ids);
1461 assert!(plan.records_attribution());
1462
1463 let mut rng = SmallRng::new(0xdec0de);
1464 let sampled = plan.run_sampling_result_with_rng(shots, &mut rng).unwrap();
1465 let next = rng.next_u64();
1466 let (_, syndrome_masks, sampled_shots) = mask_batch_parts(
1467 convert_detector_batch(sampled.syndrome(), DetectorBatchFormat::Masks).unwrap(),
1468 );
1469 assert_eq!(sampled_shots, shots);
1470 let observable_masks = sampled.observables().as_masks().unwrap();
1471 let detail_masks = sampled.detail_detector_masks().to_vec();
1472 let trace = sampled.attribution().expect("attribution was requested");
1473 assert_eq!(trace.shots(), shots);
1474 let trace_masks = trace.edge_event_masks().to_vec();
1475 let estimate = if shots == 0 {
1476 None
1477 } else {
1478 let mut loss = Mask::zero(word_count(shots));
1479 for mask in &observable_masks.masks {
1480 loss.or_assign(mask);
1481 }
1482 Some(
1483 simulator
1484 .estimate_from_attribution(trace, &loss, None, simulator.edge_count())
1485 .unwrap(),
1486 )
1487 };
1488
1489 let actual = (
1490 syndrome_masks,
1491 observable_masks,
1492 detail_masks,
1493 trace_masks,
1494 next,
1495 estimate,
1496 );
1497 if let Some(expected) = &expected {
1498 assert_eq!(&actual, expected);
1499 } else {
1500 expected = Some(actual);
1501 }
1502 }
1503 }
1504 }
1505
1506 #[test]
1507 fn ordinary_negotiated_sampling_does_not_record_attribution() {
1508 let simulator = DemHotspotEstimator::from_sampling_parts(
1509 vec![1],
1510 vec![2],
1511 vec![edge(0.25, vec![1], vec![2])],
1512 )
1513 .unwrap();
1514 for format in DetectorBatchFormat::STABLE_ORDER {
1515 let plan = simulator
1516 .compile_decoder_sampling_plan(&[1], &[2], format, &[], false)
1517 .unwrap();
1518 assert!(!plan.records_attribution());
1519 let sampled = plan
1520 .run_sampling_result_with_rng(65, &mut SmallRng::new(4))
1521 .unwrap();
1522 assert!(sampled.attribution().is_none());
1523 assert!(sampled.detail_detector_ids().is_empty());
1524 assert!(sampled.detail_detector_masks().is_empty());
1525 }
1526 }
1527
1528 #[test]
1529 fn compiled_sampling_matches_generic_batch_across_word_boundaries() {
1530 let simulator = DemHotspotEstimator::from_sampling_parts(
1531 vec![10, 20, 30],
1532 vec![7, 9],
1533 vec![
1534 edge(0.0, vec![10], vec![7]),
1535 edge(0.13, vec![20, 30], vec![9]),
1536 edge(0.71, vec![10, 30], vec![7, 9]),
1537 edge(1.0, vec![20], vec![]),
1538 ],
1539 )
1540 .unwrap();
1541 let detector_ids = [30, 10, 20];
1542 let observable_ids = [9, 7];
1543 let plan = simulator
1544 .compile_sampling_plan(&detector_ids, &observable_ids)
1545 .unwrap();
1546
1547 for shots in [1, 63, 64, 65, 129] {
1548 for seed in [0, 1, 0xdead_beef] {
1549 let mut generic_rng = SmallRng::new(seed);
1550 let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1551 let expected = packed_reference(&generic, &detector_ids, &observable_ids);
1552 let mut compiled_rng = SmallRng::new(seed);
1553 let actual = plan.run_packed_shot_batch_with_rng(shots, &mut compiled_rng);
1554 assert_eq!(actual.detector_data, expected.0);
1555 assert_eq!(actual.observable_data, expected.1);
1556 assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1557 }
1558 }
1559 }
1560
1561 #[test]
1562 fn compiled_event_batch_emits_parity_canonical_events() {
1563 let simulator = DemHotspotEstimator::from_sampling_parts(
1564 vec![10, 20],
1565 vec![7, 9],
1566 vec![
1567 edge(1.0, vec![20, 10, 20], vec![9]),
1568 edge(1.0, vec![10], vec![9, 9, 7]),
1569 ],
1570 )
1571 .unwrap();
1572 let plan = simulator.compile_sampling_plan(&[20, 10], &[9, 7]).unwrap();
1573 let batch = plan.run_detector_event_shot_batch_with_rng(2, &mut SmallRng::new(4));
1574
1575 assert_eq!(batch.offsets, vec![0, 2, 4]);
1576 assert_eq!(batch.events, vec![1, 1, 1, 1]);
1577 assert_eq!(batch.observable_data, vec![0b11, 0b11]);
1578 }
1579
1580 #[test]
1581 fn estimator_canonicalizes_implicit_ids_and_parity_once() {
1582 let simulator = DemHotspotEstimator::from_sampling_parts(
1583 Vec::new(),
1584 Vec::new(),
1585 vec![edge(1.0, vec![1, 1], vec![9, 9])],
1586 )
1587 .unwrap();
1588
1589 assert_eq!(simulator.detector_ids, vec![1]);
1590 assert_eq!(simulator.observable_ids, vec![9]);
1591 assert_eq!(simulator.edge_count(), 1);
1592 assert!(simulator.edge(0).unwrap().detectors.is_empty());
1593 assert!(simulator.edge(0).unwrap().observables.is_empty());
1594
1595 let mut generic_rng = SmallRng::new(13);
1596 let generic = simulator.run_batch_with_rng(4, &mut generic_rng, true);
1597 assert_eq!(generic.detectors[&1].bit_count(), 0);
1598 assert_eq!(generic.observables[&9].bit_count(), 0);
1599 assert_eq!(generic.edge_event_masks().len(), 1);
1600 assert_eq!(generic.edge_event_masks()[0].bit_count(), 4);
1601
1602 let plan = simulator.compile_sampling_plan(&[1], &[9]).unwrap();
1603 let mut packed_rng = SmallRng::new(13);
1604 let packed = plan.run_packed_shot_batch_with_rng(4, &mut packed_rng);
1605 assert_eq!(packed.detector_data, vec![0; 4]);
1606 assert_eq!(packed.observable_data, vec![0; 4]);
1607 assert_eq!(generic_rng.next_u64(), packed_rng.next_u64());
1608 }
1609
1610 #[test]
1611 fn parity_cancelled_edges_preserve_rng_across_sampling_paths() {
1612 for cancelled_probability in [0.0, 0.37, 1.0] {
1613 let simulator = DemHotspotEstimator::from_sampling_parts(
1614 Vec::new(),
1615 Vec::new(),
1616 vec![
1617 edge(cancelled_probability, vec![1, 1], vec![9, 9]),
1618 edge(0.43, vec![2], vec![10]),
1619 ],
1620 )
1621 .unwrap();
1622 let detector_ids = simulator.detector_ids();
1623 let observable_ids = simulator.observable_ids();
1624 let plan = simulator
1625 .compile_sampling_plan(detector_ids, observable_ids)
1626 .unwrap();
1627
1628 let mut generic_rng = SmallRng::new(123);
1629 let generic = simulator.run_batch_with_rng(129, &mut generic_rng, true);
1630 let expected = packed_reference(&generic, detector_ids, observable_ids);
1631 let generic_next = generic_rng.next_u64();
1632 assert_eq!(generic.edge_event_masks().len(), 2);
1633 assert_eq!(generic.detectors[&1].bit_count(), 0);
1634 assert_eq!(generic.observables[&9].bit_count(), 0);
1635
1636 let mut packed_rng = SmallRng::new(123);
1637 let packed = plan.run_packed_shot_batch_with_rng(129, &mut packed_rng);
1638 assert_eq!(packed.detector_data, expected.0);
1639 assert_eq!(packed.observable_data, expected.1);
1640 assert_eq!(packed_rng.next_u64(), generic_next);
1641
1642 let mut expected_offsets = Vec::with_capacity(130);
1643 let mut expected_events = Vec::new();
1644 expected_offsets.push(0);
1645 for shot in 0..129 {
1646 if generic.detectors[&2].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1647 expected_events.push(1);
1648 }
1649 expected_offsets.push(expected_events.len());
1650 }
1651 let mut event_rng = SmallRng::new(123);
1652 let events = plan.run_detector_event_shot_batch_with_rng(129, &mut event_rng);
1653 assert_eq!(events.offsets, expected_offsets);
1654 assert_eq!(events.events, expected_events);
1655 assert_eq!(events.observable_data, expected.1);
1656 assert_eq!(event_rng.next_u64(), generic_next);
1657 }
1658 }
1659
1660 #[test]
1661 fn public_id_mirrors_do_not_mutate_the_canonical_sampling_layout() {
1662 let mut simulator = DemHotspotEstimator::from_sampling_parts(
1663 Vec::new(),
1664 Vec::new(),
1665 vec![edge(0.43, vec![7], vec![9])],
1666 )
1667 .unwrap();
1668 let mut expected_rng = SmallRng::new(17);
1669 let expected = simulator.run_batch_with_rng(129, &mut expected_rng, false);
1670 let expected_rng_next = expected_rng.next_u64();
1671 let expected_packed = packed_reference(&expected, &[7], &[9]);
1672
1673 simulator.detector_ids.clear();
1674 simulator.detector_ids.push(70);
1675 simulator.observable_ids.clear();
1676 simulator.observable_ids.push(90);
1677
1678 assert_eq!(simulator.detector_ids(), &[7]);
1679 assert_eq!(simulator.observable_ids(), &[9]);
1680 assert_eq!(simulator.run_batch(129, Some(17), false).unwrap(), expected);
1681 assert_eq!(
1682 simulator.compile_logical_count_plan().observable_ids(),
1683 &[9]
1684 );
1685 let plan = simulator
1686 .compile_sampling_plan(simulator.detector_ids(), simulator.observable_ids())
1687 .unwrap();
1688 assert_eq!(plan.detector_ids(), &[7]);
1689 assert_eq!(plan.observable_ids(), &[9]);
1690
1691 let mut packed_rng = SmallRng::new(17);
1692 let packed = plan.run_packed_shot_batch_with_rng(129, &mut packed_rng);
1693 assert_eq!(packed.detector_data, expected_packed.0);
1694 assert_eq!(packed.observable_data, expected_packed.1);
1695 assert_eq!(packed_rng.next_u64(), expected_rng_next);
1696
1697 let mut expected_offsets = Vec::with_capacity(130);
1698 let mut expected_events = Vec::new();
1699 expected_offsets.push(0);
1700 for shot in 0..129 {
1701 if expected.detectors[&7].words[shot / 64] & (1u64 << (shot % 64)) != 0 {
1702 expected_events.push(0);
1703 }
1704 expected_offsets.push(expected_events.len());
1705 }
1706 let mut event_rng = SmallRng::new(17);
1707 let events = plan.run_detector_event_shot_batch_with_rng(129, &mut event_rng);
1708 assert_eq!(events.offsets, expected_offsets);
1709 assert_eq!(events.events, expected_events);
1710 assert_eq!(events.observable_data, expected_packed.1);
1711 assert_eq!(event_rng.next_u64(), expected_rng_next);
1712 }
1713
1714 #[test]
1715 fn estimator_rejects_duplicate_declared_ids() {
1716 let err = DemHotspotEstimator::from_sampling_parts(vec![1, 1], Vec::new(), Vec::new())
1717 .unwrap_err();
1718
1719 assert_eq!(err.message(), "detector ids must be unique");
1720 }
1721
1722 #[test]
1723 fn compiled_logical_count_matches_generic_loss_and_rng_sequence() {
1724 let simulator = DemHotspotEstimator::from_sampling_parts(
1725 vec![1],
1726 vec![5],
1727 vec![
1728 edge(0.17, vec![1], vec![]),
1729 edge(0.0, vec![], vec![5]),
1730 edge(0.23, vec![], vec![5, 9]),
1731 edge(0.61, vec![], vec![9, 9]),
1732 edge(1.0, vec![], vec![11]),
1733 ],
1734 )
1735 .unwrap();
1736 let plan = simulator.compile_logical_count_plan();
1737 assert_eq!(plan.observable_ids(), &[5, 9, 11]);
1738
1739 for shots in [0, 1, 63, 64, 65, 129] {
1740 for seed in [0, 1, 99] {
1741 let mut generic_rng = SmallRng::new(seed);
1742 let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1743 let mut compiled_rng = SmallRng::new(seed);
1744 let actual = plan.sample_logical_error_count_with_rng(shots, &mut compiled_rng);
1745 assert_eq!(actual, generic.loss_mask.bit_count());
1746 assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1747 }
1748 }
1749 }
1750
1751 #[test]
1752 fn single_observable_zero_allocation_path_preserves_xor_and_rng() {
1753 let simulator = DemHotspotEstimator::from_sampling_parts(
1754 vec![1],
1755 vec![5],
1756 vec![
1757 edge(0.19, vec![1], vec![]),
1758 edge(0.23, vec![], vec![5]),
1759 edge(0.61, vec![], vec![5]),
1760 edge(0.47, vec![], vec![5, 5]),
1761 edge(1.0, vec![], vec![5]),
1762 ],
1763 )
1764 .unwrap();
1765 let plan = simulator.compile_logical_count_plan();
1766
1767 for shots in [0, 1, 63, 64, 65, 129, 513] {
1768 for seed in [0, 7, 1234] {
1769 let mut generic_rng = SmallRng::new(seed);
1770 let generic = simulator.run_batch_with_rng(shots, &mut generic_rng, false);
1771 let mut compiled_rng = SmallRng::new(seed);
1772 let actual = plan.sample_logical_error_count_with_rng(shots, &mut compiled_rng);
1773 assert_eq!(actual, generic.loss_mask.bit_count());
1774 assert_eq!(compiled_rng.next_u64(), generic_rng.next_u64());
1775 }
1776 }
1777 }
1778
1779 #[test]
1780 fn compiled_sampling_preserves_validation_errors() {
1781 let simulator = DemHotspotEstimator::from_sampling_parts(
1782 vec![1],
1783 vec![2],
1784 vec![edge(0.5, vec![1], vec![2])],
1785 )
1786 .unwrap();
1787 let detector_error = simulator.compile_sampling_plan(&[9], &[2]).unwrap_err();
1788 assert_eq!(
1789 detector_error.message(),
1790 "packed DEM sampler requested detector id 9, but it is not declared by the DEM"
1791 );
1792 let observable_error = simulator.compile_sampling_plan(&[1], &[9]).unwrap_err();
1793 assert_eq!(
1794 observable_error.message(),
1795 "packed DEM sampler requested observable id 9, but it is not declared by the DEM"
1796 );
1797 }
1798
1799 #[test]
1800 fn compiled_sampling_rejects_duplicate_detector_layout() {
1801 let simulator = DemHotspotEstimator::from_sampling_parts(
1802 vec![1],
1803 vec![2],
1804 vec![edge(0.5, vec![1], vec![2])],
1805 )
1806 .unwrap();
1807
1808 let error = simulator.compile_sampling_plan(&[1, 1], &[2]).unwrap_err();
1809
1810 assert_eq!(
1811 error.message(),
1812 "decoder detector ids must be unique; duplicate detector id 1"
1813 );
1814 }
1815
1816 #[test]
1817 fn compiled_sampling_rejects_duplicate_detail_detector_layout() {
1818 let simulator = DemHotspotEstimator::from_sampling_parts(
1819 vec![1],
1820 vec![2],
1821 vec![edge(0.5, vec![1], vec![2])],
1822 )
1823 .unwrap();
1824
1825 let error = simulator
1826 .compile_decoder_sampling_plan(&[1], &[2], DetectorBatchFormat::Packed, &[1, 1], false)
1827 .unwrap_err();
1828
1829 assert_eq!(
1830 error.message(),
1831 "decoder detector ids must be unique; duplicate detector id 1"
1832 );
1833 }
1834
1835 #[test]
1836 fn compiled_sampling_rejects_duplicate_observable_layout() {
1837 let simulator = DemHotspotEstimator::from_sampling_parts(
1838 vec![1],
1839 vec![2],
1840 vec![edge(0.5, vec![1], vec![2])],
1841 )
1842 .unwrap();
1843
1844 let error = simulator.compile_sampling_plan(&[1], &[2, 2]).unwrap_err();
1845
1846 assert_eq!(
1847 error.message(),
1848 "decoder observable ids must be unique; duplicate observable id 2"
1849 );
1850 }
1851
1852 #[test]
1853 fn groups_edges_by_location() {
1854 let edges = vec![
1855 DetectorErrorEdge {
1856 probability: 0.1,
1857 detectors: vec![0],
1858 observables: Vec::new(),
1859 location_id: "a".to_string(),
1860 event: crate::DemEvent::Pauli("X".to_string()),
1861 tags: HashMap::new(),
1862 },
1863 DetectorErrorEdge {
1864 probability: 0.2,
1865 detectors: vec![1],
1866 observables: Vec::new(),
1867 location_id: "a".to_string(),
1868 event: crate::DemEvent::Pauli("Z".to_string()),
1869 tags: HashMap::new(),
1870 },
1871 ];
1872
1873 let groups = DemHotspotEstimator::from_parts(Vec::new(), Vec::new(), edges)
1874 .unwrap()
1875 .location_groups();
1876
1877 assert_eq!(groups.len(), 1);
1878 assert_eq!(groups[0].edge_indices, vec![0, 1]);
1879 assert_eq!(groups[0].total_probability, 0.30000000000000004);
1880 }
1881
1882 #[test]
1883 fn simulator_estimates_default_logical_loss() {
1884 let simulator = DemHotspotEstimator::from_parts(
1885 Vec::new(),
1886 vec![0],
1887 vec![DetectorErrorEdge {
1888 probability: 1.0,
1889 detectors: Vec::new(),
1890 observables: vec![0],
1891 location_id: "logical".to_string(),
1892 event: crate::DemEvent::Pauli("L".to_string()),
1893 tags: HashMap::new(),
1894 }],
1895 )
1896 .unwrap();
1897
1898 let estimate = simulator.estimate_default(64, Some(7), None, 1).unwrap();
1899
1900 assert_eq!(estimate.shots, 64);
1901 assert_eq!(estimate.mean_loss, 1.0);
1902 assert_eq!(estimate.top_edges, vec![0]);
1903 assert_eq!(estimate.top_locations, vec!["logical"]);
1904 }
1905
1906 #[test]
1907 fn simulator_hotspot_rejects_unrecorded_foreign_and_invalid_loss_batches() {
1908 let make_simulator = || {
1909 DemHotspotEstimator::from_parts(
1910 Vec::new(),
1911 vec![0],
1912 vec![edge(0.25, Vec::new(), vec![0])],
1913 )
1914 .unwrap()
1915 };
1916 let simulator = make_simulator();
1917
1918 let batch = simulator.run_batch(8, Some(1), false).unwrap();
1919 let err = simulator
1920 .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1921 .unwrap_err();
1922 assert!(err.to_string().contains("recorded event masks"));
1923
1924 let batch = simulator.run_batch(8, Some(1), true).unwrap();
1925 let foreign = make_simulator();
1926 let err = foreign
1927 .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1928 .unwrap_err();
1929 assert!(err.to_string().contains("layout does not match"));
1930 simulator
1931 .clone()
1932 .estimate_from_loss(&batch, &batch.loss_mask, None, 1)
1933 .unwrap();
1934
1935 let err = simulator
1936 .estimate_from_loss(&batch, &Mask::zero(2), None, 1)
1937 .unwrap_err();
1938 assert!(err.to_string().contains("loss_mask has 2 words"));
1939
1940 let mut rng = SmallRng::new(1);
1941 let zero_shot_batch = simulator.run_batch_with_rng(0, &mut rng, true);
1942 let err = simulator
1943 .estimate_from_loss(&zero_shot_batch, &zero_shot_batch.loss_mask, None, 1)
1944 .unwrap_err();
1945 assert!(err.to_string().contains("shots to be positive"));
1946 }
1947
1948 #[test]
1949 fn simulator_rejects_invalid_edge_probability() {
1950 let err = DemHotspotEstimator::from_parts(
1951 Vec::new(),
1952 Vec::new(),
1953 vec![DetectorErrorEdge {
1954 probability: 1.5,
1955 detectors: Vec::new(),
1956 observables: Vec::new(),
1957 location_id: "bad".to_string(),
1958 event: crate::DemEvent::Pauli("X".to_string()),
1959 tags: HashMap::new(),
1960 }],
1961 )
1962 .unwrap_err();
1963
1964 assert!(err
1965 .message()
1966 .contains("DEM edge probability must be in [0, 1]"));
1967 }
1968}