Skip to main content

tk_pg_optimize/
packed_op.rs

1use ::tk_pg_core::{Op, Pauli};
2use std::collections::HashSet;
3// Lookup arrays for two different Pauli encodings: [X, Y, Z, I].
4// ZX_LUT: low bit = Z, high bit = X.
5const ZX_LUT: [u64; 4] = [0b10, 0b11, 0b01, 0b00];
6// XZ_LUT: low bit = X, high bit = Z.
7const XZ_LUT: [u64; 4] = [0b01, 0b11, 0b10, 0b00];
8
9const LOW_BITS: u64 = 0x5555_5555_5555_5555;
10const HIGH_BITS: u64 = 0xAAAA_AAAA_AAAA_AAAA;
11
12/// Encoding used for packed Pauli strings.
13///
14/// Each Pauli occupies two consecutive bits for its X and Z components. From
15/// low to high, `ZX` stores Z then X, while `XZ` stores X then Z. The first
16/// Pauli occupies the least significant pair.
17enum PauliStringEncoding {
18    ZX,
19    XZ,
20}
21
22#[derive(Clone, Eq, PartialEq, Hash)]
23pub(crate) struct XZPackedPaulis(Vec<u64>);
24
25#[derive(Clone, Eq, PartialEq, Hash)]
26pub(crate) struct ZXPackedPaulis(Vec<u64>);
27
28impl From<&[Pauli]> for XZPackedPaulis {
29    fn from(paulis: &[Pauli]) -> Self {
30        Self(bitpack_paulis(paulis, PauliStringEncoding::XZ))
31    }
32}
33
34impl From<&[Pauli]> for ZXPackedPaulis {
35    fn from(paulis: &[Pauli]) -> Self {
36        Self(bitpack_paulis(paulis, PauliStringEncoding::ZX))
37    }
38}
39
40#[inline(always)]
41fn swap_xz_bits(word: u64) -> u64 {
42    ((word & LOW_BITS) << 1) | ((word & HIGH_BITS) >> 1)
43}
44
45impl From<XZPackedPaulis> for ZXPackedPaulis {
46    fn from(mut packed: XZPackedPaulis) -> Self {
47        for word in &mut packed.0 {
48            *word = swap_xz_bits(*word);
49        }
50        Self(packed.0)
51    }
52}
53
54/// Packs a Pauli string into two bits per Pauli.
55fn bitpack_paulis(paulis: &[Pauli], encoding: PauliStringEncoding) -> Vec<u64> {
56    let lut = if let PauliStringEncoding::ZX = encoding {
57        &ZX_LUT
58    } else {
59        &XZ_LUT
60    };
61    let n_u64s = paulis.len().div_ceil(32);
62    let mut bits = Vec::with_capacity(n_u64s);
63    for chunk in paulis.chunks(32) {
64        let mut word: u64 = 0;
65        for (i, pauli) in chunk.iter().enumerate() {
66            word |= lut[*pauli as usize] << (i * 2);
67        }
68        bits.push(word);
69    }
70    bits
71}
72
73/// Checks whether two bit-packed Pauli strings commute.
74///
75fn commute_bitpacked(zx_paulis: &ZXPackedPaulis, xz_paulis: &XZPackedPaulis) -> bool {
76    if zx_paulis.0.len() != xz_paulis.0.len() {
77        panic!("bitpacked Pauli strings must have the same length");
78    }
79    zx_paulis
80        .0
81        .iter()
82        .zip(xz_paulis.0.iter())
83        .map(|(&b0, &b1)| (b0 & b1).count_ones())
84        .sum::<u32>()
85        % 2
86        == 0
87}
88
89/// Wraps an [`Op`] together with its bit-packed Pauli strings for commutation checks.
90///
91/// `P` determines the XZ or ZX encoding at compile time.
92#[derive(Clone)]
93pub(crate) struct BasePackedOp<P> {
94    pub op: Op,
95    strings: Option<Vec<P>>,
96    classical_access: Option<Box<ClassicalAccess>>,
97}
98
99pub(crate) type PendingPackedOp = BasePackedOp<XZPackedPaulis>;
100pub(crate) type PackedOp = BasePackedOp<ZXPackedPaulis>;
101
102/// Classical bits read and written by an operation and its nested operations.
103#[derive(Clone, Default)]
104struct ClassicalAccess {
105    read_bits: HashSet<usize>,
106    write_bits: HashSet<usize>,
107}
108
109fn classical_access(op: &Op) -> Option<ClassicalAccess> {
110    match op {
111        Op::Measure { data } => Some(ClassicalAccess {
112            write_bits: HashSet::from([data.get_cbit()]),
113            ..Default::default()
114        }),
115        Op::ConditionalBox { data } => {
116            let mut access = ClassicalAccess {
117                read_bits: data.get_conditional_bits().iter().copied().collect(),
118                ..Default::default()
119            };
120            for inner_access in data.get_ops().iter().filter_map(classical_access) {
121                access.read_bits.extend(inner_access.read_bits);
122                access.write_bits.extend(inner_access.write_bits);
123            }
124            Some(access)
125        }
126        _ => None,
127    }
128}
129
130/// Returns whether reordering two operations is invalid due to a classical conflict.
131/// Two reads are safe, but any shared bit involving a write is a conflict.
132fn classical_conflict(first: &ClassicalAccess, second: &ClassicalAccess) -> bool {
133    !first.read_bits.is_disjoint(&second.write_bits)
134        || !first.write_bits.is_disjoint(&second.read_bits)
135        || !first.write_bits.is_disjoint(&second.write_bits)
136}
137
138impl From<PendingPackedOp> for PackedOp {
139    fn from(pending_op: PendingPackedOp) -> Self {
140        Self {
141            op: pending_op.op,
142            strings: pending_op
143                .strings
144                .map(|s| s.into_iter().map(ZXPackedPaulis::from).collect()),
145            classical_access: pending_op.classical_access,
146        }
147    }
148}
149
150impl<P> BasePackedOp<P>
151where
152    P: for<'a> From<&'a [Pauli]>,
153{
154    pub fn new(op: Op) -> Self {
155        let classical_access = classical_access(&op).map(Box::new);
156        let strings = op
157            .get_paulis()
158            .map(|ps| ps.iter().map(|p| P::from(p)).collect());
159        Self {
160            op,
161            strings,
162            classical_access,
163        }
164    }
165}
166
167impl PackedOp {
168    pub fn commute_with(&self, other: &PendingPackedOp) -> bool {
169        // Set boundaries commute with every operation.
170        if matches!(self.op, Op::SetBoundary) || matches!(other.op, Op::SetBoundary) {
171            return true;
172        }
173        // Operations cannot be reordered across a classical write dependency.
174        if let (Some(self_access), Some(other_access)) =
175            (&self.classical_access, &other.classical_access)
176            && classical_conflict(self_access, other_access)
177        {
178            return false;
179        }
180        match (&self.strings, &other.strings) {
181            (Some(p0), Some(p1)) => p0
182                .iter()
183                .all(|p0| p1.iter().all(|p1| commute_bitpacked(p0, p1))),
184            _ => false,
185        }
186    }
187    pub fn commute_with_string(&self, other: &XZPackedPaulis) -> bool {
188        if matches!(self.op, Op::SetBoundary) {
189            return true;
190        }
191        match &self.strings {
192            Some(strings) => strings.iter().all(|s| commute_bitpacked(s, other)),
193            None => false,
194        }
195    }
196}
197
198impl<P> From<BasePackedOp<P>> for Op {
199    fn from(packed_op: BasePackedOp<P>) -> Op {
200        packed_op.op
201    }
202}
203
204trait PauliOp {
205    fn get_paulis(&self) -> Option<Vec<&Vec<Pauli>>>;
206}
207impl PauliOp for Op {
208    fn get_paulis(&self) -> Option<Vec<&Vec<Pauli>>> {
209        match self {
210            Op::Rotation { data } => Some(vec![data.get_string()]),
211            Op::Measure { data } => Some(vec![data.get_string()]),
212            Op::Reset { data } => Some(vec![data.get_first_string(), data.get_second_string()]),
213            // A conditional box should contain only the Op above, so
214            // recursively collect their Pauli strings.
215            Op::ConditionalBox { data } => {
216                let mut paulis = Vec::new();
217                for op in data.get_ops() {
218                    let op_paulis = op.get_paulis()?;
219                    paulis.extend(op_paulis);
220                }
221                Some(paulis)
222            }
223            _ => None,
224        }
225    }
226}
227
228#[cfg(test)]
229mod tests {
230    use tk_pg_core::{MeasureData, ResetData, RotationData};
231
232    use super::*;
233
234    #[test]
235    fn test_commute_bitpacked() {
236        let p0 = vec![Pauli::X, Pauli::I, Pauli::Z];
237        let p1 = vec![Pauli::Z, Pauli::Z, Pauli::Y];
238        let p2 = vec![Pauli::X, Pauli::Z, Pauli::I];
239        let p3 = vec![Pauli::Y, Pauli::I, Pauli::Z];
240        let p4 = vec![Pauli::I, Pauli::I, Pauli::I];
241        assert!(commute_bitpacked(
242            &p0.as_slice().into(),
243            &p1.as_slice().into()
244        ));
245        assert!(commute_bitpacked(
246            &p0.as_slice().into(),
247            &p2.as_slice().into()
248        ));
249        assert!(!commute_bitpacked(
250            &p0.as_slice().into(),
251            &p3.as_slice().into()
252        ));
253        assert!(commute_bitpacked(
254            &p0.as_slice().into(),
255            &p0.as_slice().into()
256        ));
257        assert!(commute_bitpacked(
258            &p1.as_slice().into(),
259            &p3.as_slice().into()
260        ));
261        assert!(!commute_bitpacked(
262            &p2.as_slice().into(),
263            &p3.as_slice().into()
264        ));
265        assert!(!commute_bitpacked(
266            &p1.as_slice().into(),
267            &p2.as_slice().into()
268        ));
269        assert!(commute_bitpacked(
270            &p3.as_slice().into(),
271            &p3.as_slice().into()
272        ));
273        assert!(commute_bitpacked(
274            &p3.as_slice().into(),
275            &p4.as_slice().into()
276        ));
277        assert!(commute_bitpacked(
278            &p4.as_slice().into(),
279            &p4.as_slice().into()
280        ));
281    }
282
283    #[test]
284    #[should_panic(expected = "bitpacked Pauli strings must have the same length")]
285    fn test_commute_bitpacked_rejects_unequal_lengths() {
286        commute_bitpacked(&ZXPackedPaulis(vec![0]), &XZPackedPaulis(vec![]));
287    }
288
289    #[test]
290    fn test_xz_to_zx_conversion_matches_direct_packing() {
291        let paulis = (0..65)
292            .map(|i| match i % 4 {
293                0 => Pauli::I,
294                1 => Pauli::X,
295                2 => Pauli::Y,
296                _ => Pauli::Z,
297            })
298            .collect::<Vec<_>>();
299
300        let converted = ZXPackedPaulis::from(XZPackedPaulis::from(paulis.as_slice()));
301        let directly_packed = ZXPackedPaulis::from(paulis.as_slice());
302
303        assert_eq!(converted.0, directly_packed.0);
304    }
305
306    #[test]
307    fn test_op_commute() {
308        let op0 = Op::Rotation {
309            data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
310        };
311        let op1 = Op::Rotation {
312            data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
313        };
314        let op2 = Op::Rotation {
315            data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
316        };
317        let op3 = Op::Rotation {
318            data: RotationData::new(vec![Pauli::Z, Pauli::X], 0.2),
319        };
320        let op4 = Op::Measure {
321            data: MeasureData::new(vec![Pauli::Z, Pauli::X], true, 0),
322        };
323        let op5 = Op::Reset {
324            data: ResetData::new(
325                vec![Pauli::I, Pauli::Z],
326                vec![Pauli::I, Pauli::X],
327                true,
328                true,
329            ),
330        };
331        let op6 = Op::Reset {
332            data: ResetData::new(
333                vec![Pauli::Z, Pauli::I],
334                vec![Pauli::X, Pauli::I],
335                true,
336                true,
337            ),
338        };
339
340        assert!(PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op1.clone())));
341        assert!(!PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op2.clone())));
342        assert!(!PackedOp::new(op1.clone()).commute_with(&PendingPackedOp::new(op3.clone())));
343        assert!(PackedOp::new(op3.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
344        assert!(PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op5.clone())));
345        assert!(PackedOp::new(op2.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
346        assert!(!PackedOp::new(op6.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
347    }
348}