1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
use ndarray::{Array1, Array2, ArrayView1, ArrayView2};
use crate::bit_packing::required_packed_bytes;
use crate::types::{
BatchDecodeResult, DecodeOptions, DecodeResult, GapBatchPrediction, GapPrediction,
MatchedDetectors, NoiseSample,
};
use crate::{Matching, MatchingError, Result};
impl Matching {
/// Decodes one binary syndrome with raw minimum-weight perfect matching.
///
/// `syndrome[i]` is the detection-event bit for detector node `i`. The
/// returned vector is indexed by fault id: bit `j` is one exactly when the
/// selected correction toggles fault id `j` an odd number of times.
///
/// # Errors
///
/// Returns an error for an invalid syndrome shape or when no correction is
/// consistent with the syndrome.
pub fn decode(&self, syndrome: ArrayView1<'_, u8>) -> Result<Array1<u8>> {
Ok(self
.decode_with_options(syndrome, DecodeOptions::new())?
.prediction)
}
/// Decodes one syndrome with explicit weight and correlation options.
///
/// Set [`DecodeOptions::with_return_weight`] to include the sum of selected
/// edge weights. Set [`DecodeOptions::with_enable_correlations`] for native
/// two-pass correlated matching; this requires a graph constructed with
/// correlations enabled. Bit-packing options apply only to batch decoding.
///
/// ```
/// use ndarray::array;
/// use pymatching::{DecodeOptions, EdgeData, Matching};
///
/// let mut matching = Matching::default();
/// matching.add_boundary_edge(0, EdgeData::new(vec![0]).with_weight(2.0))?;
/// let result = matching.decode_with_options(
/// array![1_u8].view(),
/// DecodeOptions::new().with_return_weight(true),
/// )?;
/// assert_eq!(result.prediction.to_vec(), vec![1]);
/// assert_eq!(result.weight, Some(2.0));
/// # Ok::<(), pymatching::MatchingError>(())
/// ```
pub fn decode_with_options(
&self,
syndrome: ArrayView1<'_, u8>,
options: DecodeOptions,
) -> Result<DecodeResult> {
let raw = with_contiguous_1d(syndrome, |syndrome| {
self.decode_syndrome_with_options_raw(syndrome, options)
})?;
Ok(DecodeResult {
prediction: Array1::from_vec(raw.prediction),
weight: raw.has_weight.then_some(raw.weight),
})
}
/// Decodes both logical classes and returns a hard prediction plus GAP.
///
/// The prediction is exactly the underlying hard decoder's prediction. For
/// each logical observable, the decoder also solves the complementary class,
/// and `gaps` contains the absolute difference between the two weights.
///
/// Logical cuts are inferred from edge fault ids. Detector coordinates and
/// Pauli-basis annotations are not used, so the same method handles X- and
/// Z-basis memory experiments. Every observable must define one connected
/// graph cut, and the matching must come from an unmodified detector error
/// model. Correlations are used automatically when the matching was built
/// with them enabled.
///
/// ```
/// use ndarray::array;
/// use pymatching::Matching;
///
/// let dem: stim::DetectorErrorModel = "\
/// error(0.1) D0 L0\n\
/// error(0.1) D0 D1\n\
/// error(0.2) D1\n".parse()?;
/// let matching = Matching::from_detector_error_model_with_options(&dem, false)?;
/// let result = matching.decode_gap(array![1_u8, 0].view())?;
/// assert_eq!(result.prediction.len(), 1);
/// assert!(result.gaps[0] >= 0.0);
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn decode_gap(&self, syndrome: ArrayView1<'_, u8>) -> Result<GapPrediction> {
let raw = with_contiguous_1d(syndrome, |syndrome| self.decode_gap_raw(syndrome))?;
Ok(GapPrediction {
prediction: Array1::from_vec(raw.prediction),
gaps: Array1::from_vec(raw.gaps),
})
}
/// Decodes both logical classes for every shot and returns predictions and gaps.
///
/// `shots` must be an unpacked binary array with shape
/// `(num_shots, self.num_detectors())`; GAP batch decoding does not use the
/// bit-packing options from [`DecodeOptions`].
///
/// Both returned arrays have shape `(shots.nrows(), self.num_fault_ids())`.
/// See [`Matching::decode_gap`] for graph requirements and GAP semantics.
///
/// ```
/// use ndarray::array;
/// use pymatching::Matching;
///
/// let dem: stim::DetectorErrorModel = "\
/// error(0.1) D0 L0\n\
/// error(0.1) D0 D1\n\
/// error(0.2) D1\n".parse()?;
/// let matching = Matching::from_detector_error_model_with_options(&dem, false)?;
/// let result = matching.decode_gap_batch(array![[0_u8, 0], [1, 0]].view())?;
/// assert_eq!(result.predictions.dim(), (2, 1));
/// assert_eq!(result.gaps.dim(), (2, 1));
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn decode_gap_batch(&self, shots: ArrayView2<'_, u8>) -> Result<GapBatchPrediction> {
let num_rows = shots.nrows();
let raw = with_contiguous_2d(shots, |shots, rows, cols| {
self.decode_gap_batch_raw(shots, rows, cols)
})?;
if raw.rows as usize != num_rows || raw.cols as usize != self.num_fault_ids() {
return Err(MatchingError::Upstream(
"bridge returned an invalid GAP batch shape".to_string(),
));
}
Ok(GapBatchPrediction {
predictions: array2_from_u8(raw.predictions, raw.rows, raw.cols)?,
gaps: array2_from_f64(raw.gaps, raw.rows, raw.cols)?,
})
}
/// Decodes a batch of unpacked binary syndromes with raw matching.
///
/// `shots` has shape `(num_shots, syndrome_length)`. The returned array has
/// shape `(num_shots, self.num_fault_ids())`.
///
/// ```
/// use ndarray::array;
/// use pymatching::{EdgeData, Matching};
///
/// let mut matching = Matching::default();
/// matching.add_boundary_edge(0, EdgeData::new(vec![0]))?;
/// let predictions = matching.decode_batch(array![[0_u8], [1]].view())?;
/// assert_eq!(predictions, array![[0_u8], [1]]);
/// # Ok::<(), pymatching::MatchingError>(())
/// ```
pub fn decode_batch(&self, shots: ArrayView2<'_, u8>) -> Result<Array2<u8>> {
Ok(self
.decode_batch_with_options(shots, DecodeOptions::new())?
.predictions)
}
/// Decodes a batch with optional packing, weights, and correlations.
///
/// Unpacked shots are shaped `(num_shots, syndrome_length)`. Packed shots
/// use little-endian bits within each byte and normally have width
/// `ceil(self.num_detectors() / 8)`. Unpacked predictions are shaped
/// `(num_shots, self.num_fault_ids())`; packed predictions have width
/// `ceil(self.num_fault_ids() / 8)`.
///
/// Native correlated matching is selected by
/// [`DecodeOptions::with_enable_correlations`]. The matching must also have
/// been built with correlations enabled.
///
/// ```
/// use ndarray::array;
/// use pymatching::{DecodeOptions, Matching};
///
/// let dem: stim::DetectorErrorModel = "\
/// error(0.1) D0 L0\n\
/// error(0.1) D0 D1\n\
/// error(0.2) D1\n".parse()?;
/// let matching = Matching::from_detector_error_model_with_options(&dem, true)?;
/// let result = matching.decode_batch_with_options(
/// array![[0_u8, 0], [1, 0]].view(),
/// DecodeOptions::new().with_enable_correlations(true),
/// )?;
/// assert_eq!(result.predictions.dim(), (2, 1));
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
pub fn decode_batch_with_options(
&self,
shots: ArrayView2<'_, u8>,
options: DecodeOptions,
) -> Result<BatchDecodeResult> {
let num_rows = shots.nrows();
let raw = with_contiguous_2d(shots, |shots, rows, cols| {
self.decode_batch_with_options_raw(shots, rows, cols, options)
})?;
if raw.prediction_rows as usize != num_rows {
return Err(MatchingError::Upstream(
"bridge returned an invalid batch prediction row count".to_string(),
));
}
let predictions =
array2_from_u8(raw.predictions, raw.prediction_rows, raw.prediction_cols)?;
let expected_cols = if options.bit_packed_predictions {
required_packed_bytes(self.num_fault_ids())
} else {
self.num_fault_ids()
};
if predictions.ncols() != expected_cols {
return Err(MatchingError::Upstream(
"bridge returned an invalid batch prediction width".to_string(),
));
}
if raw.has_weights && raw.weights.len() != num_rows {
return Err(MatchingError::Upstream(
"bridge returned an invalid batch weight count".to_string(),
));
}
let weights = raw.has_weights.then(|| Array1::from_vec(raw.weights));
Ok(BatchDecodeResult {
predictions,
weights,
})
}
/// Decodes a batch and always returns one matching weight per shot.
///
/// This is a convenience wrapper over [`Matching::decode_batch_with_options`]
/// that enables `return_weight` while preserving the other options.
pub fn decode_batch_with_weights(
&self,
shots: ArrayView2<'_, u8>,
options: DecodeOptions,
) -> Result<(Array2<u8>, Array1<f64>)> {
let result = self.decode_batch_with_options(shots, options.with_return_weight(true))?;
let weights = result.weights.ok_or(MatchingError::Upstream(
"bridge did not return batch weights".to_string(),
))?;
Ok((result.predictions, weights))
}
/// Returns every graph edge in a raw matching correction.
///
/// The result has shape `(num_selected_edges, 2)`. Each row contains two
/// detector indices; the second value is `-1` for an edge to any boundary.
pub fn decode_to_edges_array(&self, syndrome: ArrayView1<'_, u8>) -> Result<Array2<i64>> {
self.decode_to_edges_array_with_options(syndrome, DecodeOptions::new())
}
/// Returns every correction edge with optional native correlations.
///
/// Only [`DecodeOptions::with_enable_correlations`] affects this method.
/// See [`Matching::decode_to_edges_array`] for the output format.
pub fn decode_to_edges_array_with_options(
&self,
syndrome: ArrayView1<'_, u8>,
options: DecodeOptions,
) -> Result<Array2<i64>> {
let raw = with_contiguous_1d(syndrome, |syndrome| {
self.decode_to_edges_array_raw(syndrome, options.enable_correlations)
})?;
array2_from_i64(raw.data, raw.rows, raw.cols)
}
/// Returns the detection-event pairs selected by raw matching.
///
/// Each row is a pair of active detectors, or `(detector, -1)` when an
/// event is matched to a boundary. Unlike edge-array decoding, this reports
/// matched event endpoints rather than every edge along their shortest
/// paths. Negative graph weights are not supported by this method.
pub fn decode_to_matched_dets_array(
&self,
syndrome: ArrayView1<'_, u8>,
) -> Result<Array2<i64>> {
let raw = with_contiguous_1d(syndrome, |syndrome| {
self.decode_to_matched_dets_array_raw(syndrome)
})?;
array2_from_i64(raw.data, raw.rows, raw.cols)
}
/// Returns detection-event matches as a map.
///
/// Both members of a detector pair are keys mapped to each other. A
/// detector matched to a boundary maps to `None`.
pub fn decode_to_matched_dets_dict(
&self,
syndrome: ArrayView1<'_, u8>,
) -> Result<MatchedDetectors> {
let pairs = self.decode_to_matched_dets_array(syndrome)?;
let mut matched = MatchedDetectors::with_capacity(pairs.nrows() * 2);
for pair in pairs.outer_iter() {
let detector = pair[0] as usize;
let mate = pair[1];
if mate == -1 {
matched.insert(detector, None);
} else if mate >= 0 {
let mate = mate as usize;
matched.insert(detector, Some(mate));
matched.insert(mate, Some(detector));
} else {
return Err(MatchingError::Upstream(
"bridge returned an invalid matched-detector index".to_string(),
));
}
}
Ok(matched)
}
/// Samples independent edge noise using each edge's error probability.
///
/// Returns `None` unless every edge has an `error_probability`. A supplied
/// seed makes the sample reproducible. Explicit boundary-node syndrome bits
/// are always zero.
pub fn add_noise(&self, seed: Option<u64>) -> Result<Option<NoiseSample>> {
let raw = self.add_noise_raw(seed)?;
if !raw.has_noise {
return Ok(None);
}
Ok(Some(NoiseSample {
errors: Array1::from_vec(raw.errors),
syndrome: Array1::from_vec(raw.syndrome),
}))
}
}
fn with_contiguous_1d<T>(
array: ArrayView1<'_, u8>,
operation: impl FnOnce(&[u8]) -> Result<T>,
) -> Result<T> {
if let Some(slice) = array.as_slice() {
operation(slice)
} else {
operation(&array.iter().copied().collect::<Vec<_>>())
}
}
fn with_contiguous_2d<T>(
array: ArrayView2<'_, u8>,
operation: impl FnOnce(&[u8], usize, usize) -> Result<T>,
) -> Result<T> {
let rows = array.nrows();
let cols = array.ncols();
if let Some(slice) = array.as_slice() {
operation(slice, rows, cols)
} else {
operation(&array.iter().copied().collect::<Vec<_>>(), rows, cols)
}
}
fn array2_from_u8(data: Vec<u8>, rows: u64, cols: u64) -> Result<Array2<u8>> {
Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
MatchingError::Upstream("bridge returned an invalid u8 matrix shape".to_string())
})
}
fn array2_from_i64(data: Vec<i64>, rows: u64, cols: u64) -> Result<Array2<i64>> {
Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
MatchingError::Upstream("bridge returned an invalid i64 matrix shape".to_string())
})
}
fn array2_from_f64(data: Vec<f64>, rows: u64, cols: u64) -> Result<Array2<f64>> {
Array2::from_shape_vec((rows as usize, cols as usize), data).map_err(|_| {
MatchingError::Upstream("bridge returned an invalid f64 matrix shape".to_string())
})
}