bloq_circuit/
semantic.rs

1use std::cmp::Ordering;
2
3use glam::IVec2;
4use smallvec::SmallVec;
5
6use crate::{CoordinateOverflowError, GateType, PauliBasis, PauliMap};
7
8/// Translate one coordinate without wrapping outside the signed 32-bit
9/// lattice.
10///
11/// # Errors
12///
13/// Returns [`CoordinateOverflowError`] if either translated component overflows.
14pub fn checked_translate_coordinate(
15    coordinate: IVec2,
16    offset: IVec2,
17) -> Result<IVec2, CoordinateOverflowError> {
18    coordinate
19        .x
20        .checked_add(offset.x)
21        .zip(coordinate.y.checked_add(offset.y))
22        .map(|(x, y)| IVec2::new(x, y))
23        .ok_or(CoordinateOverflowError { coordinate, offset })
24}
25
26/// Index of a [`CircuitBody`] within a [`CoordCircuit`](crate::CoordCircuit).
27#[derive(
28    Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, serde::Serialize, serde::Deserialize,
29)]
30pub struct BodyId(pub u32);
31
32/// One feedforward correction inside [`Op::ConditionalPauli`].
33///
34/// Apply `pauli` to `target` iff measurement record `control` is 1. Bundling the fields
35/// makes the per-correction invariant true by construction (no parallel-array
36/// desync). `control` is a template-local measurement id, remapped through
37/// instantiation like any other.
38#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
39pub struct ConditionalCorrection {
40    /// Pauli applied to the target.
41    pub pauli: PauliBasis,
42    /// Measurement id controlling the correction.
43    pub control: u32,
44    /// Corrected qubit coordinate.
45    pub target: IVec2,
46}
47
48/// A measurement id paired with the qubit coordinate it measured.
49#[derive(Debug, Clone, Copy, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
50pub struct MeasRecord {
51    /// The measurement's stable id.
52    pub id: u32,
53    /// The qubit that was measured.
54    pub qubit: IVec2,
55}
56
57/// Allocator and lookup table for a circuit's measurement ids.
58///
59/// Records are kept strictly sorted by id. Dense ids use direct indexing;
60/// sparse lookups fall back to binary search. On the wire only the records are
61/// stored; the next-id counter is recomputed on decode (see the serde impls)
62/// rather than trusted.
63#[derive(Debug, Clone, Default, PartialEq, Eq)]
64pub struct MeasRegistry {
65    records: Vec<MeasRecord>,
66    next_id: u32,
67}
68
69// Manual impls: the wire carries only the records. `next_id` is derived
70// state — every mutation path leaves it at `last record id + 1` (or 0 when
71// empty) — so it is recomputed on decode rather than trusted from untrusted
72// bytes, where a low value would make `allocate` hand out duplicate ids.
73// Sortedness is likewise an invariant of the constructors (binary searches
74// rely on it), so unsorted wire data is rejected.
75impl serde::Serialize for MeasRegistry {
76    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
77        self.records.serialize(serializer)
78    }
79}
80
81impl<'de> serde::Deserialize<'de> for MeasRegistry {
82    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
83        let records = Vec::<MeasRecord>::deserialize(deserializer)?;
84        if !records.windows(2).all(|pair| pair[0].id < pair[1].id) {
85            return Err(serde::de::Error::custom(
86                "measurement records must be strictly sorted by id",
87            ));
88        }
89        let next_id = match records.last() {
90            None => 0,
91            Some(record) => record
92                .id
93                .checked_add(1)
94                .ok_or_else(|| serde::de::Error::custom("measurement id space exhausted"))?,
95        };
96        Ok(Self { records, next_id })
97    }
98}
99
100impl MeasRegistry {
101    /// Creates an empty measurement registry.
102    pub fn new() -> Self {
103        Self::default()
104    }
105
106    /// Allocates one sequential id per qubit, appending a record for each, and
107    /// returns the ids in input order.
108    pub fn allocate(&mut self, qubits: impl IntoIterator<Item = IVec2>) -> Vec<u32> {
109        qubits
110            .into_iter()
111            .map(|qubit| self.allocate_one(qubit))
112            .collect()
113    }
114
115    /// Allocates a single sequential id for `qubit`, appending its record —
116    /// the [`Self::allocate`] core without the return `Vec`, for hot callers
117    /// that allocate one id at a time.
118    ///
119    /// # Panics
120    ///
121    /// Panics if the measurement-id space is exhausted.
122    pub fn allocate_one(&mut self, qubit: IVec2) -> u32 {
123        let id = self.next_id;
124        self.next_id = id_after(id);
125        self.records.push(MeasRecord { id, qubit });
126        id
127    }
128
129    /// Reserve `id` for `qubit`, keeping the record list sorted. Reserving an
130    /// already-reserved id for the same qubit is a no-op.
131    ///
132    /// # Panics
133    ///
134    /// Panics if `id` is already reserved for a different qubit or is `u32::MAX`.
135    /// The registry is unchanged if this check fails.
136    pub fn reserve(&mut self, id: u32, qubit: IVec2) {
137        // Callers reserve in ascending order, so check the tail before paying
138        // for a search.
139        let slot = match self.records.last() {
140            Some(record) if record.id < id => Err(self.records.len()),
141            _ => self.records.binary_search_by_key(&id, |record| record.id),
142        };
143        match slot {
144            Ok(index) => assert_eq!(
145                self.records[index].qubit, qubit,
146                "measurement id reserved for a different qubit"
147            ),
148            Err(index) => {
149                let next_id = id_after(id);
150                self.records.insert(index, MeasRecord { id, qubit });
151                self.next_id = self.next_id.max(next_id);
152            }
153        }
154    }
155
156    /// Reserve every record, sorting them by id first (see [`Self::reserve`]).
157    ///
158    /// # Panics
159    ///
160    /// Panics if any record's id is already reserved for a different qubit.
161    pub(crate) fn reserve_many(&mut self, records: &mut [MeasRecord]) {
162        records.sort_unstable_by_key(|record| record.id);
163        for record in records {
164            self.reserve(record.id, record.qubit);
165        }
166    }
167
168    /// Rewrites record ids through `remap`, then re-sorts and deduplicates so
169    /// the sorted-by-id invariant holds. Ids absent from `remap` are unchanged.
170    ///
171    /// # Panics
172    ///
173    /// Panics if a remapped record uses `u32::MAX`, leaving the registry unchanged.
174    pub(crate) fn remap_ids(&mut self, remap: &rustc_hash::FxHashMap<u32, u32>) {
175        if remap.is_empty() {
176            return;
177        }
178
179        let next_id = self
180            .records
181            .iter()
182            .map(|record| remap.get(&record.id).copied().unwrap_or(record.id))
183            .max()
184            .map_or(0, id_after);
185
186        for record in &mut self.records {
187            let id = remap.get(&record.id).copied().unwrap_or(record.id);
188            record.id = id;
189        }
190        self.records.sort_by_key(|record| record.id);
191        self.records.dedup_by_key(|record| record.id);
192        self.next_id = next_id;
193    }
194
195    /// Borrows the record for `id`, or `None` if it is not allocated.
196    pub fn record(&self, id: u32) -> Option<&MeasRecord> {
197        if let Some(record) = self.records.get(id as usize)
198            && record.id == id
199        {
200            return Some(record);
201        }
202        self.records
203            .binary_search_by_key(&id, |record| record.id)
204            .ok()
205            .map(|index| &self.records[index])
206    }
207
208    /// All records, sorted by id.
209    pub fn records(&self) -> &[MeasRecord] {
210        &self.records
211    }
212
213    /// The id the next [`Self::allocate`] call will hand out.
214    pub(crate) fn next_id(&self) -> u32 {
215        self.next_id
216    }
217}
218
219/// The successor of an allocated measurement id.
220fn id_after(id: u32) -> u32 {
221    id.checked_add(1)
222        .expect("id space is u32; programs stay far below 2^32 measurements")
223}
224
225/// Identifies a loop-carried detector state threaded across iterations of a
226/// repeated body.
227#[derive(
228    Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, serde::Serialize, serde::Deserialize,
229)]
230pub struct LoopStateId(pub u32);
231
232/// One term of a [`DetectorParity`]: either a measurement outcome or a
233/// loop-carried state.
234///
235/// Generic over the measurement type `M` so parities can be built over raw
236/// record ids or over already-resolved terms.
237#[derive(
238    Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, serde::Serialize, serde::Deserialize,
239)]
240pub enum DetectorTerm<M = u32> {
241    /// A measurement outcome.
242    Measurement(M),
243    /// A loop-carried detector state.
244    LoopState(LoopStateId),
245}
246
247type DetectorTerms<M> = SmallVec<[DetectorTerm<M>; 2]>;
248
249/// A mod-2 sum of [`DetectorTerm`]s and a constant sign bit — the parity a
250/// detector or observable checks.
251///
252/// Terms are held in a canonical form: sorted, with pairs that cancel removed,
253/// so equal parities compare and hash equally regardless of construction order.
254#[derive(Debug, Clone, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
255pub struct DetectorParity<M = u32> {
256    terms: DetectorTerms<M>,
257    sign: bool,
258}
259
260impl<M> Default for DetectorParity<M> {
261    fn default() -> Self {
262        Self {
263            terms: SmallVec::new(),
264            sign: false,
265        }
266    }
267}
268
269impl<M: Copy + Ord> DetectorParity<M> {
270    /// Builds a parity from measurement ids, canonicalizing the result.
271    pub fn from_measurements(measurements: impl IntoIterator<Item = M>) -> Self {
272        Self::from_terms(measurements.into_iter().map(DetectorTerm::Measurement))
273    }
274
275    /// Builds a parity from arbitrary terms, canonicalizing the result.
276    pub fn from_terms(terms: impl IntoIterator<Item = DetectorTerm<M>>) -> Self {
277        let mut parity = Self {
278            terms: terms.into_iter().collect(),
279            sign: false,
280        };
281        parity.canonicalize();
282        parity
283    }
284
285    /// Like [`Self::from_terms`], but takes the term buffer by value so
286    /// callers that already hold one (e.g. a completed flow's measurements)
287    /// avoid rebuilding it element by element.
288    pub fn from_term_buf(terms: SmallVec<[DetectorTerm<M>; 2]>) -> Self {
289        let mut parity = Self { terms, sign: false };
290        parity.canonicalize();
291        parity
292    }
293
294    /// Sets the constant XOR term. `true` represents a negative stabilizer
295    /// sign, so a noiseless detector with odd raw measurement parity evaluates
296    /// to zero.
297    #[must_use]
298    pub fn with_sign(mut self, sign: bool) -> Self {
299        self.sign = sign;
300        self
301    }
302
303    /// The constant XOR term (`true` for a negative stabilizer sign).
304    #[must_use]
305    pub fn sign(&self) -> bool {
306        self.sign
307    }
308
309    /// The canonicalized terms.
310    pub fn terms(&self) -> &[DetectorTerm<M>] {
311        &self.terms
312    }
313
314    /// Measurement terms only, dropping loop-carried detector state.
315    pub fn measurements(&self) -> impl Iterator<Item = M> + '_ {
316        self.terms.iter().filter_map(|term| match term {
317            DetectorTerm::Measurement(measurement) => Some(*measurement),
318            DetectorTerm::LoopState(_) => None,
319        })
320    }
321
322    /// Returns `true` for the zero parity: no terms and no constant sign.
323    pub fn is_empty(&self) -> bool {
324        self.terms.is_empty() && !self.sign
325    }
326
327    /// XORs `other`'s terms into `self` (mod-2 addition) and recanonicalizes.
328    pub fn xor_assign(&mut self, other: &Self) {
329        self.sign ^= other.sign;
330        self.terms.extend_from_slice(&other.terms);
331        self.canonicalize();
332    }
333
334    /// Maps measurement terms in the existing buffer and recanonicalizes it.
335    #[must_use]
336    pub fn map_measurements(mut self, mut f: impl FnMut(M) -> M) -> Self {
337        for term in &mut self.terms {
338            if let DetectorTerm::Measurement(measurement) = term {
339                *measurement = f(*measurement);
340            }
341        }
342        self.canonicalize();
343        self
344    }
345
346    /// Maps each measurement term through `f`, leaving loop-state terms intact,
347    /// and canonicalizes the result. Loop-state terms pass through unchanged.
348    ///
349    /// # Errors
350    ///
351    /// Returns the first error `f` produces.
352    pub fn try_map_measurements<N: Copy + Ord, E>(
353        &self,
354        mut f: impl FnMut(M) -> Result<N, E>,
355    ) -> Result<DetectorParity<N>, E> {
356        let mut terms = DetectorTerms::with_capacity(self.terms.len());
357        for &term in &self.terms {
358            terms.push(match term {
359                DetectorTerm::Measurement(measurement) => {
360                    DetectorTerm::Measurement(f(measurement)?)
361                }
362                DetectorTerm::LoopState(state) => DetectorTerm::LoopState(state),
363            });
364        }
365        Ok(DetectorParity::from_terms(terms).with_sign(self.sign))
366    }
367
368    fn canonicalize(&mut self) {
369        // The one- and two-term cases dominate (a detector compares two
370        // consecutive stabilizer rounds); resolve them without invoking the
371        // sort machinery.
372        match self.terms.as_mut_slice() {
373            [] | [_] => return,
374            [a, b] => {
375                match (*a).cmp(&*b) {
376                    Ordering::Equal => self.terms.clear(),
377                    Ordering::Greater => self.terms.swap(0, 1),
378                    Ordering::Less => {}
379                }
380                return;
381            }
382            _ => {}
383        }
384
385        self.terms.sort_unstable();
386        let mut write = 0;
387        let mut read = 0;
388        while read < self.terms.len() {
389            let term = self.terms[read];
390            let mut count = 1;
391            read += 1;
392            while read < self.terms.len() && self.terms[read] == term {
393                count += 1;
394                read += 1;
395            }
396            if count % 2 == 1 {
397                self.terms[write] = term;
398                write += 1;
399            }
400        }
401        self.terms.truncate(write);
402    }
403}
404
405impl<M: std::fmt::Display> std::fmt::Display for DetectorParity<M> {
406    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
407        if self.sign {
408            write!(f, "-")?;
409        }
410        if self.terms.is_empty() {
411            return write!(f, "0");
412        }
413        for (index, term) in self.terms.iter().enumerate() {
414            if index > 0 {
415                write!(f, "*")?;
416            }
417            match term {
418                DetectorTerm::Measurement(measurement) => write!(f, "{measurement}")?,
419                DetectorTerm::LoopState(state) => write!(f, "loop_state({})", state.0)?,
420            }
421        }
422        Ok(())
423    }
424}
425
426/// A detector state carried between iterations of a repeated body.
427///
428/// `initial` is the parity substituted for the state on the first iteration;
429/// `next` is the parity the state takes for the following iteration.
430#[derive(Debug, Clone, PartialEq, Eq)]
431pub struct LoopCarriedDetectorState<M = u32> {
432    /// The state this record defines.
433    pub state: LoopStateId,
434    /// Parity used for the state on the first iteration.
435    pub initial: DetectorParity<M>,
436    /// Parity the state carries into the next iteration.
437    pub next: DetectorParity<M>,
438}
439
440/// An ordered list of operations — the entry block of a circuit or the body of
441/// a [`Op::Repeat`].
442#[derive(Debug, Clone, Default, PartialEq, serde::Serialize, serde::Deserialize)]
443pub struct CircuitBody {
444    ops: Vec<Op>,
445}
446
447impl CircuitBody {
448    /// Creates an empty circuit body.
449    pub fn new() -> Self {
450        Self::default()
451    }
452
453    /// Creates a circuit body from an operation sequence.
454    pub fn from_ops(ops: Vec<Op>) -> Self {
455        Self { ops }
456    }
457
458    /// Borrows this body's operations.
459    pub fn ops(&self) -> &[Op] {
460        &self.ops
461    }
462
463    /// Mutably borrows this body's operations.
464    pub fn ops_mut(&mut self) -> &mut Vec<Op> {
465        &mut self.ops
466    }
467}
468
469/// Coordinates attached to a detector annotation, almost always an `(x, y)`
470/// pair; kept inline so the thousands of detector ops a compile produces do
471/// not heap-allocate their coordinates.
472pub type DetectorCoords = SmallVec<[f64; 2]>;
473
474/// Offsets a detector's first two coordinates by a layout offset, leaving any
475/// further coordinates untouched.
476#[must_use]
477pub fn translate_detector_coords(coords: &DetectorCoords, offset: IVec2) -> DetectorCoords {
478    let mut coords = coords.clone();
479    if let Some(x) = coords.get_mut(0) {
480        *x += offset.x as f64;
481    }
482    if let Some(y) = coords.get_mut(1) {
483        *y += offset.y as f64;
484    }
485    coords
486}
487
488/// A single coordinate-addressed circuit operation.
489#[derive(Debug, Clone, PartialEq, serde::Serialize, serde::Deserialize)]
490pub enum Op {
491    /// A gate applied to its target qubits (pairwise for two-qubit gates).
492    Gate {
493        /// Gate kind.
494        gate: GateType,
495        /// Target qubits.
496        qubits: Vec<IVec2>,
497    },
498    /// A single-qubit measurement of each qubit in `basis`; `measurements[i]`
499    /// is the record id produced for `qubits[i]`.
500    Measure {
501        /// Measured basis.
502        basis: PauliBasis,
503        /// Measured qubits.
504        qubits: Vec<IVec2>,
505        /// Measurement ids produced in qubit order.
506        measurements: Vec<u32>,
507        /// Probability of flipping each reported measurement result.
508        flip_probability: f64,
509    },
510    /// Multi-Pauli-product measurement (Stim `MPP`). Each entry of `products` is
511    /// one Pauli-product group (e.g. `X0*X1`) measured jointly; `products[i]`
512    /// produces record `measurements[i]`, and the data-qubit support is carried
513    /// here for emission. Temporal `Port` blocks use this to measure patch
514    /// stabilizers as an ideal noiseless open boundary.
515    MPP {
516        /// Joint Pauli products.
517        products: Vec<PauliMap>,
518        /// Measurement ids produced in product order.
519        measurements: Vec<u32>,
520    },
521    /// Independent single-qubit depolarizing channels on `qubits`.
522    Depolarize1 {
523        /// Error probability.
524        probability: f64,
525        /// Affected qubits.
526        qubits: Vec<IVec2>,
527    },
528    /// Independent two-qubit depolarizing channels on consecutive qubit pairs.
529    Depolarize2 {
530        /// Error probability.
531        probability: f64,
532        /// Affected consecutive qubit pairs.
533        qubits: Vec<IVec2>,
534    },
535    /// Independent Pauli errors on `qubits` (Stim `X_ERROR`/`Y_ERROR`/`Z_ERROR`).
536    PauliError {
537        /// Error probability.
538        probability: f64,
539        /// Applied Pauli.
540        pauli: PauliBasis,
541        /// Affected qubits.
542        qubits: Vec<IVec2>,
543    },
544    /// A moment barrier separating parallel operations.
545    Tick,
546    /// Executes `body` `repetitions` times (Stim `REPEAT`).
547    Repeat {
548        /// Repeated body.
549        body: BodyId,
550        /// Iteration count.
551        repetitions: u32,
552    },
553    /// Physically-applied Pauli feedforward: each correction applies its Pauli
554    /// to its target iff its control measurement is 1 (Stim `CZ rec[-k] q`).
555    ///
556    /// Support-transparent: the [`FlowEngine`](crate::FlowEngine) ignores it, so
557    /// flows/detectors derive from the Clifford+[`Measure`](Op::Measure)
558    /// structure alone. The *parity* effect of a
559    /// measurement-conditioned sign flip (a control entering a downstream
560    /// detector/observable parity) is the **backend/DEM generator's**
561    /// responsibility, not the IR's — the IR carries the op, not the analysis.
562    ConditionalPauli(Vec<ConditionalCorrection>),
563}
564
565#[cfg(test)]
566mod tests {
567    use super::*;
568    use glam::ivec2;
569
570    #[test]
571    fn registry_overflow_panics_leave_records_unchanged() {
572        for remap in [false, true] {
573            let mut registry = MeasRegistry::new();
574            registry.reserve(3, ivec2(0, 0));
575            let before = registry.clone();
576            let result = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
577                if remap {
578                    registry.remap_ids(&[(3, u32::MAX)].into_iter().collect());
579                } else {
580                    registry.reserve(u32::MAX, ivec2(1, 0));
581                }
582            }));
583            assert!(result.is_err(), "exhausted measurement ids must panic");
584            assert_eq!(
585                registry,
586                before,
587                "{} mutated the registry after overflow",
588                if remap { "remap_ids" } else { "reserve" },
589            );
590        }
591    }
592
593    #[test]
594    fn detector_parity_xors_signs_and_terms() {
595        let mut parity = DetectorParity::from_measurements([7]).with_sign(true);
596        parity.xor_assign(&DetectorParity::from_measurements([7]));
597
598        assert!(parity.terms().is_empty());
599        assert!(parity.sign());
600        assert!(
601            !parity.is_empty(),
602            "negative identity is not the zero parity"
603        );
604
605        parity.xor_assign(&DetectorParity::default().with_sign(true));
606        assert!(parity.is_empty());
607    }
608
609    #[test]
610    fn detector_parity_map_recanonicalizes_the_reused_buffer() {
611        let parity = DetectorParity::from_measurements([1, 2, 3])
612            .with_sign(true)
613            .map_measurements(|measurement| if measurement == 1 { 3 } else { measurement });
614
615        assert_eq!(parity.measurements().collect::<Vec<_>>(), vec![2]);
616        assert!(parity.sign());
617    }
618
619    /// The wire carries only records: `next_id` is recomputed on decode (a
620    /// trusted-from-the-wire value could make `allocate` reuse an id), and
621    /// unsorted records — which would break the binary searches — are
622    /// rejected.
623    #[test]
624    fn deserialize_recomputes_next_id_and_rejects_unsorted_records() {
625        let mut registry = MeasRegistry::new();
626        registry.reserve(3, ivec2(0, 0));
627        registry.reserve(7, ivec2(1, 0));
628        let bytes = postcard::to_allocvec(&registry).expect("registry encodes into a Vec");
629        let mut restored: MeasRegistry = postcard::from_bytes(&bytes).expect("registry decodes");
630        assert_eq!(restored, registry);
631        assert_eq!(restored.record(7).unwrap().qubit, ivec2(1, 0));
632        assert!(restored.record(1).is_none());
633        assert_eq!(restored.allocate([ivec2(2, 0)]), vec![8]);
634
635        let unsorted = vec![
636            MeasRecord {
637                id: 7,
638                qubit: ivec2(1, 0),
639            },
640            MeasRecord {
641                id: 3,
642                qubit: ivec2(0, 0),
643            },
644        ];
645        let bytes = postcard::to_allocvec(&unsorted).expect("test wire encodes into a Vec");
646        postcard::from_bytes::<MeasRegistry>(&bytes).unwrap_err();
647    }
648
649    #[test]
650    fn meas_registry_reserves_many_in_sorted_order() {
651        let mut registry = MeasRegistry::new();
652        let mut records = vec![
653            MeasRecord {
654                id: 2,
655                qubit: ivec2(2, 0),
656            },
657            MeasRecord {
658                id: 0,
659                qubit: ivec2(0, 0),
660            },
661            MeasRecord {
662                id: 1,
663                qubit: ivec2(1, 0),
664            },
665        ];
666
667        registry.reserve_many(&mut records);
668
669        assert_eq!(
670            registry.records(),
671            &[
672                MeasRecord {
673                    id: 0,
674                    qubit: ivec2(0, 0)
675                },
676                MeasRecord {
677                    id: 1,
678                    qubit: ivec2(1, 0)
679                },
680                MeasRecord {
681                    id: 2,
682                    qubit: ivec2(2, 0)
683                },
684            ]
685        );
686    }
687}
bloq_circuit/semantic.rs

bloq_circuit/
semantic.rs
