Repository: HQSquantumsimulations/qoqo (language: python)

Issue:
activating github actions



Discussion / hints:

Fix patch:
diff --git a/Cargo.lock b/Cargo.lock
index 7c710927..6df6fd0b 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -80,6 +80,12 @@ dependencies = [
  "serde",
 ]
 
+[[package]]
+name = "fixedbitset"
+version = "0.4.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "0ce7134b9999ecaf8bcd65542e436736ef32ddca1b3e06094cb6ec5755203b80"
+
 [[package]]
 name = "futures"
 version = "0.3.21"
@@ -191,6 +197,22 @@ dependencies = [
  "syn",
 ]
 
+[[package]]
+name = "hashbrown"
+version = "0.12.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "8a9ee70c43aaf417c914396645a0fa852624801b24ebb7ae78fe8272889ac888"
+
+[[package]]
+name = "indexmap"
+version = "1.9.1"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "10a35a97730320ffe8e2d410b5d3b69279b98d2c14bdb8b70ea89ecf7888d41e"
+dependencies = [
+ "autocfg",
+ "hashbrown",
+]
+
 [[package]]
 name = "indoc"
 version = "1.0.6"
@@ -380,6 +402,16 @@ version = "1.0.7"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "0c520e05135d6e763148b6426a837e239041653ba7becd2e538c076c738025fc"
 
+[[package]]
+name = "petgraph"
+version = "0.6.2"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "e6d5014253a1331579ce62aa67443b4a658c5e7dd03d4bc6d302b94474888143"
+dependencies = [
+ "fixedbitset",
+ "indexmap",
+]
+
 [[package]]
 name = "pin-project-lite"
 version = "0.2.9"
@@ -623,6 +655,7 @@ dependencies = [
  "nalgebra",
  "ndarray",
  "num-complex",
+ "petgraph",
  "proc-macro2",
  "qoqo_calculator",
  "quote",
diff --git a/roqoqo/Cargo.toml b/roqoqo/Cargo.toml
index f760cbee..c94d1267 100644
--- a/roqoqo/Cargo.toml
+++ b/roqoqo/Cargo.toml
@@ -37,6 +37,7 @@ rand_distr = {version="0.4", optional=true}
 rand = { version = "0.8.4"}
 async-trait = {version = "0.1", optional = true}
 futures ={version = "0.3", optional=true}
+petgraph = "0.6.2"
 
 [dev-dependencies]
 serde_test = "1.0"
diff --git a/roqoqo/src/circuitdag.rs b/roqoqo/src/circuitdag.rs
new file mode 100644
index 00000000..937e33ae
--- /dev/null
+++ b/roqoqo/src/circuitdag.rs
@@ -0,0 +1,696 @@
+// Copyright © 2022 HQS Quantum Simulations GmbH. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+// in compliance with the License. You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software distributed under the
+// License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
+// express or implied. See the License for the specific language governing permissions and
+// limitations under the License.
+
+use std::collections::{HashMap, HashSet};
+
+use crate::operations::*;
+use crate::Circuit;
+
+use petgraph::adj::NodeIndex;
+use petgraph::graph::Graph;
+use petgraph::Directed;
+
+/// Represents the Direct Acyclic Graph (DAG) of a Circuit.
+#[derive(Debug)]
+pub struct CircuitDag {
+    pub(crate) graph: Graph<Operation, (), Directed, usize>,
+    pub(crate) commuting_operations: Vec<NodeIndex<usize>>,
+    pub(crate) first_parallel_block: HashSet<NodeIndex<usize>>,
+    pub(crate) last_parallel_block: HashSet<NodeIndex<usize>>,
+    pub(crate) first_all: Option<NodeIndex<usize>>,
+    pub(crate) last_all: Option<NodeIndex<usize>>,
+    pub(crate) first_operation_involving_qubit: HashMap<usize, NodeIndex<usize>>,
+    pub(crate) last_operation_involving_qubit: HashMap<usize, NodeIndex<usize>>,
+    pub(crate) first_operation_involving_classical: HashMap<(String, usize), NodeIndex<usize>>,
+    pub(crate) last_operation_involving_classical: HashMap<(String, usize), NodeIndex<usize>>,
+}
+
+impl CircuitDag {
+    /// Creates a new empty CircuitDag.
+    ///
+    pub fn with_capacity(node_number: usize, edge_number: usize) -> Self {
+        CircuitDag {
+            graph: Graph::<Operation, (), Directed, usize>::with_capacity(node_number, edge_number),
+            commuting_operations: Vec::<NodeIndex<usize>>::new(),
+            first_parallel_block: HashSet::<NodeIndex<usize>>::new(),
+            last_parallel_block: HashSet::<NodeIndex<usize>>::new(),
+            first_all: Option::<NodeIndex<usize>>::None,
+            last_all: Option::<NodeIndex<usize>>::None,
+            first_operation_involving_qubit: HashMap::<usize, NodeIndex<usize>>::new(),
+            last_operation_involving_qubit: HashMap::<usize, NodeIndex<usize>>::new(),
+            first_operation_involving_classical: HashMap::<(String, usize), NodeIndex<usize>>::new(
+            ),
+            last_operation_involving_classical: HashMap::<(String, usize), NodeIndex<usize>>::new(),
+        }
+    }
+
+    /// Adds an operation to the back of the CircuitDag if necessary.
+    ///
+    /// # Arguments
+    ///
+    /// * 'operation' - The Operation to add to the end of the CircuitDag.
+    ///
+    /// # Returns
+    ///
+    /// * 'Option<NodeIndex<usize>>' - The NodeIndex relative to the Operation, if added to CircuitGraph.
+    pub fn add_to_back(&mut self, operation: Operation) -> Option<usize> {
+        // Create node
+        let node = self.graph.add_node(operation.clone());
+
+        // InvolvedQubits: push to commuting_operations or start the add to back process
+        if let (InvolvedQubits::None, InvolvedClassical::None) =
+            (operation.involved_qubits(), operation.involved_classical())
+        {
+            self.commuting_operations.push(node.index());
+        } else {
+            self.add_to_back_involved(node.index());
+        }
+
+        // InvolvedClassical: populate for the first time the classical register data
+        // structure or start the update process
+        if !self.is_definition_classical_populate(node.index(), operation.clone()) {
+            self.update_classical_back(node.index(), operation);
+        }
+
+        Some(node.index())
+    }
+
+    /// Adds an operation that involves some or all qubits to the end of the CircuitDag.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The NodeIndex<usize> of the node to add to the end of the CircuitDag.
+    fn add_to_back_involved(&mut self, node: NodeIndex<usize>) {
+        let node_involved_qubits: InvolvedQubits = self
+            .graph
+            .node_weight(node.into())
+            .unwrap()
+            .involved_qubits();
+        // Calls the proper subfunction depending on the qubits involved
+        //  in the operation
+        if let InvolvedQubits::Set(x) = node_involved_qubits {
+            for qubit in x {
+                self.update_from_qubit_back(node, qubit);
+            }
+        } else if let InvolvedQubits::All = node_involved_qubits {
+            self.update_from_all_operation_back(node);
+        }
+    }
+
+    /// Updates the relevant attributes and the graph of CircuitDag from a single qubit involved
+    /// in an Operation added to the back of the CircuitDag.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node whose Operation involves the qubit.
+    /// * 'qubit' - The qubit involved in the Operation.
+    fn update_from_qubit_back(&mut self, node: NodeIndex<usize>, qubit: usize) {
+        // Update last_operation_involving qubit and last_parallel_block
+        //  depending on current structure
+        if let Some(&i) = self.last_operation_involving_qubit.get(&qubit) {
+            self.graph.add_edge(i.into(), node.into(), ());
+            self.last_parallel_block.remove(&i);
+        }
+        let qubit_presence = self.last_operation_involving_qubit.insert(qubit, node);
+        self.last_parallel_block.insert(node);
+
+        // Update the first layer in case the qubit has never been seen before
+        if qubit_presence.is_none() {
+            // Update first_operation_involving_qubit and first_parallel_block
+            //  depending on last_all
+            if self.last_all.is_none() {
+                self.first_operation_involving_qubit.insert(qubit, node);
+                self.first_parallel_block.insert(node);
+            } else {
+                self.first_operation_involving_qubit
+                    .insert(qubit, self.last_all.unwrap());
+                self.first_parallel_block.insert(self.last_all.unwrap());
+            }
+        }
+    }
+
+    /// Updates the relevant attributes and the graph of CircuitDag when an Operation that involves
+    /// all qubits is added to the back.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node whose Operation involves all qubits.
+    fn update_from_all_operation_back(&mut self, node: NodeIndex<usize>) {
+        // Update first_all and last_all
+        if self.first_all.is_none() {
+            self.first_all = Some(node);
+        }
+        self.last_all = Some(node);
+
+        // Set the node as the only one in last_parallel_block and updates
+        //  first_parallel_block if necessary
+        self.last_parallel_block.clear();
+        self.last_parallel_block.insert(node);
+        if self.first_parallel_block.is_empty() {
+            self.first_parallel_block.insert(node);
+        }
+
+        // Handling InvolvedQubits::All as first Operation
+        if self.first_operation_involving_qubit.is_empty()
+            && self.last_operation_involving_qubit.is_empty()
+        {
+            self.first_operation_involving_qubit.insert(0, node);
+            self.last_operation_involving_qubit.insert(0, node);
+        } else {
+            // All the latest nodes in the graph must now point to the new node and
+            //  last_operation_involving_qubit is updated
+            let mut temp_map: HashMap<usize, NodeIndex<usize>> =
+                HashMap::with_capacity(self.last_operation_involving_qubit.capacity());
+            for (&qubit, &old_node) in &self.last_operation_involving_qubit {
+                self.graph.update_edge(old_node.into(), node.into(), ());
+                temp_map.insert(qubit, node);
+            }
+            self.last_operation_involving_qubit = temp_map;
+        }
+    }
+
+    /// Adds an operation to the front of the CircuitDag is necessary.
+    ///
+    /// # Arguments
+    ///
+    /// * 'operation' - The Operation to add to the front of the CircuitDag.
+    ///
+    /// # Returns
+    ///
+    /// * 'Option<NodeIndex<usize>>' - The NodeIndex<usize> relative to the Operation, if added to CircuitGraph.
+    pub fn add_to_front(&mut self, operation: Operation) -> Option<usize> {
+        // Create node
+        let node = self.graph.add_node(operation.clone());
+
+        // InvolvedQubits: push to commuting_operations or start the add to front process
+        if let (InvolvedQubits::None, InvolvedClassical::None) =
+            (operation.involved_qubits(), operation.involved_classical())
+        {
+            self.commuting_operations.push(node.index());
+        } else {
+            self.add_to_front_involved(node.index());
+        }
+
+        // InvolvedClassical: populate for the first time the classical register data
+        // structure or start the update process
+        if !self.is_definition_classical_populate(node.index(), operation.clone()) {
+            self.update_classical_front(node.index(), operation);
+        }
+
+        Some(node.index())
+    }
+
+    /// Adds an operation that involves some or all qubits to the front of the CircuitDag.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The NodeIndex<usize> of the node to add to the end of the CircuitDag.
+    fn add_to_front_involved(&mut self, node: NodeIndex<usize>) {
+        let node_involved_qubits: InvolvedQubits = self
+            .graph
+            .node_weight(node.into())
+            .unwrap()
+            .involved_qubits();
+        // Calls the proper subfunction depending on the qubits involved
+        //  in the operation
+        if let InvolvedQubits::Set(x) = node_involved_qubits {
+            for qubit in x {
+                self.update_from_qubit_front(node, qubit);
+            }
+        } else if let InvolvedQubits::All = node_involved_qubits {
+            self.update_from_all_operation_front(node);
+        }
+    }
+
+    /// Updates the relevant attributes and the graph of CircuitDag from a single qubit involved
+    /// in an Operation added to the front of the CircuitDag.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node whose Operation involves the qubit.
+    /// * 'qubit' - The qubit involved in the Operation.
+    fn update_from_qubit_front(&mut self, node: NodeIndex<usize>, qubit: usize) {
+        // Update first_operation_involving qubit and first_parallel_block
+        //  depending on current structure
+        if let Some(&i) = self.first_operation_involving_qubit.get(&qubit) {
+            self.graph.add_edge(node.into(), i.into(), ());
+            self.first_parallel_block.remove(&i);
+        }
+        let qubit_presence = self.first_operation_involving_qubit.insert(qubit, node);
+        self.first_parallel_block.insert(node);
+
+        // Update the last layer in case the qubit has never been seen before
+        if qubit_presence.is_none() {
+            // Update last_operation_involving_qubit and last_parallel_block
+            //  depending on first_all
+            if self.first_all.is_none() {
+                self.last_operation_involving_qubit.insert(qubit, node);
+                self.last_parallel_block.insert(node);
+            } else {
+                self.last_operation_involving_qubit
+                    .insert(qubit, self.first_all.unwrap());
+                self.last_parallel_block.insert(self.first_all.unwrap());
+            }
+        }
+    }
+
+    /// Updates the relevant attributes and the graph of CircuitDag when an Operation that involves
+    /// all qubits is added to the front.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node whose Operation involves all qubits.
+    fn update_from_all_operation_front(&mut self, node: NodeIndex<usize>) {
+        // Update last_all and first_all
+        if self.last_all.is_none() {
+            self.last_all = Some(node);
+        }
+        self.first_all = Some(node);
+
+        // Set the node as the only one in first_parallel_block and updates
+        //  last_parallel_block if necessary
+        self.first_parallel_block.clear();
+        self.first_parallel_block.insert(node);
+        if self.last_parallel_block.is_empty() {
+            self.last_parallel_block.insert(node);
+        }
+
+        // Handling InvolvedQubits::All as first Operation
+        if self.first_operation_involving_qubit.is_empty()
+            && self.last_operation_involving_qubit.is_empty()
+        {
+            self.first_operation_involving_qubit.insert(0, node);
+            self.last_operation_involving_qubit.insert(0, node);
+        } else {
+            // The new node in the graph must point to the last first layer nodes and
+            //  first_operation_involving_qubit is updated
+            let mut temp_map: HashMap<usize, NodeIndex<usize>> =
+                HashMap::with_capacity(self.first_operation_involving_qubit.capacity());
+            for (&qubit, &old_node) in &self.first_operation_involving_qubit {
+                self.graph.update_edge(node.into(), old_node.into(), ());
+                temp_map.insert(qubit, node);
+            }
+            self.first_operation_involving_qubit = temp_map;
+        }
+    }
+
+    /// Given an Operation and its node, checks that it is a Definition and populates the
+    /// classical layer accordingly.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node of the Operation.
+    /// * 'operation' - The Operation itself.
+    fn is_definition_classical_populate(
+        &mut self,
+        node: NodeIndex<usize>,
+        operation: Operation,
+    ) -> bool {
+        match &operation {
+            Operation::DefinitionBit(_) => {
+                let new_op: DefinitionBit = operation.clone().try_into().unwrap();
+                for i in 0..*new_op.length() {
+                    self.first_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                    self.last_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                }
+                true
+            }
+            Operation::DefinitionComplex(_) => {
+                let new_op: DefinitionComplex = operation.clone().try_into().unwrap();
+                for i in 0..*new_op.length() {
+                    self.first_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                    self.last_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                }
+                true
+            }
+            Operation::DefinitionFloat(_) => {
+                let new_op: DefinitionFloat = operation.clone().try_into().unwrap();
+                for i in 0..*new_op.length() {
+                    self.first_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                    self.last_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                }
+                true
+            }
+            Operation::DefinitionUsize(_) => {
+                let new_op: DefinitionUsize = operation.clone().try_into().unwrap();
+                for i in 0..*new_op.length() {
+                    self.first_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                    self.last_operation_involving_classical
+                        .insert((String::from(new_op.name()), i), node);
+                }
+                true
+            }
+            _ => false,
+        }
+    }
+
+    /// Checks and updates the relevant classical registers attributes from a given Operation
+    /// that was added to the back of the graph.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node of the Operation that was added to the back of the graph.
+    /// * 'operation' - The Operation that was added to the back of the graph.
+    fn update_classical_back(&mut self, node: NodeIndex<usize>, operation: Operation) {
+        // Depending on InvolvedClassical, update both last_ and first_operation_involving_classical
+        match operation.involved_classical() {
+            InvolvedClassical::Set(x) => {
+                // Cycle InvolvedClassical::Set, insert node everywhere in last_operation_involving_classical
+                for (name, readout) in &x {
+                    // If the classical register has never been seen before, insert it in
+                    //  first_operation_involving_classical as well
+                    if self
+                        .last_operation_involving_classical
+                        .insert((String::clone(name), *readout), node)
+                        .is_none()
+                    {
+                        self.first_operation_involving_classical
+                            .insert((String::clone(name), *readout), node);
+                    }
+                }
+            }
+            InvolvedClassical::All(x) | InvolvedClassical::AllQubits(x) => {
+                let mut temp_map: HashMap<(String, usize), NodeIndex<usize>> =
+                    HashMap::with_capacity(self.last_operation_involving_classical.capacity());
+                // Cycle last_operation_involving_classical
+                for (name, readout) in self.last_operation_involving_classical.keys() {
+                    // If the classical register's name in InvolvedClassical::All or ::AllQubits
+                    //  is present in last_operation_involving_classical, insert the node
+                    //  in the temporary HashMap
+                    if *name == x {
+                        temp_map.insert((String::clone(name), *readout), node);
+                    }
+                }
+                // Update last_operation_involving_classical with the temporary HashMap
+                self.last_operation_involving_classical = temp_map.clone();
+            }
+            InvolvedClassical::None => (),
+        }
+    }
+
+    /// Checks and updates the relevant classical registers attributes from a given Operation
+    /// that was added to the front of the graph.
+    ///
+    /// # Arguments
+    ///
+    /// * 'node' - The index of the node of the Operation that was added to the front of the graph.
+    /// * 'operation' - The Operation that was added to the front of the graph.
+    fn update_classical_front(&mut self, node: NodeIndex<usize>, operation: Operation) {
+        // Depending on InvolvedClassical, update both last_ and first_operation_involving_classical
+        match operation.involved_classical() {
+            InvolvedClassical::Set(x) => {
+                // Cycle InvolvedClassical::Set, insert node everywhere in first_operation_involving_classical
+                for (name, readout) in &x {
+                    // If the classical register has never been seen before, insert it in
+                    //  last_operation_involving_classical as well
+                    if self
+                        .first_operation_involving_classical
+                        .insert((String::clone(name), *readout), node)
+                        .is_none()
+                    {
+                        self.last_operation_involving_classical
+                            .insert((String::clone(name), *readout), node);
+                    }
+                }
+            }
+            InvolvedClassical::All(x) | InvolvedClassical::AllQubits(x) => {
+                // Cycle first_operation_involving_classical
+                let mut temp_map: HashMap<(String, usize), NodeIndex<usize>> =
+                    HashMap::with_capacity(self.first_operation_involving_classical.capacity());
+                for (name, readout) in self.first_operation_involving_classical.keys() {
+                    // If the classical register's name in InvolvedClassical::All or ::AllQubits
+                    //  is present in first_operation_involving_classical, insert the node
+                    //  in the temporary HashMap
+                    if *name == x {
+                        temp_map.insert((String::clone(name), *readout), node);
+                    }
+                }
+                // Update first_operation_involving_classical with the temporary HashMap
+                self.first_operation_involving_classical = temp_map.clone();
+            }
+            InvolvedClassical::None => (),
+        }
+    }
+
+    /// Returns a reference to the vector of commuting operations in CircuitDag.
+    ///
+    pub fn commuting_operations(&self) -> &Vec<usize> {
+        &self.commuting_operations
+    }
+
+    /// Returns a reference to the HasSet containing the nodes in the first parallel block.
+    ///
+    pub fn first_parallel_block(&self) -> &HashSet<usize> {
+        &self.first_parallel_block
+    }
+
+    /// Returns a reference to the HashSet containing the nodes in the last parallel block.
+    ///
+    pub fn last_parallel_block(&self) -> &HashSet<usize> {
+        &self.last_parallel_block
+    }
+
+    /// Returns a reference to the HashMap where a key represents a qubit and its value represents
+    /// the first node that involves that qubit.
+    ///
+    pub fn first_operation_involving_qubit(&self) -> &HashMap<usize, usize> {
+        &self.first_operation_involving_qubit
+    }
+
+    /// Returns a reference to the HashMap where a key represents a qubit and its value represents
+    /// the last node that involves that qubit.
+    ///
+    pub fn last_operation_involving_qubit(&self) -> &HashMap<usize, usize> {
+        &self.last_operation_involving_qubit
+    }
+
+    /// Returns a reference to the HashMap where a key is composed by the name and the size
+    /// of the classical register and its value represents the first node that involves that
+    /// register.
+    ///
+    pub fn first_operation_involving_classical(&self) -> &HashMap<(String, usize), usize> {
+        &self.first_operation_involving_classical
+    }
+
+    /// Returns a reference to the HashMap where a key is composed by the name and the size
+    /// of the classical register and its value represents the last node that involves that
+    /// register.
+    ///
+    pub fn last_operation_involving_classical(&self) -> &HashMap<(String, usize), usize> {
+        &self.last_operation_involving_classical
+    }
+}
+
+/// Creates a new CircuitDag from a given Circuit.
+///
+impl From<Circuit> for CircuitDag {
+    fn from(circuit: Circuit) -> Self {
+        let mut new_dag = CircuitDag {
+            graph: Graph::<Operation, (), Directed, usize>::with_capacity(
+                circuit.len(),
+                circuit.operations().len(),
+            ),
+            commuting_operations: Vec::<NodeIndex<usize>>::new(),
+            first_parallel_block: HashSet::<NodeIndex<usize>>::new(),
+            last_parallel_block: HashSet::<NodeIndex<usize>>::new(),
+            first_all: Option::<NodeIndex<usize>>::None,
+            last_all: Option::<NodeIndex<usize>>::None,
+            first_operation_involving_qubit: HashMap::<usize, NodeIndex<usize>>::new(),
+            last_operation_involving_qubit: HashMap::<usize, NodeIndex<usize>>::new(),
+            first_operation_involving_classical: HashMap::<(String, usize), NodeIndex<usize>>::new(
+            ),
+            last_operation_involving_classical: HashMap::<(String, usize), NodeIndex<usize>>::new(),
+        };
+
+        for operation in circuit.operations() {
+            new_dag.add_to_back(operation.clone());
+        }
+
+        new_dag
+    }
+}
+
+/// The following module contains tests that need access to internal data structures.
+///
+#[cfg(test)]
+mod tests {
+    use crate::operations::*;
+    use crate::{Circuit, CircuitDag};
+    use test_case::test_case;
+
+    static DEFAULT_NODE_NUMBER: usize = 10;
+    static DEFAULT_EDGE_NUMBER: usize = 30;
+
+    /// Test graph node existance after adding an operation that involves qubits.
+    ///
+    #[test_case(Operation::from(PauliX::new(0)))]
+    #[test_case(Operation::from(PauliY::new(1)))]
+    #[test_case(Operation::from(ControlledPauliZ::new(0, 1)))]
+    fn check_node_existance(operation: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+        dag.add_to_back(operation.clone());
+
+        assert!(dag.graph.node_count() == 1);
+
+        dag.add_to_front(operation.clone());
+        dag.add_to_back(Operation::from(CNOT::new(0, 1)));
+
+        assert!(dag.graph.node_count() == 3);
+    }
+
+    #[test_case(Operation::from(PauliX::new(0)), Operation::from(PauliY::new(0)))]
+    #[test_case(Operation::from(PauliZ::new(0)), Operation::from(CNOT::new(0, 1)))]
+    fn check_node_count(operation1: Operation, operation2: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+        dag.add_to_back(operation1.clone());
+        dag.add_to_front(operation2.clone());
+
+        assert!(dag.graph.node_count() == 2);
+
+        dag.add_to_back(operation1.clone());
+
+        assert!(dag.graph.node_count() == 3);
+    }
+
+    #[test_case(Operation::from(PauliX::new(0)), Operation::from(PauliY::new(0)))]
+    #[test_case(
+        Operation::from(PauliX::new(0)),
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None,))
+    )]
+    #[test_case(
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None,)),
+        Operation::from(PauliX::new(0))
+    )]
+    #[test_case(
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None,)),
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None,))
+    )]
+    fn check_edge(operation1: Operation, operation2: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+        dag.add_to_back(Operation::from(DefinitionBit::new(
+            "ro".to_string(),
+            4,
+            false,
+        )));
+
+        let ind1 = dag.add_to_back(operation1.clone());
+        let ind2 = dag.add_to_back(operation2.clone());
+
+        assert!(dag
+            .graph
+            .contains_edge(ind1.unwrap().into(), ind2.unwrap().into()));
+    }
+
+    #[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None)))]
+    #[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ri"), 2, None)))]
+    fn check_first_last_all_existence(operation: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+        assert!(dag.first_all.is_none());
+        assert!(dag.last_all.is_none());
+
+        let ind_back = dag.add_to_back(operation.clone());
+        let ind_front = dag.add_to_front(operation.clone());
+
+        assert!(dag.first_all.is_some());
+        assert!(dag.last_all.is_some());
+
+        assert!(dag.first_all.unwrap() == ind_front.unwrap());
+        assert!(dag.last_all.unwrap() == ind_back.unwrap());
+    }
+
+    #[test_case(
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None)),
+        Operation::from(PragmaRepeatedMeasurement::new(String::from("ri"), 2, None))
+    )]
+    fn check_first_last_all_order(operation1: Operation, operation2: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+        dag.add_to_back(operation1);
+        dag.add_to_front(operation2);
+
+        assert!(dag.first_all.is_some());
+        assert!(dag.last_all.is_some());
+
+        assert_ne!(
+            dag.graph.node_weight(dag.first_all.unwrap().into()),
+            dag.graph.node_weight(dag.last_all.unwrap().into())
+        );
+    }
+
+    #[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None,)))]
+    #[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ri"), 2, None,)))]
+    fn check_operation_involving_qubits_all(operation: Operation) {
+        let mut dag: CircuitDag =
+            CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+        assert!(dag.first_operation_involving_qubit().is_empty());
+        assert!(dag.last_operation_involving_qubit().is_empty());
+
+        dag.add_to_front(operation.clone());
+
+        let back = dag.add_to_back(Operation::from(PauliX::new(0)));
+
+        assert_eq!(dag.last_operation_involving_qubit().get(&0), back.as_ref());
+
+        let front = dag.add_to_front(Operation::from(CNOT::new(0, 1)));
+
+        assert_eq!(dag.last_operation_involving_qubit().get(&0), back.as_ref());
+        assert_eq!(
+            dag.first_operation_involving_qubit().get(&0),
+            front.as_ref()
+        );
+
+        assert_ne!(dag.last_operation_involving_qubit().get(&0), front.as_ref());
+        assert_ne!(dag.first_operation_involving_qubit().get(&0), back.as_ref());
+
+        let new_front_all = dag.add_to_front(operation.clone());
+        let new_back_all = dag.add_to_back(operation.clone());
+
+        assert!(dag
+            .graph
+            .contains_edge(new_front_all.unwrap().into(), front.unwrap().into()));
+        assert!(dag
+            .graph
+            .contains_edge(back.unwrap().into(), new_back_all.unwrap().into()));
+    }
+
+    #[test_case(vec![Operation::from(CNOT::new(0,1)), Operation::from(PauliX::new(0)), Operation::from(PauliY::new(1))])]
+    #[test_case(vec![Operation::from(PauliZ::new(0)), Operation::from(ControlledPauliZ::new(1,2))])]
+    fn test_new_from_circuit(op_vec: Vec<Operation>) {
+        let mut circuit: Circuit = Circuit::new();
+        for op in &op_vec {
+            circuit.add_operation((*op).clone());
+        }
+
+        let dag: CircuitDag = CircuitDag::from(circuit);
+
+        assert!(!dag.first_operation_involving_qubit().is_empty());
+        assert!(!dag.last_operation_involving_qubit().is_empty());
+
+        assert_eq!(dag.graph.node_count(), op_vec.len());
+    }
+}
diff --git a/roqoqo/src/lib.rs b/roqoqo/src/lib.rs
index cc59f38c..da18dd1e 100644
--- a/roqoqo/src/lib.rs
+++ b/roqoqo/src/lib.rs
@@ -303,6 +303,8 @@ mod circuit;
 pub use circuit::Circuit;
 #[doc(hidden)]
 pub use circuit::*;
+mod circuitdag;
+pub use circuitdag::CircuitDag;
 pub mod backends;
 pub mod devices;
 pub mod measurements;


Test patch:
diff --git a/roqoqo/tests/integration/circuitdag.rs b/roqoqo/tests/integration/circuitdag.rs
new file mode 100644
index 00000000..799642c8
--- /dev/null
+++ b/roqoqo/tests/integration/circuitdag.rs
@@ -0,0 +1,335 @@
+// Copyright © 2021 HQS Quantum Simulations GmbH. All Rights Reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
+// in compliance with the License. You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software distributed under the
+// License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
+// express or implied. See the License for the specific language governing permissions and
+// limitations under the License.
+
+use std::collections::HashSet;
+
+use roqoqo::operations::*;
+use roqoqo::{Circuit, CircuitDag};
+
+use test_case::test_case;
+
+static DEFAULT_NODE_NUMBER: usize = 10;
+static DEFAULT_EDGE_NUMBER: usize = 30;
+
+/// Test adding an operation that doesn't involve qubits.
+///
+#[test_case(
+    Operation::from(PragmaSetNumberOfMeasurements::new(3, "ro".to_string())),
+    Operation::from(PragmaSetNumberOfMeasurements::new(5, "ti".to_string()))
+)]
+#[test_case(
+    Operation::from(PragmaSetNumberOfMeasurements::new(4, "ri".to_string())),
+    Operation::from(PragmaSetNumberOfMeasurements::new(1, "to".to_string()))
+)]
+fn add_operation_no_involved_qubits(operation1: Operation, operation2: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    let back1 = dag.add_to_back(operation1.clone());
+
+    assert!(operation1.involved_qubits() == InvolvedQubits::None);
+    assert_eq!(dag.commuting_operations().get(0), back1.as_ref());
+
+    dag.add_to_front(Operation::from(PauliY::new(0)));
+    dag.add_to_back(Operation::from(CNOT::new(0, 1)));
+
+    let front1 = dag.add_to_front(operation2.clone());
+
+    assert_eq!(dag.commuting_operations().get(1), front1.as_ref());
+}
+
+#[test_case(Operation::from(PauliX::new(0)), Operation::from(PauliY::new(1)))]
+#[test_case(Operation::from(PauliY::new(1)), Operation::from(PauliZ::new(2)))]
+#[test_case(Operation::from(CNOT::new(0, 1)), Operation::from(PauliX::new(1)))]
+fn check_parallel_blocks_set(operation1: Operation, operation2: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+    let mut inv_qubits_1: HashSet<usize> = HashSet::new();
+    if let InvolvedQubits::Set(x) = operation1.involved_qubits() {
+        for qubit in x {
+            inv_qubits_1.insert(qubit);
+        }
+    }
+
+    dag.add_to_back(operation1.clone());
+
+    assert!(dag.last_parallel_block().len() == 1);
+    assert!(dag.last_parallel_block().len() == 1);
+
+    dag.add_to_front(operation2.clone());
+    dag.add_to_back(operation1.clone());
+
+    if inv_qubits_1.len() == 2 {
+        assert!(dag.last_parallel_block().len() == 1);
+    } else {
+        assert!(dag.last_parallel_block().len() == 2);
+    }
+}
+
+#[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ro"), 1, None)))]
+#[test_case(Operation::from(PragmaRepeatedMeasurement::new(String::from("ri"), 2, None)))]
+fn check_parallel_blocks_all(operation: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    assert!(dag.last_parallel_block().len() == 0);
+    assert!(dag.first_parallel_block().len() == 0);
+
+    dag.add_to_back(operation.clone());
+
+    assert!(dag.first_parallel_block().len() == 1);
+    assert!(dag.last_parallel_block().len() == 1);
+
+    dag.add_to_front(operation.clone());
+
+    assert!(dag.first_parallel_block().len() == 1);
+    assert!(dag.last_parallel_block().len() == 1);
+}
+
+#[test_case(Operation::from(PauliX::new(0)), Operation::from(PauliY::new(1)))]
+#[test_case(Operation::from(PauliY::new(1)), Operation::from(PauliZ::new(2)))]
+#[test_case(Operation::from(PauliX::new(0)), Operation::from(PauliX::new(2)))]
+fn check_parallel_blocks_mixed(operation1: Operation, operation2: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    dag.add_to_front(operation1);
+
+    assert!(dag.first_parallel_block().len() == 1);
+    assert!(dag.last_parallel_block().len() == 1);
+
+    dag.add_to_back(Operation::from(PragmaRepeatedMeasurement::new(
+        String::from("ro"),
+        1,
+        None,
+    )));
+    dag.add_to_front(operation2);
+
+    assert!(dag.last_parallel_block().len() == 1);
+    assert!(dag.first_parallel_block().len() == 2);
+}
+
+#[test_case(Operation::from(PauliX::new(0)))]
+#[test_case(Operation::from(CNOT::new(0, 1)))]
+fn check_operation_involving_qubits_set(operation: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    dag.add_to_front(Operation::from(PauliZ::new(0)));
+    dag.add_to_back(Operation::from(CNOT::new(0, 1)));
+
+    assert!(
+        dag.last_operation_involving_qubit().get(&0)
+            == dag.last_operation_involving_qubit().get(&1)
+    );
+
+    let ind = dag.add_to_back(operation.clone());
+
+    if let InvolvedQubits::Set(qubits) = operation.involved_qubits() {
+        for qubit in qubits {
+            assert!(dag.last_operation_involving_qubit().contains_key(&qubit));
+            assert!(dag.last_operation_involving_qubit().get(&qubit) == ind.as_ref());
+        }
+    }
+}
+
+#[test_case(Operation::from(CNOT::new(0, 1)))]
+#[test_case(Operation::from(PauliX::new(0)))]
+fn check_involved_classical_none(operation: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    assert!(dag.first_operation_involving_classical().is_empty());
+    assert!(dag.last_operation_involving_classical().is_empty());
+
+    dag.add_to_back(operation.clone());
+
+    assert!(dag.first_operation_involving_classical().is_empty());
+    assert!(dag.last_operation_involving_classical().is_empty());
+}
+
+#[test_case(Operation::from(MeasureQubit::new(0, "ro".to_string(), 0)), Operation::from(MeasureQubit::new(1, "ro".to_string(), 1)))]
+#[test_case(Operation::from(MeasureQubit::new(1, "ro".to_string(), 1)), Operation::from(MeasureQubit::new(2, "ro".to_string(), 2)))]
+fn check_involved_classical_set(operation1: Operation, operation2: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    let back = dag.add_to_back(operation1.clone());
+
+    if let InvolvedClassical::Set(x) = operation1.involved_classical() {
+        let el = x.iter().next().unwrap();
+        assert!(dag.last_operation_involving_classical().contains_key(el));
+        assert_eq!(
+            dag.last_operation_involving_classical().get(el),
+            back.as_ref()
+        );
+    }
+
+    assert!(!dag.last_operation_involving_classical().is_empty());
+    assert!(!dag.first_operation_involving_classical().is_empty());
+
+    let front = dag.add_to_front(operation2.clone());
+
+    if let InvolvedClassical::Set(x) = operation2.involved_classical() {
+        let el = x.iter().next().unwrap();
+        assert!(dag.first_operation_involving_classical().contains_key(el));
+        assert_eq!(
+            dag.first_operation_involving_classical().get(el),
+            front.as_ref()
+        );
+    }
+
+    let front2 = dag.add_to_front(operation2.clone());
+
+    if let InvolvedClassical::Set(x) = operation2.involved_classical() {
+        let el = x.iter().next().unwrap();
+        assert_ne!(
+            dag.first_operation_involving_classical().get(el),
+            front.as_ref()
+        );
+        assert_eq!(
+            dag.first_operation_involving_classical().get(el),
+            front2.as_ref()
+        );
+    }
+}
+
+#[test_case(Operation::from(DefinitionComplex::new("ri".to_string(), 4, false)))]
+#[test_case(Operation::from(DefinitionBit::new("ri".to_string(), 4, false)))]
+fn test_is_definition_classical_populate(operation: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    let node = dag.add_to_back(operation.clone());
+
+    assert!(!dag.first_operation_involving_classical().is_empty());
+    assert!(!dag.last_operation_involving_classical().is_empty());
+
+    assert!(dag
+        .first_operation_involving_classical()
+        .contains_key(&("ri".to_string(), 0)));
+    assert!(dag
+        .first_operation_involving_classical()
+        .contains_key(&("ri".to_string(), 1)));
+    assert!(dag
+        .first_operation_involving_classical()
+        .contains_key(&("ri".to_string(), 2)));
+
+    for i in 0..4 {
+        assert!(dag
+            .first_operation_involving_classical()
+            .contains_key(&("ri".to_string(), i)));
+        assert_eq!(
+            dag.first_operation_involving_classical()
+                .get(&("ri".to_string(), i)),
+            node.as_ref()
+        );
+        assert!(dag
+            .last_operation_involving_classical()
+            .contains_key(&("ri".to_string(), i)));
+        assert_eq!(
+            dag.last_operation_involving_classical()
+                .get(&("ri".to_string(), i)),
+            node.as_ref()
+        );
+    }
+}
+
+#[test_case(Operation::from(DefinitionComplex::new("ro".to_string(), 4, false)))]
+#[test_case(Operation::from(DefinitionBit::new("ri".to_string(), 3, false)))]
+fn check_involved_classical_all(operation: Operation) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+
+    let back = dag.add_to_back(Operation::from(MeasureQubit::new(0, "ro".to_string(), 0)));
+    let front = dag.add_to_front(Operation::from(MeasureQubit::new(1, "ro".to_string(), 1)));
+
+    assert_eq!(
+        dag.last_operation_involving_classical()
+            .get(&("ro".to_string(), 0)),
+        back.as_ref()
+    );
+    assert_eq!(
+        dag.last_operation_involving_classical()
+            .get(&("ro".to_string(), 0)),
+        back.as_ref()
+    );
+    assert_eq!(
+        dag.last_operation_involving_classical()
+            .get(&("ro".to_string(), 1)),
+        front.as_ref()
+    );
+    assert_eq!(
+        dag.last_operation_involving_classical()
+            .get(&("ro".to_string(), 1)),
+        front.as_ref()
+    );
+    assert_eq!(
+        dag.first_operation_involving_classical()
+            .get(&("ro".to_string(), 0)),
+        back.as_ref()
+    );
+    assert_eq!(
+        dag.first_operation_involving_classical()
+            .get(&("ro".to_string(), 0)),
+        back.as_ref()
+    );
+    assert_eq!(
+        dag.first_operation_involving_classical()
+            .get(&("ro".to_string(), 1)),
+        front.as_ref()
+    );
+    assert_eq!(
+        dag.first_operation_involving_classical()
+            .get(&("ro".to_string(), 1)),
+        front.as_ref()
+    );
+
+    let new_back = dag.add_to_back(operation.clone());
+
+    if let InvolvedClassical::All(x) = operation.involved_classical() {
+        assert_eq!(
+            dag.last_operation_involving_classical()
+                .get(&(x.clone(), 0)),
+            new_back.as_ref()
+        );
+        assert_ne!(
+            dag.last_operation_involving_classical()
+                .get(&(x.clone(), 1)),
+            back.as_ref()
+        );
+    }
+
+    let new_front = dag.add_to_front(operation.clone());
+
+    if let InvolvedClassical::All(x) = operation.involved_classical() {
+        assert_eq!(
+            dag.first_operation_involving_classical()
+                .get(&(x.clone(), 0)),
+            new_front.as_ref()
+        );
+        assert_ne!(
+            dag.first_operation_involving_classical()
+                .get(&(x.clone(), 1)),
+            front.as_ref()
+        );
+    }
+}
+
+#[test_case(vec![Operation::from(CNOT::new(0,1)), Operation::from(PauliX::new(0)), Operation::from(PauliY::new(1))])]
+#[test_case(vec![Operation::from(PauliZ::new(0)), Operation::from(ControlledPauliZ::new(1,2))])]
+fn test_pragma_conditional(op_vec: Vec<Operation>) {
+    let mut dag: CircuitDag = CircuitDag::with_capacity(DEFAULT_NODE_NUMBER, DEFAULT_EDGE_NUMBER);
+    let mut circuit: Circuit = Circuit::new();
+    for op in &op_vec {
+        circuit.add_operation((*op).clone());
+    }
+
+    let operation: Operation =
+        Operation::from(PragmaConditional::new("to".to_string(), 2, circuit));
+
+    dag.add_to_back(operation.clone());
+
+    assert!(!dag.first_operation_involving_qubit().is_empty());
+    assert!(!dag.last_operation_involving_qubit().is_empty());
+}
diff --git a/roqoqo/tests/integration/main.rs b/roqoqo/tests/integration/main.rs
index a24ea120..b0d8d2da 100644
--- a/roqoqo/tests/integration/main.rs
+++ b/roqoqo/tests/integration/main.rs
@@ -24,3 +24,6 @@ mod devices;
 
 #[cfg(test)]
 mod quantum_program;
+
+#[cfg(test)]
+mod circuitdag;