Skip to main content

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}