Skip to main content

tk_pg_core/
graph.rs

1use std::fmt;
2
3use serde::{Deserialize, Serialize};
4
5use crate::errors::PauliGraphError;
6use crate::{ConditionalBoxData, GateType, Op, gate_type_n_args, gate_type_n_params};
7
8/// A single-qubit Pauli operator.
9#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
10#[repr(u8)]
11pub enum Pauli {
12    /// The $X$ Pauli operator.
13    X = 0,
14    /// The $Y$ Pauli operator.
15    Y = 1,
16    /// The $Z$ Pauli operator.
17    Z = 2,
18    /// The identity operator.
19    I = 3,
20}
21
22impl fmt::Display for Pauli {
23    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
24        let s = match self {
25            Pauli::X => "X",
26            Pauli::Y => "Y",
27            Pauli::Z => "Z",
28            Pauli::I => "I",
29        };
30        write!(f, "{s}")
31    }
32}
33
34/// A tk-pg-core program consisting of a qubit count and an ordered list of operations.
35///
36/// The following structural validity checks are performed at `Op` insertion time:
37/// - All `Op::Gate` operations have valid parameter counts for their gate type.
38/// - All `Op::Gate` operations have valid arguments for their gate type, within the valid range.
39/// - All Pauli graph native operations have Pauli strings with length matching the graph's qubit count.
40/// - Conditional bits/values lengths match.
41/// - `Op::BlackBox` operations have all argument qubits within the valid range.
42/// - `GateType::BlackBox` gates have no conditions, and they must have data.
43#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
44#[serde(try_from = "PauliGraphRaw")]
45pub struct PauliGraph {
46    n_qubits: usize,
47    ops: Vec<Op>,
48}
49
50/// Internal struct used for deserialization before validation.
51#[derive(Deserialize)]
52struct PauliGraphRaw {
53    n_qubits: usize,
54    ops: Vec<Op>,
55}
56
57impl TryFrom<PauliGraphRaw> for PauliGraph {
58    type Error = String;
59    fn try_from(raw: PauliGraphRaw) -> Result<Self, Self::Error> {
60        let pg = PauliGraph {
61            n_qubits: raw.n_qubits,
62            ops: raw.ops,
63        };
64        pg.try_validate().map_err(|e| e.to_string())?;
65        Ok(pg)
66    }
67}
68
69impl PauliGraph {
70    /// Creates a new `PauliGraph` with the specified number of qubits and an empty `Op` list.
71    ///
72    /// # Arguments
73    ///
74    /// - `n_qubits` (`usize`) - The number of qubits in the graph.
75    ///
76    /// # Returns
77    ///
78    /// - `Self` - A new `PauliGraph` instance with the specified number of qubits and an empty `Op` list.
79    ///
80    pub fn new(n_qubits: usize) -> Self {
81        Self {
82            n_qubits,
83            ops: vec![],
84        }
85    }
86
87    /// Returns the graph with its operation list replaced by `ops`.
88    ///
89    /// # Arguments
90    ///
91    /// - `mut self` (`Self`) - The current graph instance.
92    /// - `ops` (`Vec<Op>`) - The new list of `Op`s to replace the current list.
93    ///
94    /// # Returns
95    ///
96    /// - `Self` - The updated graph instance with the new `Op` list.
97    ///
98    /// # Panics
99    ///
100    /// Panics if any operation in `ops` fails the structural validity checks.
101    pub fn with_ops(mut self, ops: Vec<Op>) -> Self {
102        for op in &ops {
103            validate_op(op, self.get_n_qubits());
104        }
105        self.ops = ops;
106        self
107    }
108
109    /// Appends a single `op` to the graph.
110    ///
111    /// # Arguments
112    ///
113    /// - `&mut self` (`Self`) - The current graph instance.
114    /// - `op` (`Op`) - The `Op` to append.
115    ///
116    /// # Panics
117    ///
118    /// Panics if `op` fails the structural validity checks.
119    pub fn add_op(&mut self, op: Op) {
120        validate_op(&op, self.get_n_qubits());
121        self.ops.push(op);
122    }
123
124    /// Inserts `op` at position `index` in the `Op` list.
125    ///
126    /// # Arguments
127    ///
128    /// - `&mut self` (`Self`) - The current graph instance.
129    /// - `index` (`usize`) - The position at which to insert the `Op`.
130    /// - `op` (`Op`) - The `Op` to insert.
131    ///
132    /// # Panics
133    ///
134    /// Panics if `op` fails the structural validity checks.
135    pub fn insert_op(&mut self, index: usize, op: Op) {
136        validate_op(&op, self.get_n_qubits());
137        self.ops.insert(index, op);
138    }
139
140    /// Appends all operations from `other` onto this graph.
141    ///
142    /// # Arguments
143    ///
144    /// - `&mut self` (`Self`) - The current graph instance.
145    /// - `mut other` (`PauliGraph`) - The graph whose operations are to be appended.
146    ///
147    /// # Panics
148    ///
149    /// Panics if the number of qubits in `self` and `other` do not match.
150    pub fn extend(&mut self, mut other: PauliGraph) {
151        if self.n_qubits != other.n_qubits {
152            panic!(
153                "PauliGraph n_qubits must match: self has {}, other has {}",
154                self.n_qubits, other.n_qubits
155            );
156        }
157        self.ops.append(&mut other.ops);
158    }
159
160    /// Appends conditional `op`.
161    ///
162    /// If the last operation is a
163    /// [`Op::ConditionalBox`] with matching conditions, `op` is appended into it instead of
164    /// creating a new box. If `conditional_bits` is empty, `op` is added unconditionally
165    /// via [`Self::add_op`].
166    ///
167    /// # Panics
168    ///
169    /// Panics if `op` fails the structural validity checks, or if `conditional_bits` and
170    /// `conditional_values` have different lengths.
171    pub fn add_conditional_op(
172        &mut self,
173        op: Op,
174        conditional_bits: Vec<usize>,
175        conditional_values: Vec<bool>,
176    ) {
177        if conditional_bits.len() != conditional_values.len() {
178            panic!("Length of conditional bits and values must match");
179        }
180        if conditional_bits.is_empty() {
181            self.add_op(op);
182        } else {
183            let n_qubits = self.get_n_qubits();
184            if let Some(last_op) = self.ops.last_mut()
185                && let Op::ConditionalBox { data } = last_op
186                && conditional_box_matches(data, &conditional_bits, &conditional_values)
187            {
188                validate_op(&op, n_qubits);
189                data.ops.push(op);
190                return;
191            }
192            self.add_op(Op::ConditionalBox {
193                data: ConditionalBoxData::new(vec![op], conditional_bits, conditional_values),
194            });
195        }
196    }
197
198    /// Inserts conditional `op` at position `index`.
199    ///
200    /// If the adjacent operation at `index - 1` or `index` is a [`Op::ConditionalBox`] with matching conditions, `op` is merged into
201    /// it instead of creating a new box. If `conditional_bits` is empty, `op` is inserted
202    /// unconditionally via [`Self::insert_op`].
203    ///
204    /// # Panics
205    ///
206    /// Panics if `op` fails the structural validity checks, or if `conditional_bits` and
207    /// `conditional_values` have different lengths.
208    pub fn insert_conditional_op(
209        &mut self,
210        index: usize,
211        op: Op,
212        conditional_bits: Vec<usize>,
213        conditional_values: Vec<bool>,
214    ) {
215        if conditional_bits.len() != conditional_values.len() {
216            panic!("Length of conditional bits and values must match");
217        }
218        if conditional_bits.is_empty() {
219            self.insert_op(index, op);
220            return;
221        }
222
223        let n_qubits = self.get_n_qubits();
224        if index > 0
225            && let Some(Op::ConditionalBox { data }) = self.ops.get_mut(index - 1)
226            && conditional_box_matches(data, &conditional_bits, &conditional_values)
227        {
228            validate_op(&op, n_qubits);
229            data.ops.push(op);
230            return;
231        }
232
233        if let Some(Op::ConditionalBox { data }) = self.ops.get_mut(index)
234            && conditional_box_matches(data, &conditional_bits, &conditional_values)
235        {
236            validate_op(&op, n_qubits);
237            data.ops.insert(0, op);
238            return;
239        }
240
241        self.insert_op(
242            index,
243            Op::ConditionalBox {
244                data: ConditionalBoxData::new(vec![op], conditional_bits, conditional_values),
245            },
246        );
247    }
248
249    /// Removes the operation at position `index`.
250    ///
251    /// # Panics
252    ///
253    /// Panics if `index` is out of bounds.
254    pub fn remove_op(&mut self, index: usize) {
255        self.ops.remove(index);
256    }
257
258    /// Swaps the operations at positions `index1` and `index2`.
259    ///
260    /// # Panics
261    ///
262    /// Panics if `index1` or `index2` is out of bounds.
263    pub fn swap_ops(&mut self, index1: usize, index2: usize) {
264        self.ops.swap(index1, index2);
265    }
266
267    /// Replaces the operations in the index range `range` with `new_ops`.
268    ///
269    /// # Panics
270    ///
271    /// Panics if any operation in `new_ops` fails the structural validity checks or if `range` is out of bounds.
272    pub fn replace_slice(&mut self, range: std::ops::Range<usize>, new_ops: Vec<Op>) {
273        for op in &new_ops {
274            validate_op(op, self.get_n_qubits());
275        }
276        self.ops.splice(range, new_ops);
277    }
278
279    /// Increases the qubit count by one, extending all Pauli strings with an identity on the new qubit.
280    pub fn add_qubit(&mut self) {
281        let old_n_qubits = self.n_qubits;
282        self.n_qubits += 1;
283        for op in &mut self.ops {
284            add_qubit_to_op(op, old_n_qubits);
285        }
286    }
287
288    /// Returns the ordered operations in the graph.
289    pub fn get_ops(&self) -> &Vec<Op> {
290        &self.ops
291    }
292
293    /// Returns the number of qubits.
294    pub fn get_n_qubits(&self) -> usize {
295        self.n_qubits
296    }
297
298    /// Validates all operations against the structural validity checks.
299    ///
300    /// # Panics
301    ///
302    /// Panics if any operation fails the structural validity checks.
303    pub fn try_validate(&self) -> Result<(), PauliGraphError> {
304        for op in self.get_ops() {
305            try_validate_op(op, self.get_n_qubits())?;
306        }
307        Ok(())
308    }
309}
310
311fn try_validate_op(op: &Op, pg_nqubits: usize) -> Result<(), PauliGraphError> {
312    match op {
313        Op::Rotation { data } => validate_pauli_string_len(data.get_string().len(), pg_nqubits, op),
314        Op::Measure { data } => validate_pauli_string_len(data.get_string().len(), pg_nqubits, op),
315        Op::Reset { data } => {
316            validate_pauli_string_len(data.get_first_string().len(), pg_nqubits, op)?;
317            validate_pauli_string_len(data.get_second_string().len(), pg_nqubits, op)
318        }
319        Op::Tableau { data } => {
320            for (string, _) in data.get_z_images().iter().chain(data.get_x_images()) {
321                validate_pauli_string_len(string.len(), pg_nqubits, op)?;
322            }
323            Ok(())
324        }
325        Op::Gate { data } => {
326            if let Some(expected_arg_counts) = gate_type_n_args(data.get_gate_type())
327                && data.get_args().len() != expected_arg_counts
328            {
329                return Err(PauliGraphError::InvalidOp {
330                    op: op.clone(),
331                    message: format!(
332                        "Gate has wrong number of arguments.\nExpected: {}\nGot: {}",
333                        expected_arg_counts,
334                        data.get_args().len()
335                    ),
336                });
337            }
338            let expected_param_counts = gate_type_n_params(data.get_gate_type());
339            if data.get_params().len() != expected_param_counts {
340                return Err(PauliGraphError::InvalidOp {
341                    op: op.clone(),
342                    message: format!(
343                        "Gate has wrong number of parameters.\nExpected: {}\nGot: {}",
344                        expected_param_counts,
345                        data.get_params().len()
346                    ),
347                });
348            }
349            if data.get_gate_type() == &GateType::Measure {
350                validate_op_arg_range(
351                    *data
352                        .get_args()
353                        .first()
354                        .expect("Measure gate missing qubit argument"),
355                    pg_nqubits,
356                    op,
357                )?;
358            } else {
359                validate_op_arg_range(
360                    *data
361                        .get_args()
362                        .iter()
363                        .max()
364                        .expect("Gate missing qubit arguments"),
365                    pg_nqubits,
366                    op,
367                )?;
368            }
369            let conditional_bits_len = data.get_conditional_bits().len();
370            let conditional_values_len = data.get_conditional_values().len();
371            if conditional_bits_len != conditional_values_len {
372                return Err(PauliGraphError::InvalidOp {
373                    op: op.clone(),
374                    message: format!(
375                        "Gate has mismatched conditional bits and values lengths.\nBits: {}\nValues: {}",
376                        conditional_bits_len, conditional_values_len
377                    ),
378                });
379            }
380            if data.get_gate_type() == &GateType::BlackBox {
381                if data.get_args().is_empty() {
382                    return Err(PauliGraphError::InvalidOp {
383                        op: op.clone(),
384                        message: "BlackBox gate cannot have empty arguments.".into(),
385                    });
386                }
387                if !data.get_conditional_bits().is_empty()
388                    || !data.get_conditional_values().is_empty()
389                {
390                    return Err(PauliGraphError::InvalidOp {
391                        op: op.clone(),
392                        message: "BlackBox gates cannot have conditions.".into(),
393                    });
394                }
395                if data.get_data().is_none() {
396                    return Err(PauliGraphError::InvalidOp {
397                        op: op.clone(),
398                        message: "BlackBox gate is missing payload data.".into(),
399                    });
400                }
401            }
402            Ok(())
403        }
404        Op::BlackBox { data } => validate_op_arg_range(
405            *data
406                .get_qubits()
407                .iter()
408                .max()
409                .expect("Gate missing qubit argument"),
410            pg_nqubits,
411            op,
412        ),
413        Op::ConditionalBox { data } => {
414            let conditional_bits_len = data.get_conditional_bits().len();
415            let conditional_values_len = data.get_conditional_values().len();
416            if conditional_bits_len != conditional_values_len {
417                return Err(PauliGraphError::InvalidOp {
418                    op: op.clone(),
419                    message: format!(
420                        "ConditionalBox has mismatched conditional bits and values lengths.\nBits: {}\nValues: {}",
421                        conditional_bits_len, conditional_values_len
422                    ),
423                });
424            }
425            if conditional_bits_len == 0 {
426                return Err(PauliGraphError::InvalidOp {
427                    op: op.clone(),
428                    message: "ConditionalBox must have non-empty conditional bits and values."
429                        .into(),
430                });
431            }
432            for inner_op in data.get_ops() {
433                try_validate_op(inner_op, pg_nqubits)?;
434            }
435            Ok(())
436        }
437        Op::SetBoundary => Ok(()),
438    }
439}
440
441fn validate_op(op: &Op, pg_nqubits: usize) {
442    try_validate_op(op, pg_nqubits).unwrap_or_else(|e| panic!("{e}"))
443}
444
445fn validate_op_arg_range(maxq: usize, n_qubits: usize, op: &Op) -> Result<(), PauliGraphError> {
446    if maxq >= n_qubits {
447        Err(PauliGraphError::InvalidOp {
448            op: op.clone(),
449            message: format!(
450                "Operation has argument qubit index out of range.\nExpected: < {}\nGot: {}",
451                n_qubits, maxq
452            ),
453        })?
454    }
455    Ok(())
456}
457fn validate_pauli_string_len(len: usize, n_qubits: usize, op: &Op) -> Result<(), PauliGraphError> {
458    if len != n_qubits {
459        Err(PauliGraphError::InvalidOp {
460            op: op.clone(),
461            message: format!(
462                "String length does not match graph qubit count.\nExpected: {}\nGot: {}",
463                n_qubits, len
464            ),
465        })?
466    }
467    Ok(())
468}
469
470fn conditional_box_matches(
471    data: &ConditionalBoxData,
472    conditional_bits: &[usize],
473    conditional_values: &[bool],
474) -> bool {
475    data.get_conditional_bits() == conditional_bits
476        && data.get_conditional_values() == conditional_values
477}
478
479fn append_identity(paulis: &mut Vec<Pauli>) {
480    paulis.push(Pauli::I);
481}
482
483fn single_qubit_tableau_image(n_qubits: usize, pauli: Pauli) -> Vec<Pauli> {
484    let mut image = vec![Pauli::I; n_qubits];
485    image.push(pauli);
486    image
487}
488
489fn add_qubit_to_op(op: &mut Op, old_n_qubits: usize) {
490    match op {
491        Op::Rotation { data } => {
492            append_identity(&mut data.string);
493        }
494        Op::Measure { data } => {
495            append_identity(&mut data.string);
496        }
497        Op::Reset { data } => {
498            append_identity(&mut data.first_string);
499            append_identity(&mut data.second_string);
500        }
501        Op::Tableau { data } => {
502            for (string, _) in &mut data.z_images {
503                append_identity(string);
504            }
505            for (string, _) in &mut data.x_images {
506                append_identity(string);
507            }
508            data.z_images
509                .push((single_qubit_tableau_image(old_n_qubits, Pauli::Z), false));
510            data.x_images
511                .push((single_qubit_tableau_image(old_n_qubits, Pauli::X), false));
512        }
513        Op::ConditionalBox { data } => {
514            for inner_op in &mut data.ops {
515                add_qubit_to_op(inner_op, old_n_qubits);
516            }
517        }
518        Op::Gate { .. } | Op::BlackBox { .. } | Op::SetBoundary => {}
519    }
520}