use ::tk_pg_core::{Op, Pauli};
use std::collections::HashSet;
const ZX_LUT: [u64; 4] = [0b10, 0b11, 0b01, 0b00];
const XZ_LUT: [u64; 4] = [0b01, 0b11, 0b10, 0b00];
const LOW_BITS: u64 = 0x5555_5555_5555_5555;
const HIGH_BITS: u64 = 0xAAAA_AAAA_AAAA_AAAA;
enum PauliStringEncoding {
ZX,
XZ,
}
#[derive(Clone, Eq, PartialEq, Hash)]
pub(crate) struct XZPackedPaulis(Vec<u64>);
#[derive(Clone, Eq, PartialEq, Hash)]
pub(crate) struct ZXPackedPaulis(Vec<u64>);
impl From<&[Pauli]> for XZPackedPaulis {
fn from(paulis: &[Pauli]) -> Self {
Self(bitpack_paulis(paulis, PauliStringEncoding::XZ))
}
}
impl From<&[Pauli]> for ZXPackedPaulis {
fn from(paulis: &[Pauli]) -> Self {
Self(bitpack_paulis(paulis, PauliStringEncoding::ZX))
}
}
#[inline(always)]
fn swap_xz_bits(word: u64) -> u64 {
((word & LOW_BITS) << 1) | ((word & HIGH_BITS) >> 1)
}
impl From<XZPackedPaulis> for ZXPackedPaulis {
fn from(mut packed: XZPackedPaulis) -> Self {
for word in &mut packed.0 {
*word = swap_xz_bits(*word);
}
Self(packed.0)
}
}
fn bitpack_paulis(paulis: &[Pauli], encoding: PauliStringEncoding) -> Vec<u64> {
let lut = if let PauliStringEncoding::ZX = encoding {
&ZX_LUT
} else {
&XZ_LUT
};
let n_u64s = paulis.len().div_ceil(32);
let mut bits = Vec::with_capacity(n_u64s);
for chunk in paulis.chunks(32) {
let mut word: u64 = 0;
for (i, pauli) in chunk.iter().enumerate() {
word |= lut[*pauli as usize] << (i * 2);
}
bits.push(word);
}
bits
}
fn commute_bitpacked(zx_paulis: &ZXPackedPaulis, xz_paulis: &XZPackedPaulis) -> bool {
if zx_paulis.0.len() != xz_paulis.0.len() {
panic!("bitpacked Pauli strings must have the same length");
}
zx_paulis
.0
.iter()
.zip(xz_paulis.0.iter())
.map(|(&b0, &b1)| (b0 & b1).count_ones())
.sum::<u32>()
% 2
== 0
}
#[derive(Clone)]
pub(crate) struct BasePackedOp<P> {
pub op: Op,
strings: Option<Vec<P>>,
classical_access: Option<Box<ClassicalAccess>>,
}
pub(crate) type PendingPackedOp = BasePackedOp<XZPackedPaulis>;
pub(crate) type PackedOp = BasePackedOp<ZXPackedPaulis>;
#[derive(Clone, Default)]
struct ClassicalAccess {
read_bits: HashSet<usize>,
write_bits: HashSet<usize>,
}
fn classical_access(op: &Op) -> Option<ClassicalAccess> {
match op {
Op::Measure { data } => Some(ClassicalAccess {
write_bits: HashSet::from([data.get_cbit()]),
..Default::default()
}),
Op::ConditionalBox { data } => {
let mut access = ClassicalAccess {
read_bits: data.get_conditional_bits().iter().copied().collect(),
..Default::default()
};
for inner_access in data.get_ops().iter().filter_map(classical_access) {
access.read_bits.extend(inner_access.read_bits);
access.write_bits.extend(inner_access.write_bits);
}
Some(access)
}
_ => None,
}
}
fn classical_conflict(first: &ClassicalAccess, second: &ClassicalAccess) -> bool {
!first.read_bits.is_disjoint(&second.write_bits)
|| !first.write_bits.is_disjoint(&second.read_bits)
|| !first.write_bits.is_disjoint(&second.write_bits)
}
impl From<PendingPackedOp> for PackedOp {
fn from(pending_op: PendingPackedOp) -> Self {
Self {
op: pending_op.op,
strings: pending_op
.strings
.map(|s| s.into_iter().map(ZXPackedPaulis::from).collect()),
classical_access: pending_op.classical_access,
}
}
}
impl<P> BasePackedOp<P>
where
P: for<'a> From<&'a [Pauli]>,
{
pub fn new(op: Op) -> Self {
let classical_access = classical_access(&op).map(Box::new);
let strings = op
.get_paulis()
.map(|ps| ps.iter().map(|p| P::from(p)).collect());
Self {
op,
strings,
classical_access,
}
}
}
impl PackedOp {
pub fn commute_with(&self, other: &PendingPackedOp) -> bool {
if matches!(self.op, Op::SetBoundary) || matches!(other.op, Op::SetBoundary) {
return true;
}
if let (Some(self_access), Some(other_access)) =
(&self.classical_access, &other.classical_access)
&& classical_conflict(self_access, other_access)
{
return false;
}
match (&self.strings, &other.strings) {
(Some(p0), Some(p1)) => p0
.iter()
.all(|p0| p1.iter().all(|p1| commute_bitpacked(p0, p1))),
_ => false,
}
}
pub fn commute_with_string(&self, other: &XZPackedPaulis) -> bool {
if matches!(self.op, Op::SetBoundary) {
return true;
}
match &self.strings {
Some(strings) => strings.iter().all(|s| commute_bitpacked(s, other)),
None => false,
}
}
}
impl<P> From<BasePackedOp<P>> for Op {
fn from(packed_op: BasePackedOp<P>) -> Op {
packed_op.op
}
}
trait PauliOp {
fn get_paulis(&self) -> Option<Vec<&Vec<Pauli>>>;
}
impl PauliOp for Op {
fn get_paulis(&self) -> Option<Vec<&Vec<Pauli>>> {
match self {
Op::Rotation { data } => Some(vec![data.get_string()]),
Op::Measure { data } => Some(vec![data.get_string()]),
Op::Reset { data } => Some(vec![data.get_first_string(), data.get_second_string()]),
Op::ConditionalBox { data } => {
let mut paulis = Vec::new();
for op in data.get_ops() {
let op_paulis = op.get_paulis()?;
paulis.extend(op_paulis);
}
Some(paulis)
}
_ => None,
}
}
}
#[cfg(test)]
mod tests {
use tk_pg_core::{MeasureData, ResetData, RotationData};
use super::*;
#[test]
fn test_commute_bitpacked() {
let p0 = vec![Pauli::X, Pauli::I, Pauli::Z];
let p1 = vec![Pauli::Z, Pauli::Z, Pauli::Y];
let p2 = vec![Pauli::X, Pauli::Z, Pauli::I];
let p3 = vec![Pauli::Y, Pauli::I, Pauli::Z];
let p4 = vec![Pauli::I, Pauli::I, Pauli::I];
assert!(commute_bitpacked(
&p0.as_slice().into(),
&p1.as_slice().into()
));
assert!(commute_bitpacked(
&p0.as_slice().into(),
&p2.as_slice().into()
));
assert!(!commute_bitpacked(
&p0.as_slice().into(),
&p3.as_slice().into()
));
assert!(commute_bitpacked(
&p0.as_slice().into(),
&p0.as_slice().into()
));
assert!(commute_bitpacked(
&p1.as_slice().into(),
&p3.as_slice().into()
));
assert!(!commute_bitpacked(
&p2.as_slice().into(),
&p3.as_slice().into()
));
assert!(!commute_bitpacked(
&p1.as_slice().into(),
&p2.as_slice().into()
));
assert!(commute_bitpacked(
&p3.as_slice().into(),
&p3.as_slice().into()
));
assert!(commute_bitpacked(
&p3.as_slice().into(),
&p4.as_slice().into()
));
assert!(commute_bitpacked(
&p4.as_slice().into(),
&p4.as_slice().into()
));
}
#[test]
#[should_panic(expected = "bitpacked Pauli strings must have the same length")]
fn test_commute_bitpacked_rejects_unequal_lengths() {
commute_bitpacked(&ZXPackedPaulis(vec![0]), &XZPackedPaulis(vec![]));
}
#[test]
fn test_xz_to_zx_conversion_matches_direct_packing() {
let paulis = (0..65)
.map(|i| match i % 4 {
0 => Pauli::I,
1 => Pauli::X,
2 => Pauli::Y,
_ => Pauli::Z,
})
.collect::<Vec<_>>();
let converted = ZXPackedPaulis::from(XZPackedPaulis::from(paulis.as_slice()));
let directly_packed = ZXPackedPaulis::from(paulis.as_slice());
assert_eq!(converted.0, directly_packed.0);
}
#[test]
fn test_op_commute() {
let op0 = Op::Rotation {
data: RotationData::new(vec![Pauli::X, Pauli::I], 0.1),
};
let op1 = Op::Rotation {
data: RotationData::new(vec![Pauli::X, Pauli::X], 0.1),
};
let op2 = Op::Rotation {
data: RotationData::new(vec![Pauli::Z, Pauli::I], 0.1),
};
let op3 = Op::Rotation {
data: RotationData::new(vec![Pauli::Z, Pauli::X], 0.2),
};
let op4 = Op::Measure {
data: MeasureData::new(vec![Pauli::Z, Pauli::X], true, 0),
};
let op5 = Op::Reset {
data: ResetData::new(
vec![Pauli::I, Pauli::Z],
vec![Pauli::I, Pauli::X],
true,
true,
),
};
let op6 = Op::Reset {
data: ResetData::new(
vec![Pauli::Z, Pauli::I],
vec![Pauli::X, Pauli::I],
true,
true,
),
};
assert!(PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op1.clone())));
assert!(!PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op2.clone())));
assert!(!PackedOp::new(op1.clone()).commute_with(&PendingPackedOp::new(op3.clone())));
assert!(PackedOp::new(op3.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
assert!(PackedOp::new(op0.clone()).commute_with(&PendingPackedOp::new(op5.clone())));
assert!(PackedOp::new(op2.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
assert!(!PackedOp::new(op6.clone()).commute_with(&PendingPackedOp::new(op4.clone())));
}
}