Skip to main content

faultscope_core/dem/
event_plan.rs

1use std::ops::Range;
2use std::sync::Arc;
3
4use crate::program::{ExpandedOperation, ExpandedProgram, ExpansionMode};
5use crate::{DemEvent, IndexedNoiseLocation, NoiseModel, NpError, NpResult, Operation};
6
7/// Controls circuit-to-DEM conversions that cannot preserve a disjoint noise
8/// channel exactly using independent DEM instructions.
9///
10/// The default forbids fallback approximation. A positive threshold opts into
11/// Stim-compatible independent approximation of multi-component
12/// [`NoiseModel::PauliChannel`] locations when every component probability is
13/// at most the threshold. Stim's exact one-qubit conversion is attempted first.
14#[derive(Debug, Clone, Copy, PartialEq)]
15pub struct DemGenerationOptions {
16    approximate_disjoint_errors_threshold: f64,
17}
18
19impl DemGenerationOptions {
20    /// Construct strict DEM-generation options.
21    pub const fn strict() -> Self {
22        Self {
23            approximate_disjoint_errors_threshold: 0.0,
24        }
25    }
26
27    /// Construct options permitting independent approximation up to `threshold`.
28    pub fn new(threshold: f64) -> NpResult<Self> {
29        if !threshold.is_finite() || !(0.0..=1.0).contains(&threshold) {
30            return Err(NpError::new(format!(
31                "approximate_disjoint_errors must be a finite probability in [0, 1], got {threshold}"
32            )));
33        }
34        Ok(Self {
35            approximate_disjoint_errors_threshold: threshold,
36        })
37    }
38
39    /// Largest disjoint component probability accepted for approximation.
40    pub const fn approximate_disjoint_errors_threshold(self) -> f64 {
41        self.approximate_disjoint_errors_threshold
42    }
43}
44
45impl Default for DemGenerationOptions {
46    fn default() -> Self {
47        Self::strict()
48    }
49}
50
51#[derive(Debug, Clone, PartialEq)]
52pub struct DemEventPlan {
53    pub(super) program: Arc<ExpandedProgram>,
54    pub(super) fault_events: Vec<DemFaultEvent>,
55    pub(super) fault_event_range_by_noise: Vec<Range<usize>>,
56}
57
58impl DemEventPlan {
59    pub(super) fn measurement_noise_event_range(&self, noise_id: Option<usize>) -> Range<usize> {
60        let range = noise_id
61            .map(|noise_id| self.fault_event_range_by_noise[noise_id].clone())
62            .unwrap_or(0..0);
63        debug_assert!(range.clone().all(|event_index| matches!(
64            &self.fault_events[event_index].event,
65            DemEvent::Bool(true)
66        )));
67        range
68    }
69}
70
71#[derive(Debug, Clone, PartialEq)]
72pub(super) struct DemFaultEvent {
73    pub(super) noise_id: usize,
74    pub(super) event: DemEvent,
75    pub(super) probability: f64,
76    pub(super) sibling_semantics: DemFaultEventSiblingSemantics,
77}
78
79#[derive(Debug, Clone, Copy, PartialEq, Eq)]
80pub(super) enum DemFaultEventSiblingSemantics {
81    None,
82    Independent,
83    Disjoint,
84}
85
86pub fn collect_dem_event_plan(operations: &[Operation]) -> NpResult<DemEventPlan> {
87    collect_dem_event_plan_with_options(operations, DemGenerationOptions::default())
88}
89
90/// Compile a DEM event plan with explicit disjoint-channel handling options.
91pub fn collect_dem_event_plan_with_options(
92    operations: &[Operation],
93    options: DemGenerationOptions,
94) -> NpResult<DemEventPlan> {
95    let program = crate::program::expand_operations(operations, ExpansionMode::Dem)?;
96    collect_dem_event_plan_from_program_with_options(program, options)
97}
98
99pub(super) fn collect_dem_event_plan_from_program_with_options(
100    program: ExpandedProgram,
101    options: DemGenerationOptions,
102) -> NpResult<DemEventPlan> {
103    let program = Arc::new(program);
104    let (fault_events, fault_event_range_by_noise) = collect_dem_fault_events(&program, options)?;
105    Ok(DemEventPlan {
106        program,
107        fault_events,
108        fault_event_range_by_noise,
109    })
110}
111
112fn collect_dem_fault_events(
113    program: &ExpandedProgram,
114    options: DemGenerationOptions,
115) -> NpResult<(Vec<DemFaultEvent>, Vec<Range<usize>>)> {
116    let mut fault_events = Vec::new();
117    let mut fault_event_range_by_noise = vec![0..0; program.noise_locations.len()];
118    for operation in &program.operations {
119        match operation {
120            ExpandedOperation::Noise(noise_id) => {
121                fault_event_range_by_noise[*noise_id] = collect_dem_fault_events_for_location(
122                    &mut fault_events,
123                    *noise_id,
124                    &program.noise_locations[*noise_id],
125                    options,
126                )?;
127            }
128            ExpandedOperation::MeasureSingle {
129                noise: Some(noise_id),
130                ..
131            }
132            | ExpandedOperation::MeasurePauli {
133                noise: Some(noise_id),
134                ..
135            } => {
136                let location = &program.noise_locations[*noise_id];
137                if !matches!(location.model, NoiseModel::MeasurementBitFlip) {
138                    return Err(NpError::new(
139                        "DEM generation currently supports MeasurementBitFlip on measurement operations",
140                    ));
141                }
142                fault_event_range_by_noise[*noise_id] = collect_dem_fault_events_for_location(
143                    &mut fault_events,
144                    *noise_id,
145                    location,
146                    options,
147                )?;
148            }
149            _ => {}
150        }
151    }
152    Ok((fault_events, fault_event_range_by_noise))
153}
154
155fn collect_dem_fault_events_for_location(
156    fault_events: &mut Vec<DemFaultEvent>,
157    noise_id: usize,
158    location: &IndexedNoiseLocation,
159    options: DemGenerationOptions,
160) -> NpResult<Range<usize>> {
161    let start = fault_events.len();
162    for (event, probability, sibling_semantics) in non_identity_events(location, options)? {
163        fault_events.push(DemFaultEvent {
164            noise_id,
165            event,
166            probability,
167            sibling_semantics,
168        });
169    }
170    Ok(start..fault_events.len())
171}
172
173fn non_identity_events(
174    location: &IndexedNoiseLocation,
175    options: DemGenerationOptions,
176) -> NpResult<Vec<(DemEvent, f64, DemFaultEventSiblingSemantics)>> {
177    match &location.model {
178        NoiseModel::BernoulliPauli(pauli) => Ok(vec![(
179            DemEvent::Pauli(pauli.clone()),
180            location.rate,
181            DemFaultEventSiblingSemantics::None,
182        )]),
183        NoiseModel::MeasurementBitFlip => Ok(vec![(
184            DemEvent::Bool(true),
185            location.rate,
186            DemFaultEventSiblingSemantics::None,
187        )]),
188        NoiseModel::SingleQubitDepolarizing => {
189            let probability = independent_depolarizing_component_probability(
190                location.rate,
191                4,
192                "SingleQubitDepolarizing",
193            )?;
194            Ok(["X", "Y", "Z"]
195                .iter()
196                .map(|event| {
197                    (
198                        DemEvent::Pauli((*event).to_string()),
199                        probability,
200                        DemFaultEventSiblingSemantics::Independent,
201                    )
202                })
203                .collect())
204        }
205        NoiseModel::TwoQubitDepolarizing => {
206            let fault_events = [
207                "IX", "IY", "IZ", "XI", "XX", "XY", "XZ", "YI", "YX", "YY", "YZ", "ZI", "ZX", "ZY",
208                "ZZ",
209            ];
210            let probability = independent_depolarizing_component_probability(
211                location.rate,
212                16,
213                "TwoQubitDepolarizing",
214            )?;
215            Ok(fault_events
216                .iter()
217                .map(|event| {
218                    (
219                        DemEvent::Pauli((*event).to_string()),
220                        probability,
221                        DemFaultEventSiblingSemantics::Independent,
222                    )
223                })
224                .collect())
225        }
226        NoiseModel::PauliChannel(weights) => {
227            let total: f64 = weights.iter().map(|(_, weight)| *weight).sum();
228            if total <= 0.0 {
229                return Err(NpError::new(
230                    "PauliChannel weights must have positive total weight",
231                ));
232            }
233            // A PauliChannel is categorical in the forward sampler.  DEM
234            // instructions are independent, so match Stim by requiring either
235            // its exact one-qubit conversion or explicit fallback
236            // approximation. Combine duplicate Pauli labels first so a Rust
237            // caller cannot turn one physical outcome into a false
238            // multi-component channel merely by repeating its label.
239            let mut event_weights: Vec<(String, f64)> = Vec::new();
240            for (event, weight) in weights.iter().filter(|(_, weight)| *weight > 0.0) {
241                if let Some((_, existing_weight)) = event_weights
242                    .iter_mut()
243                    .find(|(existing_event, _)| existing_event == event)
244                {
245                    *existing_weight += *weight;
246                } else {
247                    event_weights.push((event.clone(), *weight));
248                }
249            }
250            let events = event_weights
251                .into_iter()
252                .map(|(event, weight)| (event, location.rate * (weight / total)))
253                .collect::<Vec<_>>();
254
255            let positive_probability_count = if location.rate > 0.0 { events.len() } else { 0 };
256            if positive_probability_count <= 1 {
257                return Ok(events
258                    .into_iter()
259                    .map(|(event, probability)| {
260                        (
261                            DemEvent::Pauli(event),
262                            probability,
263                            DemFaultEventSiblingSemantics::None,
264                        )
265                    })
266                    .collect());
267            }
268
269            // Stim first tries to turn PAULI_CHANNEL_1 into independent X, Y,
270            // and Z mechanisms exactly.  PAULI_CHANNEL_2 (and FaultScope's
271            // wider generic PauliChannel) does not have this special case.
272            if events[0].0.len() == 1 {
273                let mut disjoint = [0.0; 3];
274                for (event, probability) in &events {
275                    let index = match event.as_str() {
276                        "X" => 0,
277                        "Y" => 1,
278                        "Z" => 2,
279                        _ => unreachable!("validated one-qubit PauliChannel event"),
280                    };
281                    disjoint[index] = *probability;
282                }
283                if let Some(independent) =
284                    try_disjoint_to_independent_xyz_errors(disjoint[0], disjoint[1], disjoint[2])
285                {
286                    return Ok(["X", "Y", "Z"]
287                        .into_iter()
288                        .zip(independent)
289                        .filter(|(_, probability)| *probability > 0.0)
290                        .map(|(event, probability)| {
291                            (
292                                DemEvent::Pauli(event.to_string()),
293                                probability,
294                                DemFaultEventSiblingSemantics::Independent,
295                            )
296                        })
297                        .collect());
298                }
299            }
300
301            let largest_probability = events
302                .iter()
303                .map(|(_, probability)| *probability)
304                .fold(0.0_f64, f64::max);
305            let threshold = options.approximate_disjoint_errors_threshold();
306            let comparison_slack = 8.0 * f64::EPSILON * largest_probability.max(threshold);
307            let exceeds_threshold = if threshold == 0.0 {
308                true
309            } else {
310                largest_probability - threshold > comparison_slack
311            };
312            if exceeds_threshold {
313                return Err(NpError::new(format!(
314                    "PauliChannel has multiple disjoint outcomes, including component probability {largest_probability}, which cannot be represented exactly by independent DEM edges; set approximate_disjoint_errors=True, or set it to a probability threshold at least {largest_probability}, to enable Stim-compatible approximation"
315                )));
316            }
317
318            Ok(events
319                .into_iter()
320                .map(|(event, probability)| {
321                    (
322                        DemEvent::Pauli(event),
323                        probability,
324                        DemFaultEventSiblingSemantics::Disjoint,
325                    )
326                })
327                .collect())
328        }
329    }
330}
331
332/// Try Stim's exact PAULI_CHANNEL_1 conversion into independent X/Y/Z errors.
333///
334/// `None` means no sufficiently accurate independent representation was found;
335/// callers may then use the explicitly enabled disjoint approximation.
336fn try_disjoint_to_independent_xyz_errors(x: f64, y: f64, z: f64) -> Option<[f64; 3]> {
337    fn solve(x: f64, y: f64, z: f64, max_steps: usize) -> Option<[f64; 3]> {
338        let identity = (1.0 - x - y - z).max(0.0);
339        if identity < x {
340            let [independent_x, independent_y, independent_z] = solve(identity, z, y, max_steps)?;
341            return Some([1.0 - independent_x, independent_y, independent_z]);
342        }
343        if identity < y {
344            let [independent_x, independent_y, independent_z] = solve(z, identity, x, max_steps)?;
345            return Some([independent_x, 1.0 - independent_y, independent_z]);
346        }
347        if identity < z {
348            let [independent_x, independent_y, independent_z] = solve(y, x, identity, max_steps)?;
349            return Some([independent_x, independent_y, 1.0 - independent_z]);
350        }
351
352        if x + z < 0.5 && x + y < 0.5 && y + z < 0.5 {
353            let sqrt_xz = (1.0 - 2.0 * x - 2.0 * z).sqrt();
354            let sqrt_xy = (1.0 - 2.0 * x - 2.0 * y).sqrt();
355            let sqrt_yz = (1.0 - 2.0 * y - 2.0 * z).sqrt();
356            let independent_x = 0.5 - 0.5 * sqrt_xz * sqrt_xy / sqrt_yz;
357            let independent_y = 0.5 - 0.5 * sqrt_xy * sqrt_yz / sqrt_xz;
358            let independent_z = 0.5 - 0.5 * sqrt_xz * sqrt_yz / sqrt_xy;
359            if independent_x >= 0.0 && independent_y >= 0.0 && independent_z >= 0.0 {
360                return Some([independent_x, independent_y, independent_z]);
361            }
362        }
363
364        let mut independent_x = x;
365        let mut independent_y = y;
366        let mut independent_z = z;
367        for _ in 0..max_steps {
368            let xy = independent_x * independent_y;
369            let xz = independent_x * independent_z;
370            let yz = independent_y * independent_z;
371            let not_x = 1.0 - independent_x;
372            let not_y = 1.0 - independent_y;
373            let not_z = 1.0 - independent_z;
374            let not_xy = not_x * not_y;
375            let not_xz = not_x * not_z;
376            let not_yz = not_y * not_z;
377            let actual_x = independent_x * not_yz + not_x * yz;
378            let actual_y = independent_y * not_xz + not_y * xz;
379            let actual_z = independent_z * not_xy + not_z * xy;
380            let error_x = actual_x - x;
381            let error_y = actual_y - y;
382            let error_z = actual_z - z;
383            if error_x.abs() + error_y.abs() + error_z.abs() < 1e-14 {
384                return Some([independent_x, independent_y, independent_z]);
385            }
386
387            let derivative_x = not_yz - yz;
388            let derivative_y = not_xz - xz;
389            let derivative_z = not_xy - xy;
390            independent_x -= error_x / derivative_x;
391            independent_y -= error_y / derivative_y;
392            independent_z -= error_z / derivative_z;
393            if independent_x < 0.0 {
394                independent_x = 0.0;
395            }
396            if independent_y < 0.0 {
397                independent_y = 0.0;
398            }
399            if independent_z < 0.0 {
400                independent_z = 0.0;
401            }
402        }
403        None
404    }
405
406    solve(x, y, z, 50)
407}
408
409/// Reparameterize an n-qubit uniform depolarizing channel into independent
410/// Bernoulli factors over every non-identity Pauli, as Stim does during DEM
411/// analysis.  `group_size` is 4^n.
412fn independent_depolarizing_component_probability(
413    rate: f64,
414    group_size: usize,
415    model_name: &str,
416) -> NpResult<f64> {
417    let group_size = group_size as f64;
418    let maximum_exact_rate = (group_size - 1.0) / group_size;
419    if rate > maximum_exact_rate {
420        return Err(NpError::new(format!(
421            "{model_name} rate {rate} exceeds {maximum_exact_rate}, the largest rate representable exactly by independent DEM edges"
422        )));
423    }
424    if rate == 0.0 {
425        return Ok(0.0);
426    }
427
428    // lambda = 1 - group_size * rate / (group_size - 1) is every
429    // non-trivial Fourier coefficient of the categorical depolarizing
430    // distribution.  Independent factors give
431    // lambda = (1 - 2q)^(group_size / 2).  ln_1p/exp_m1 retain accuracy for
432    // very small rates.
433    let log_lambda = (-group_size * rate / (group_size - 1.0)).ln_1p();
434    Ok(-0.5 * ((2.0 / group_size) * log_lambda).exp_m1())
435}