ppvm_pauli_word/pattern/
enumerate.rs

1// SPDX-FileCopyrightText: 2026 The PPVM Authors
2// SPDX-License-Identifier: Apache-2.0
3
4use super::data::{Decorated, OpPattern, PauliPattern};
5use crate::word::PauliWord;
6use ppvm_traits::char::Pauli;
7use ppvm_traits::traits::{PauliStorage, PauliWordTrait};
8
9use itertools::{Itertools, MultiProduct};
10
11impl OpPattern {
12    /// Iterate over every [`Pauli`] symbol matching this op pattern.
13    pub fn enumerate_matches(&self) -> EnumMatchesOpPattern<'_> {
14        EnumMatchesOpPattern {
15            pattern: self,
16            current: 0,
17        }
18    }
19}
20
21/// Iterator over the Pauli symbols accepted by an [`OpPattern`].
22#[derive(Debug, Clone)]
23pub struct EnumMatchesOpPattern<'a> {
24    pattern: &'a OpPattern,
25    current: usize,
26}
27
28impl<'a> Iterator for EnumMatchesOpPattern<'a> {
29    type Item = Pauli;
30
31    fn next(&mut self) -> Option<Self::Item> {
32        use OpPattern::*;
33        match self.pattern {
34            Identity if self.current == 0 => {
35                self.current += 1;
36                Some(Pauli::I)
37            }
38            Single(op) if self.current == 0 => {
39                self.current += 1;
40                Some((*op).into())
41            }
42            Double(left, right) if self.current < 2 => {
43                let result = if self.current == 0 {
44                    self.current += 1;
45                    (*left).into()
46                } else {
47                    self.current += 1;
48                    (*right).into()
49                };
50                Some(result)
51            }
52            AnyNonIdentity if self.current < 3 => {
53                self.current += 1;
54                Some(unsafe { std::mem::transmute::<u8, Pauli>(self.current as u8) })
55            }
56            SingleOrIdentity(op) if self.current < 2 => {
57                let result = if self.current == 0 {
58                    self.current += 1;
59                    (*op).into()
60                } else {
61                    self.current += 1;
62                    Pauli::I
63                };
64                Some(result)
65            }
66            DoubleOrIdentity(a, b) if self.current < 3 => {
67                let result = if self.current == 0 {
68                    self.current += 1;
69                    (*a).into()
70                } else if self.current == 1 {
71                    self.current += 1;
72                    (*b).into()
73                } else {
74                    self.current += 1;
75                    Pauli::I
76                };
77                Some(result)
78            }
79            AnyPauliOrIdentity => {
80                let result = unsafe { std::mem::transmute::<u8, Pauli>(self.current as u8) };
81                self.current += 1;
82                Some(result)
83            }
84            _ => None,
85        }
86    }
87}
88
89impl PauliPattern {
90    /// Iterate over every [`PauliWord`] over `n_qubits` qubits that
91    /// matches this pattern. Star patterns are not supported and will
92    /// panic.
93    pub fn enumerate_matches<A: PauliStorage>(
94        &self,
95        n_qubits: usize,
96    ) -> EnumMatchesPauliPattern<'_, A> {
97        let mut start: usize = 0;
98        let mut iters = Vec::new();
99        let patterns = self.0.iter().peekable();
100        for pat in patterns {
101            match pat {
102                Decorated::Position(op, pos) => {
103                    for _ in start..*pos {
104                        iters.push(OpPattern::Identity.enumerate_matches());
105                    }
106                    iters.push(op.enumerate_matches());
107                    start = *pos + 1;
108                }
109                Decorated::Repeat(op, count) => {
110                    for _ in 0..*count {
111                        iters.push(op.enumerate_matches());
112                    }
113                }
114                Decorated::Star(_) => panic!("Star patterns are not supported"),
115            }
116        }
117
118        // match iters.len() to n_qubits
119        for _ in iters.len()..n_qubits {
120            iters.push(OpPattern::Identity.enumerate_matches());
121        }
122
123        EnumMatchesPauliPattern {
124            n_qubits,
125            iter: iters.into_iter().multi_cartesian_product(),
126            _phantom: std::marker::PhantomData,
127        }
128    }
129}
130
131/// Iterator over the concrete [`PauliWord`]s accepted by a [`PauliPattern`].
132#[derive(Debug, Clone)]
133pub struct EnumMatchesPauliPattern<'a, A: PauliStorage> {
134    n_qubits: usize,
135    iter: MultiProduct<EnumMatchesOpPattern<'a>>,
136    _phantom: std::marker::PhantomData<A>,
137}
138
139impl<'a, A: PauliStorage> Iterator for EnumMatchesPauliPattern<'a, A> {
140    type Item = PauliWord<A>;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        if let Some(item) = self.iter.next() {
144            let mut result = PauliWord::new(self.n_qubits);
145            for (i, bit) in item.iter().enumerate() {
146                result.set(i, *bit);
147            }
148            return Some(result);
149        }
150        None
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    #[test]
159    fn test_pattern_enumeration() {
160        let pat: PauliPattern = "[XY]1Z3".into();
161        let items: Vec<_> = pat.enumerate_matches::<u64>(4).collect();
162        assert!(items.contains(&"IXIZ".into()));
163        assert!(items.contains(&"IYIZ".into()));
164
165        let pat: PauliPattern = "Z?{4}".into();
166        let items: Vec<_> = pat.enumerate_matches::<u64>(4).collect();
167        assert!(items.contains(&"ZZZZ".into()));
168        assert!(items.contains(&"ZZZI".into()));
169        assert!(items.contains(&"ZZIZ".into()));
170        assert!(items.contains(&"ZZII".into()));
171        assert!(items.contains(&"ZIZZ".into()));
172        assert!(items.contains(&"ZIZI".into()));
173        assert!(items.contains(&"ZIIZ".into()));
174        assert!(items.contains(&"ZIII".into()));
175        assert!(items.contains(&"IZZZ".into()));
176        assert!(items.contains(&"IZZI".into()));
177        assert!(items.contains(&"IZIZ".into()));
178        assert!(items.contains(&"IZII".into()));
179        assert!(items.contains(&"IIZZ".into()));
180        assert!(items.contains(&"IIZI".into()));
181        assert!(items.contains(&"IIIZ".into()));
182        assert!(items.contains(&"IIII".into()));
183    }
184}
ppvm_pauli_word/pattern/enumerate.rs

ppvm_pauli_word/pattern/
enumerate.rs
