tk_pg_bitpacked/lib.rs
1//! This crate implements Clifford conjugation on bit-packed representations of Pauli operators.
2//! The unstable_simd feature enables the use of the nightly portable_simd API.
3
4#![cfg_attr(feature = "unstable_simd", feature(portable_simd))]
5#![cfg_attr(
6 feature = "unstable_simd",
7 expect(clippy::too_many_arguments, clippy::type_complexity)
8)]
9
10use tk_pg_core::Pauli;
11
12mod kernels;
13mod slice;
14mod u8_encodings;
15
16pub use kernels::*;
17pub use slice::*;
18pub use u8_encodings::*;
19
20#[cfg(feature = "unstable_simd")]
21mod simd;
22#[cfg(feature = "unstable_simd")]
23pub use simd::*;
24
25#[cfg(test)]
26mod test_utils;
27
28/// Converts a slice of boolean values into a vector of `u64` values, where each `u64`
29/// represents up to 64 boolean values packed as bits.
30///
31/// Booleans are packed **little-endian** within each `u64`.
32///
33/// # Arguments
34///
35/// - `bits` (`&[bool]`) - A slice of boolean values to be converted.
36///
37/// # Returns
38///
39/// - `Vec<u64>` - A vector of `u64` values representing the packed boolean values.
40///
41/// # Example
42///
43/// ```
44/// use tk_pg_bitpacked::bools_to_u64_vec;
45/// // indices 0 and 2 are true → bits 0 and 2 set → 0b0101 = 5
46/// let bits = vec![true, false, true, false];
47/// let packed = bools_to_u64_vec(&bits);
48/// assert_eq!(packed, vec![0b0101_u64]);
49/// ```
50pub fn bools_to_u64_vec(bits: &[bool]) -> Vec<u64> {
51 bits.chunks(64)
52 .map(|chunk| {
53 chunk
54 .iter()
55 .enumerate()
56 .fold(0u64, |acc, (i, &b)| if b { acc | (1 << i) } else { acc })
57 })
58 .collect()
59}
60
61/// Converts a vector of `Pauli` values into two vectors of `u64` bit-packed representations.
62///
63/// Each Pauli is encoded into two bits:
64/// - Z component: 0 for `I`/`X`, 1 for `Z`/`Y`
65/// - X component: 0 for `I`/`Z`, 1 for `X`/`Y`
66///
67/// Paulis are packed **little-endian** within each `u64`.
68///
69/// # Arguments
70///
71/// * `paulis` - A slice of `Pauli` values to be encoded.
72///
73/// # Returns
74///
75/// A tuple `(zs, xs)` where:
76/// - `zs`: Z component bits packed into `u64` values.
77/// - `xs`: X component bits packed into `u64` values.
78///
79/// # Example
80///
81/// ```
82/// use tk_pg_core::Pauli;
83/// use tk_pg_bitpacked::paulis_to_u64s;
84/// // [I, X, Y, Z] → Z bits: [0,0,1,1] = 0b1100 = 12
85/// // → X bits: [0,1,1,0] = 0b0110 = 6
86/// let paulis = vec![Pauli::I, Pauli::X, Pauli::Y, Pauli::Z];
87/// let (zs, xs) = paulis_to_u64s(&paulis);
88/// assert_eq!(zs, vec![0b1100_u64]);
89/// assert_eq!(xs, vec![0b0110_u64]);
90/// ```
91pub fn paulis_to_u64s(paulis: &[Pauli]) -> (Vec<u64>, Vec<u64>) {
92 let n_u64s = paulis.len().div_ceil(64);
93 let mut zs = Vec::with_capacity(n_u64s);
94 let mut xs = Vec::with_capacity(n_u64s);
95 let mut z_current: u64 = 0;
96 let mut x_current: u64 = 0;
97 let mut bits_filled = 0;
98 for pauli in paulis {
99 let z_bit = match pauli {
100 Pauli::I => 0,
101 Pauli::X => 0,
102 Pauli::Z => 1,
103 Pauli::Y => 1,
104 };
105 let x_bit = match pauli {
106 Pauli::I => 0,
107 Pauli::X => 1,
108 Pauli::Z => 0,
109 Pauli::Y => 1,
110 };
111 z_current |= (z_bit as u64) << bits_filled;
112 x_current |= (x_bit as u64) << bits_filled;
113 bits_filled += 1;
114 if bits_filled == 64 {
115 zs.push(z_current);
116 xs.push(x_current);
117 z_current = 0;
118 x_current = 0;
119 bits_filled = 0;
120 }
121 }
122 if bits_filled > 0 {
123 zs.push(z_current);
124 xs.push(x_current);
125 }
126 (zs, xs)
127}
128
129/// Converts two vectors of `u64` bit-packed representations back into a vector of `Pauli` values.
130///
131/// This function is the inverse of `paulis_to_u64s`. It decodes the Z and X component bits
132/// from the packed `u64` values to reconstruct the original Pauli operators.
133///
134/// # Arguments
135///
136/// * `packed_z_bits` - A reference to a vector of `u64` values containing the Z component bits.
137/// * `packed_x_bits` - A reference to a vector of `u64` values containing the X component bits.
138/// * `n_paulis` - The exact number of Pauli operators to decode (prevents decoding padding bits).
139///
140/// # Returns
141///
142/// A `Vec<Pauli>` containing the decoded Pauli operators.
143///
144/// # Example
145///
146/// ```
147/// use tk_pg_core::Pauli;
148/// use tk_pg_bitpacked::u64s_to_paulis;
149/// let zs = vec![0b1100_u64]; // Z bits for [I, X, Y, Z]
150/// let xs = vec![0b0110_u64]; // X bits for [I, X, Y, Z]
151/// let paulis = vec![Pauli::I, Pauli::X, Pauli::Y, Pauli::Z];
152/// let decoded = u64s_to_paulis(&zs, &xs, paulis.len());
153/// assert_eq!(paulis, decoded);
154/// ```
155pub fn u64s_to_paulis(packed_z_bits: &[u64], packed_x_bits: &[u64], n_paulis: usize) -> Vec<Pauli> {
156 let mut paulis = Vec::with_capacity(n_paulis);
157 let mut decoded = 0;
158 for (z_pack, x_pack) in packed_z_bits.iter().zip(packed_x_bits) {
159 for i in 0..64 {
160 if decoded == n_paulis {
161 return paulis;
162 }
163 let z_bit = (z_pack >> i) & 0b1;
164 let x_bit = (x_pack >> i) & 0b1;
165 let pauli = match (z_bit, x_bit) {
166 (0, 0) => Pauli::I,
167 (0, 1) => Pauli::X,
168 (1, 0) => Pauli::Z,
169 (1, 1) => Pauli::Y,
170 _ => unreachable!(),
171 };
172 paulis.push(pauli);
173 decoded += 1;
174 }
175 }
176 paulis
177}
178
179/// Converts a vector of boolean sign flip values into a bit-packed `u64` representation.
180///
181/// Each boolean is encoded as a single bit (`true` → 1, `false` → 0), packed
182/// **little-endian** within each `u64`.
183///
184/// # Arguments
185///
186/// * `sign_flips` - A slice of `bool` values to be bit-packed.
187///
188/// # Returns
189///
190/// A `Vec<u64>` containing the bit-packed representation of the boolean values.
191///
192/// # Example
193///
194/// ```
195/// use tk_pg_bitpacked::sign_flips_to_u64s;
196/// // indices 0 and 2 are true → bits 0 and 2 set → 0b0101 = 5
197/// let signs = vec![true, false, true, false];
198/// let packed = sign_flips_to_u64s(&signs);
199/// assert_eq!(packed, vec![0b0101_u64]);
200/// ```
201pub fn sign_flips_to_u64s(sign_flips: &[bool]) -> Vec<u64> {
202 let n_u64s = sign_flips.len().div_ceil(64);
203 let mut encodings = Vec::with_capacity(n_u64s);
204 let mut current: u64 = 0;
205 let mut bits_filled = 0;
206 for &sign in sign_flips {
207 if sign {
208 current |= 1 << bits_filled;
209 }
210 bits_filled += 1;
211 if bits_filled == 64 {
212 encodings.push(current);
213 current = 0;
214 bits_filled = 0;
215 }
216 }
217 if bits_filled > 0 {
218 encodings.push(current);
219 }
220 encodings
221}
222
223/// Converts a vector of `u64` bit-packed representations back into a vector of boolean sign flip values.
224///
225/// This function is the inverse of `sign_flips_to_u64s`. It decodes the packed bits from the `u64`
226/// values to reconstruct the original boolean values.
227///
228/// # Arguments
229///
230/// * `packed_sign_flip_bits` - A slice of `u64` values containing the bit-packed sign flips.
231/// * `n_signs` - The exact number of boolean values to decode (prevents decoding padding bits).
232///
233/// # Returns
234///
235/// A `Vec<bool>` containing the decoded boolean sign flip values.
236///
237/// # Example
238///
239/// ```
240/// use tk_pg_bitpacked::u64s_to_sign_flips;
241/// let packed = vec![0b0101_u64]; // bits for [true, false, true, false]
242/// let decoded = u64s_to_sign_flips(&packed, 4);
243/// assert_eq!(decoded, vec![true, false, true, false]);
244/// ```
245pub fn u64s_to_sign_flips(packed_sign_flip_bits: &[u64], n_signs: usize) -> Vec<bool> {
246 let mut signs = Vec::with_capacity(n_signs);
247 let mut decoded = 0;
248 for encoding in packed_sign_flip_bits {
249 for i in 0..64 {
250 if decoded == n_signs {
251 return signs;
252 }
253 let bits = (encoding >> i) & 0b1;
254 signs.push(bits == 1);
255 decoded += 1;
256 }
257 }
258 signs
259}
260
261#[cfg(test)]
262mod tests {
263 use super::*;
264
265 #[test]
266 fn test_bools_to_u64_vec() {
267 // indices 0 and 2 set → bits 0 and 2 → 0b0101 = 5
268 let bits = vec![true, false, true, false];
269 assert_eq!(bools_to_u64_vec(&bits), vec![0b0101_u64]);
270
271 // empty input
272 assert_eq!(bools_to_u64_vec(&[]), Vec::<u64>::new());
273
274 // 65 booleans span two u64s; index 64 maps to bit 0 of the second u64
275 let mut long_bits = vec![false; 65];
276 long_bits[64] = true;
277 assert_eq!(bools_to_u64_vec(&long_bits), vec![0_u64, 1_u64]);
278
279 // 128 booleans across two full u64s: every even index is true
280 // each u64 gets alternating bits set: 0b010101...01 = 0x5555_5555_5555_5555
281 let bits_128: Vec<bool> = (0..128).map(|i| i % 2 == 0).collect();
282 let packed = bools_to_u64_vec(&bits_128);
283 assert_eq!(packed.len(), 2);
284 assert_eq!(packed[0], 0x5555_5555_5555_5555_u64);
285 assert_eq!(packed[1], 0x5555_5555_5555_5555_u64);
286 }
287
288 #[test]
289 fn test_paulis_to_u64s() {
290 // [I, X, Y, Z] → Z bits [0,0,1,1] = 0b1100 = 12, X bits [0,1,1,0] = 0b0110 = 6
291 let paulis = vec![Pauli::I, Pauli::X, Pauli::Y, Pauli::Z];
292 let (zs, xs) = paulis_to_u64s(&paulis);
293 assert_eq!(zs, vec![0b1100_u64]);
294 assert_eq!(xs, vec![0b0110_u64]);
295
296 // empty input
297 let (zs, xs) = paulis_to_u64s(&[]);
298 assert!(zs.is_empty());
299 assert!(xs.is_empty());
300 }
301
302 #[test]
303 fn test_paulis_to_u64s_long() {
304 // 65 Paulis: first 64 are I, last one is X
305 // → first u64: zs=0, xs=0; second u64: zs=0, xs=1 (bit 0 of second word)
306 let mut paulis = vec![Pauli::I; 65];
307 paulis[64] = Pauli::X;
308 let (zs, xs) = paulis_to_u64s(&paulis);
309 assert_eq!(zs, vec![0_u64, 0_u64]);
310 assert_eq!(xs, vec![0_u64, 1_u64]);
311
312 // 128 Paulis: roundtrip
313 let paulis: Vec<Pauli> = (0..128)
314 .map(|i| match i % 4 {
315 0 => Pauli::I,
316 1 => Pauli::X,
317 2 => Pauli::Y,
318 _ => Pauli::Z,
319 })
320 .collect();
321 let (zs, xs) = paulis_to_u64s(&paulis);
322 assert_eq!(zs.len(), 2);
323 assert_eq!(xs.len(), 2);
324 assert_eq!(u64s_to_paulis(&zs, &xs, paulis.len()), paulis);
325 }
326
327 #[test]
328 fn test_u64s_to_paulis() {
329 // roundtrip
330 let paulis = vec![Pauli::I, Pauli::X, Pauli::Y, Pauli::Z];
331 let (zs, xs) = paulis_to_u64s(&paulis);
332 assert_eq!(u64s_to_paulis(&zs, &xs, paulis.len()), paulis);
333
334 // n_paulis truncates padding bits
335 let (zs, xs) = paulis_to_u64s(&[Pauli::X, Pauli::Z]);
336 assert_eq!(u64s_to_paulis(&zs, &xs, 2), vec![Pauli::X, Pauli::Z]);
337 }
338
339 #[test]
340 fn test_sign_flips_to_u64s() {
341 // indices 0 and 2 true → bits 0 and 2 → 0b0101 = 5
342 let signs = vec![true, false, true, false];
343 assert_eq!(sign_flips_to_u64s(&signs), vec![0b0101_u64]);
344
345 // empty input
346 assert_eq!(sign_flips_to_u64s(&[]), Vec::<u64>::new());
347 }
348
349 #[test]
350 fn test_sign_flips_to_u64s_long() {
351 // 65 booleans: first 64 false, last true
352 // → first u64 = 0, second u64 = 1
353 let mut signs = vec![false; 65];
354 signs[64] = true;
355 assert_eq!(sign_flips_to_u64s(&signs), vec![0_u64, 1_u64]);
356
357 // 128 booleans: roundtrip
358 let signs: Vec<bool> = (0..128).map(|i| i % 3 == 0).collect();
359 let packed = sign_flips_to_u64s(&signs);
360 assert_eq!(packed.len(), 2);
361 assert_eq!(u64s_to_sign_flips(&packed, signs.len()), signs);
362 }
363
364 #[test]
365 fn test_u64s_to_sign_flips() {
366 // roundtrip
367 let signs = vec![true, false, true, false];
368 let packed = sign_flips_to_u64s(&signs);
369 assert_eq!(u64s_to_sign_flips(&packed, signs.len()), signs);
370
371 // n_signs truncates padding bits
372 let packed = sign_flips_to_u64s(&[true, true, false]);
373 assert_eq!(u64s_to_sign_flips(&packed, 3), vec![true, true, false]);
374 }
375}