quil_rs/program/analysis/
qubit_graph.rs

1//! The `QubitGraph` is a logical execution/dependency graph of
2//! instructions with respect to gates on shared qubits.
3
4// Copyright 2024 Rigetti Computing
5//
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17use std::collections::HashMap;
18
19use crate::instruction::{Instruction, InstructionHandler, InstructionRole};
20use crate::quil::Quil;
21use petgraph::{graph::DiGraph, Direction};
22
23use super::BasicBlock;
24
25#[derive(Debug, thiserror::Error)]
26pub enum QubitGraphError {
27    #[error("Unsupported instruction: {}", .0.to_quil_or_debug())]
28    UnsupportedInstruction(Instruction),
29}
30
31/// QubitGraph is a logical execution/dependency graph of instructions.  Pragma, RF Control, and Control Flow instructions
32/// are not supported. It is a directed graph *from* the first instructions (the set of instructions that do not depend
33/// on prior instructions) *to* the last instructions (the set of instructions that are not prerequisites for any later
34/// instructions).
35///
36/// Nodes are instructions; edges link subsequent instructions which use a shared qubit.
37#[derive(Debug)]
38pub struct QubitGraph<'a> {
39    graph: DiGraph<&'a Instruction, ()>,
40}
41
42impl<'a> QubitGraph<'a> {
43    pub(crate) fn new(
44        instructions: impl Iterator<Item = &'a Instruction>,
45    ) -> Result<Self, QubitGraphError> {
46        let mut last_instruction_for_qubit = HashMap::new();
47        let mut graph = DiGraph::new();
48        let mut handler = InstructionHandler::default();
49
50        for instruction in instructions {
51            match handler.role_for_instruction(instruction) {
52                InstructionRole::ClassicalCompute => {
53                    if let Instruction::Pragma(_) = instruction {
54                        return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()));
55                    }
56                } // Valid, mostly ignored
57                InstructionRole::ControlFlow => match &instruction {
58                    Instruction::Jump(_)
59                    | Instruction::JumpWhen(_)
60                    | Instruction::JumpUnless(_) => {
61                        return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()))
62                    }
63                    _ => {}
64                },
65                InstructionRole::ProgramComposition => {} // Valid, includes Gate, etc.,
66                InstructionRole::RFControl => {
67                    return Err(QubitGraphError::UnsupportedInstruction(instruction.clone()))
68                }
69            }
70
71            let qubits: Vec<_> = instruction.get_qubits().into_iter().collect();
72
73            let node = graph.add_node(instruction);
74
75            for qubit in qubits {
76                if let Some(last_instruction) = last_instruction_for_qubit.insert(qubit, node) {
77                    graph.add_edge(last_instruction, node, ());
78                }
79            }
80        }
81
82        Ok(Self { graph })
83    }
84
85    /// Fold over all paths over the graph, starting from sources (nodes with no incoming edges),
86    /// and ending at sinks (nodes with no outgoing edges).
87    ///
88    /// The `f` function is called for each instruction in each path, with the current accumulator value and the current
89    /// instruction.
90    ///
91    /// # Examples
92    ///
93    /// ## Tree
94    ///
95    /// ```text
96    /// CNOT 0 1
97    /// X 0
98    /// H 1
99    /// ```
100    ///
101    /// 1. `CNOT 0 1` is visited with the initial value, and a new accumulator `A` is returned from `f`.
102    /// 2. `X 0` is visited with accumulator `A`, and a result value `B` is returned from `f`.
103    /// 3. `H 1` is visited with accumulator `A`, and a second result value `C` is returned from `f`.
104    /// 4. The result values are collected into a [`Vec`] and returned as `[B, C]`.
105    ///
106    /// ## Diamond
107    ///
108    /// If the program graph forms a diamond shape (i.e. multiple paths converge to a single node), the `f` function
109    /// will be called multiple times with the same instruction, but with potentially different accumulator values.
110    ///
111    /// ```text
112    /// CNOT 0 1
113    /// X 0
114    /// H 1
115    /// CNOT 1 0
116    /// ```
117    ///
118    /// 1. `CNOT 0 1` is visited with the initial value, and a new accumulator `A` is returned from `f`.
119    /// 2. `X 0` is visited with accumulator `A`, and a new accumulator `B` is returned from `f`.
120    /// 3. `H 1` is visited with accumulator `A`, and a new accumulator `C` is returned from `f`.
121    /// 4. `CNOT 1 0` is visited with accumulator `B`, and a result value `D` is returned from `f`.
122    /// 5. `CNOT 1 0` is visited with accumulator `C`, and a result value `E` is returned from `f`.
123    /// 5. The result values are collected into a [`Vec`] and returned as `[D, E]`.
124    fn path_fold<T, F>(&self, initial_value: T, mut f: F) -> Vec<T>
125    where
126        T: Clone + std::fmt::Debug,
127        F: FnMut(T, &Instruction) -> T,
128    {
129        let nodes: Vec<_> = self.graph.externals(Direction::Incoming).collect();
130        let mut stack = vec![(initial_value, nodes)];
131        let mut result = Vec::new();
132
133        while let Some((acc, nodes)) = stack.pop() {
134            if nodes.is_empty() {
135                result.push(acc);
136                continue;
137            }
138
139            for node in nodes {
140                let instruction = &self.graph[node];
141                let value = f(acc.clone(), instruction);
142                stack.push((
143                    value,
144                    self.graph
145                        .neighbors_directed(node, Direction::Outgoing)
146                        .collect(),
147                ));
148            }
149        }
150
151        result
152    }
153
154    /// Returns the length of the longest path from an initial instruction (one with no prerequisite instructions) to a final
155    /// instruction (one with no dependent instructions), where the length of a path is the number of gate instructions in the path.
156    ///
157    /// # Arguments
158    ///
159    /// * `gate_minimum_qubit_count` - The minimum number of qubits in a gate for it to be counted in the depth.
160    pub fn gate_depth(&self, gate_minimum_qubit_count: usize) -> usize {
161        let path_lengths = self.path_fold(0, |depth: usize, instruction: &Instruction| -> usize {
162            if let Instruction::Gate(gate) = instruction {
163                if gate.qubits.len() >= gate_minimum_qubit_count {
164                    return depth + 1;
165                }
166            }
167            depth
168        });
169        path_lengths.into_iter().max().unwrap_or_default()
170    }
171}
172
173impl<'a> TryFrom<&'_ BasicBlock<'a>> for QubitGraph<'a> {
174    type Error = QubitGraphError;
175
176    fn try_from(block: &BasicBlock<'a>) -> Result<Self, Self::Error> {
177        QubitGraph::new(block.instructions().iter().copied())
178    }
179}
180
181#[cfg(test)]
182mod tests {
183    use crate::Program;
184    use rstest::rstest;
185
186    use super::*;
187
188    use super::super::test_programs::*;
189
190    #[rstest]
191    #[case(QUIL_AS_TREE, 2)]
192    #[case(QUIL_AS_INVERSE_TREE, 2)]
193    #[case(QUIL_AS_LINEAR, 4)]
194    #[case(QUIL_WITH_DIAMOND, 6)]
195    #[case(QUIL_WITH_SWAP, 3)]
196    #[case(KITCHEN_SINK_QUIL, 2)]
197    fn gate_depth(#[case] input: &str, #[case] expected: usize) {
198        let program: Program = input.parse().unwrap();
199        let block: BasicBlock = (&program).try_into().unwrap();
200        let graph: QubitGraph = (&block).try_into().unwrap();
201        let depth = graph.gate_depth(1);
202        assert_eq!(expected, depth);
203    }
204
205    #[rstest]
206    #[case(QUIL_AS_TREE, 1)]
207    #[case(QUIL_AS_INVERSE_TREE, 1)]
208    #[case(QUIL_AS_LINEAR, 0)]
209    #[case(QUIL_WITH_DIAMOND, 2)]
210    #[case(QUIL_WITH_SWAP, 1)]
211    #[case(KITCHEN_SINK_QUIL, 1)]
212    fn multiqubit_gate_depth(#[case] input: &str, #[case] expected: usize) {
213        let program: Program = input.parse().unwrap();
214        let block: BasicBlock = (&program).try_into().unwrap();
215        let graph: QubitGraph = (&block).try_into().unwrap();
216        let depth = graph.gate_depth(2);
217        assert_eq!(expected, depth);
218    }
219
220    #[rstest]
221    #[case(QUIL_AS_TREE, Some(2))]
222    #[case(QUIL_AS_INVERSE_TREE, Some(2))]
223    #[case(QUIL_AS_LINEAR, Some(4))]
224    #[case(QUIL_WITH_DIAMOND, Some(6))]
225    #[case(QUIL_WITH_SWAP, Some(3))]
226    #[case(KITCHEN_SINK_QUIL, Some(2))]
227    #[case(QUIL_WITH_JUMP, None)]
228    #[case(QUIL_WITH_JUMP_WHEN, None)]
229    #[case(QUIL_WITH_JUMP_UNLESS, None)]
230    fn gate_depth_conditional(#[case] input: &str, #[case] expected: Option<usize>) {
231        let program: Program = input.parse().unwrap();
232        let block = (&program).try_into();
233        let block: BasicBlock = match block {
234            Ok(block) => block,
235            Err(_) => {
236                if expected.is_none() {
237                    return;
238                } else {
239                    panic!("Expected block, got error");
240                }
241            }
242        };
243
244        let maybe_graph: Result<QubitGraph, _> = (&block).try_into();
245        match maybe_graph {
246            Ok(graph) => {
247                let depth = graph.gate_depth(1);
248                assert_eq!(expected, Some(depth));
249            }
250            Err(_) => {
251                assert_eq!(expected, None)
252            }
253        }
254    }
255}
quil_rs/program/analysis/qubit_graph.rs

quil_rs/program/analysis/
qubit_graph.rs
