1use ::tk_pg_core::{Op, Pauli};
2use std::collections::HashSet;
3const ZX_LUT: [u64; 4] = [0b10, 0b11, 0b01, 0b00];
6const 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
12enum 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
54fn 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
73fn 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#[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#[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
130fn 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 if matches!(self.op, Op::SetBoundary) || matches!(other.op, Op::SetBoundary) {
171 return true;
172 }
173 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 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}