Repository: PennyLaneAI/pennylane
Pull request #2165 (2022-02-03 16:16:25)

Convert a directed multigraph to tape
**Context:**
In the circuit cutting pipeline, once we have the subgraphs corresponding to the circuit [fragments](https://github.com/PennyLaneAI/pennylane/pull/2153) we must then to convert these to tapes in order to execute them.

**Description of the Change:**
A method for converting directed multigraphs to tapes has been added.

**Benefits:**
Facilitates circuit cutting.


github-actions[bot]: Hello. You may have forgotten to update the changelog!
Please edit [`doc/releases/changelog-dev.md`](/PennyLaneAI/pennylane/blob/master/doc/releases/changelog-dev.md) with:
* A one-to-two sentence description of the change. You may include a small working example for new features.
* A link back to this PR.
* Your name (or GitHub username) in the contributors section.
codecov[bot]: # [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#2165](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (ed15a26) into [sc-14127-a-user-can-fragment-a-circuit-graph-into](https://codecov.io/gh/PennyLaneAI/pennylane/commit/8495fff14929104c09bf31b9ad09a80a1f95795e?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (8495fff) will **increase** coverage by `5.00%`.
> The diff coverage is `100.00%`.

[![Impacted file tree graph](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/graphs/tree.svg?width=650&height=150&src=pr&token=9S3YzlUgGk&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)

```diff
@@                                  Coverage Diff                                  @@
##           sc-14127-a-user-can-fragment-a-circuit-graph-into    #2165      +/-   ##
=====================================================================================
+ Coverage                                              91.40%   96.41%   +5.00%     
=====================================================================================
  Files                                                    231      231              
  Lines                                                  17753    17829      +76     
=====================================================================================
+ Hits                                                   16228    17189     +961     
+ Misses                                                  1525      640     -885     
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/transforms/qcut.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvcWN1dC5weQ==) | `100.00% <100.00%> (ø)` | |
| [pennylane/vqe/vqe.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3ZxZS92cWUucHk=) | `100.00% <0.00%> (ø)` | |
| [pennylane/drawer/tape\_mpl.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2RyYXdlci90YXBlX21wbC5weQ==) | `100.00% <0.00%> (ø)` | |
| [pennylane/transforms/control.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvY29udHJvbC5weQ==) | `100.00% <0.00%> (ø)` | |
| [pennylane/ops/qubit/attributes.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL29wcy9xdWJpdC9hdHRyaWJ1dGVzLnB5) | `100.00% <0.00%> (ø)` | |
| [pennylane/optimize/shot\_adaptive.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL29wdGltaXplL3Nob3RfYWRhcHRpdmUucHk=) | `100.00% <0.00%> (ø)` | |
| [pennylane/gradients/parameter\_shift.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2dyYWRpZW50cy9wYXJhbWV0ZXJfc2hpZnQucHk=) | `100.00% <0.00%> (ø)` | |
| [pennylane/drawer/representation\_resolver.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2RyYXdlci9yZXByZXNlbnRhdGlvbl9yZXNvbHZlci5weQ==) | `99.43% <0.00%> (+<0.01%)` | :arrow_up: |
| [pennylane/\_qubit\_device.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL19xdWJpdF9kZXZpY2UucHk=) | `98.39% <0.00%> (+0.01%)` | :arrow_up: |
| [pennylane/queuing.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3F1ZXVpbmcucHk=) | `98.83% <0.00%> (+0.01%)` | :arrow_up: |
| ... and [36 more](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Last update [8495fff...ed15a26](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2165?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).


Patch:
diff --git a/doc/releases/changelog-dev.md b/doc/releases/changelog-dev.md
index d9a4f6a7d..3c3926b94 100644
--- a/doc/releases/changelog-dev.md
+++ b/doc/releases/changelog-dev.md
@@ -47,6 +47,10 @@
   `PrepareNode` placeholders and fragments into subgraphs and a communication graph.
   [(#2153)](https://github.com/PennyLaneAI/pennylane/pull/2153)
 
+  A method has been added that takes a directed multigraph with `MeasureNode`
+  and `PrepareNode` placeholder nodes and converts it into a tape.
+  [(#2165)](https://github.com/PennyLaneAI/pennylane/pull/2165)
+
   A differentiable tensor contraction function `contract_tensors` has been
   added.
   [(#2158)](https://github.com/PennyLaneAI/pennylane/pull/2158)
diff --git a/pennylane/transforms/__init__.py b/pennylane/transforms/__init__.py
index 77a52bdcd..07493811c 100644
--- a/pennylane/transforms/__init__.py
+++ b/pennylane/transforms/__init__.py
@@ -94,6 +94,7 @@ The following are utility functions that compose the circuit cutting transform.
     ~transforms.replace_wire_cut_node
     ~transforms.replace_wire_cut_nodes
     ~transforms.fragment_graph
+    ~transforms.graph_to_tape
     ~transforms.contract_tensors
 
 Transforms that act on tapes
@@ -172,5 +173,6 @@ from .qcut import (
     replace_wire_cut_node,
     replace_wire_cut_nodes,
     fragment_graph,
+    graph_to_tape,
     contract_tensors,
 )
diff --git a/pennylane/transforms/qcut.py b/pennylane/transforms/qcut.py
index 762caac79..7c85fbf85 100644
--- a/pennylane/transforms/qcut.py
+++ b/pennylane/transforms/qcut.py
@@ -15,16 +15,20 @@
 This module provides the circuit cutting functionality that allows large
 circuits to be distributed across multiple devices.
 """
+
+import copy
 import string
 from typing import Sequence, Tuple
 
 from networkx import MultiDiGraph, weakly_connected_components
 
 import pennylane as qml
+from pennylane import apply
 from pennylane.measure import MeasurementProcess
 from pennylane.operation import Operation, Operator, Tensor
 from pennylane.ops.qubit.non_parametric_ops import WireCut
 from pennylane.tape import QuantumTape
+from pennylane.wires import Wires
 
 
 class MeasureNode(Operation):
@@ -287,6 +291,79 @@ def fragment_graph(graph: MultiDiGraph) -> Tuple[Tuple[MultiDiGraph], MultiDiGra
     return subgraphs, communication_graph
 
 
+def _find_new_wire(wires: Wires) -> int:
+    """Finds a new wire label that is not in ``wires``."""
+    ctr = 0
+    while ctr in wires:
+        ctr += 1
+    return ctr
+
+
+# pylint: disable=protected-access
+def graph_to_tape(graph: MultiDiGraph) -> QuantumTape:
+    """
+    Converts a directed multigraph to the corresponding :class:`~.QuantumTape`.
+
+    Each node in the graph should have an order attribute specifying the topological order of
+    the operations.
+
+    .. note::
+
+        This function is designed for use as part of the circuit cutting workflow.
+        Check out the :doc:`transforms </code/qml_transforms>` page for more details.
+
+    Args:
+        graph (MultiDiGraph): directed multigraph to be converted to a tape
+
+    Returns:
+        QuantumTape: the quantum tape corresponding to the input graph
+
+    **Example**
+
+    Consider the following, where ``graph`` contains :class:`~.MeasureNode` and
+    :class:`~.PrepareNode` pairs that divide the full circuit graph into five subgraphs.
+    We can find the circuit fragments by using:
+
+    .. code-block:: python
+
+        >>> subgraphs, communication_graph = qml.transforms.fragment_graph(graph)
+        >>> tapes = [qml.transforms.graph_to_tape(sg) for sg in subgraphs]
+        >>> tapes
+        [<QuantumTape: wires=[0], params=1>, <QuantumTape: wires=[0, 1], params=1>,
+         <QuantumTape: wires=[1], params=1>, <QuantumTape: wires=[0], params=0>,
+         <QuantumTape: wires=[1], params=0>]
+    """
+
+    wires = Wires.all_wires([n.wires for n in graph.nodes])
+
+    ordered_ops = sorted(
+        [(order, op) for op, order in graph.nodes(data="order")], key=lambda x: x[0]
+    )
+    wire_map = {w: w for w in wires}
+    reverse_wire_map = {v: k for k, v in wire_map.items()}
+
+    copy_ops = [copy.copy(op) for _, op in ordered_ops]
+
+    with QuantumTape() as tape:
+        for op in copy_ops:
+            new_wires = [wire_map[w] for w in op.wires]
+            op._wires = Wires(new_wires)  # TODO: find a better way to update operation wires
+            apply(op)
+
+            if isinstance(op, MeasureNode):
+                assert len(op.wires) == 1
+                measured_wire = op.wires[0]
+
+                new_wire = _find_new_wire(wires)
+                wires += new_wire
+
+                original_wire = reverse_wire_map[measured_wire]
+                wire_map[original_wire] = new_wire
+                reverse_wire_map[new_wire] = original_wire
+
+    return tape
+
+
 def _get_symbol(i):
     """Finds the i-th ASCII symbol. Works for lowercase and uppercase letters, allowing i up to
     51."""


Test patch:
diff --git a/tests/transforms/test_qcut.py b/tests/transforms/test_qcut.py
index 1ee529f7d..1d3a9222b 100644
--- a/tests/transforms/test_qcut.py
+++ b/tests/transforms/test_qcut.py
@@ -14,6 +14,7 @@
 """
 Unit tests for the `pennylane.qcut` package.
 """
+import copy
 import string
 import sys
 
@@ -23,6 +24,7 @@ from networkx import MultiDiGraph
 import pennylane as qml
 from pennylane import numpy as np
 from pennylane.transforms import qcut
+from pennylane.wires import Wires
 
 with qml.tape.QuantumTape() as tape:
     qml.RX(0.432, wires=0)
@@ -50,6 +52,25 @@ with qml.tape.QuantumTape() as multi_cut_tape:
     qml.expval(qml.PauliZ(wires=[0]))
 
 
+# tape containing mid-circuit measurements
+with qml.tape.QuantumTape() as mcm_tape:
+    qml.Hadamard(wires=0)
+    qml.RX(0.432, wires=0)
+    qml.RY(0.543, wires=1)
+    qml.CNOT(wires=[0, 1])
+    qml.WireCut(wires=1)
+    qml.CNOT(wires=[1, 2])
+    qml.WireCut(wires=1)
+    qml.RZ(0.321, wires=1)
+    qml.CNOT(wires=[0, 1])
+    qml.Hadamard(wires=2)
+    qml.WireCut(wires=1)
+    qml.CNOT(wires=[1, 2])
+    qml.WireCut(wires=1)
+    qml.CNOT(wires=[0, 1])
+    qml.expval(qml.PauliZ(wires=[0]))
+
+
 def compare_nodes(nodes, expected_wires, expected_names):
     """Helper function to compare nodes of directed multigraph"""
 
@@ -80,6 +101,29 @@ def compare_fragment_edges(edge_data, expected_data):
         assert (data[0].name, data[1].name, data[2]) in expected
 
 
+def compare_tapes(tape, expected_tape):
+    """
+    Helper function to compare tapes
+    """
+
+    assert set(tape.wires) == set(expected_tape.wires)
+    assert tape.get_parameters() == expected_tape.get_parameters()
+
+    for op, exp_op in zip(tape.operations, expected_tape.operations):
+        if (
+            op.name == "PrepareNode"
+        ):  # The exact ordering of PrepareNodes w.r.t wires varies on each call
+            assert exp_op.name == "PrepareNode"
+        else:
+            assert op.name == exp_op.name
+            assert op.wires.tolist() == exp_op.wires.tolist()
+
+    for meas, exp_meas in zip(tape.measurements, expected_tape.measurements):
+        assert meas.return_type.name == exp_meas.return_type.name
+        assert meas.obs.name == exp_meas.obs.name
+        assert meas.wires.tolist() == exp_meas.wires.tolist()
+
+
 class TestTapeToGraph:
     """
     Tests conversion of tapes to graph representations that are amenable to
@@ -737,6 +781,161 @@ class TestFragmentGraph:
         assert communication_graph_0.edges == communication_graph_1.edges
 
 
+class TestGraphToTape:
+    """Tests that directed multigraphs are correctly converted to tapes"""
+
+    def test_graph_to_tape(self):
+        """
+        Tests that directed multigraphs, containing MeasureNodes and
+        PrepareNodes, are correctly converted to tapes
+        """
+        with qml.tape.QuantumTape() as tape:
+            qml.RX(0.432, wires=0)
+            qml.RY(0.543, wires="a")
+            qml.WireCut(wires=[0, "a"])
+            qml.CNOT(wires=[0, "a"])
+            qml.RZ(0.240, wires=0)
+            qml.RZ(0.133, wires="a")
+            qml.WireCut(wires="a")
+            qml.CNOT(wires=["a", 2])
+            qml.RX(0.432, wires="a")
+            qml.WireCut(wires=2)
+            qml.CNOT(wires=[2, 3])
+            qml.RY(0.543, wires=2)
+            qml.RZ(0.876, wires=3)
+            qml.expval(qml.PauliZ(wires=[0]))
+
+        g = qcut.tape_to_graph(tape)
+        qcut.replace_wire_cut_nodes(g)
+        subgraphs, communication_graph = qcut.fragment_graph(g)
+
+        tapes = [qcut.graph_to_tape(sg) for sg in subgraphs]
+
+        with qml.tape.QuantumTape() as tape_0:
+            qml.RX(0.432, wires=[0])
+            qcut.MeasureNode(wires=[0])
+
+        with qml.tape.QuantumTape() as tape_1:
+            qml.RY(0.543, wires=["a"])
+            qcut.MeasureNode(wires=["a"])
+
+        with qml.tape.QuantumTape() as tape_2:
+            qcut.PrepareNode(wires=[0])
+            qcut.PrepareNode(wires=["a"])
+            qml.CNOT(wires=[0, "a"])
+            qml.RZ(0.24, wires=[0])
+            qml.RZ(0.133, wires=["a"])
+            qcut.MeasureNode(wires=["a"])
+            qml.expval(qml.PauliZ(wires=[0]))
+
+        with qml.tape.QuantumTape() as tape_3:
+            qcut.PrepareNode(wires=["a"])
+            qml.CNOT(wires=["a", 2])
+            qml.RX(0.432, wires=["a"])
+            qcut.MeasureNode(wires=[2])
+
+        with qml.tape.QuantumTape() as tape_4:
+            qcut.PrepareNode(wires=[2])
+            qml.CNOT(wires=[2, 3])
+            qml.RY(0.543, wires=[2])
+            qml.RZ(0.876, wires=[3])
+
+        expected_tapes = [tape_0, tape_1, tape_2, tape_3, tape_4]
+
+        for tape, expected_tape in zip(tapes, expected_tapes):
+            compare_tapes(tape, expected_tape)
+
+    def test_mid_circuit_measurement(self):
+        """
+        Tests a circuit that is fragmented into subgraphs that
+        include mid-circuit measurements, ensuring that the
+        generated circuits apply the deferred measurement principle.
+        """
+        g = qcut.tape_to_graph(mcm_tape)
+        qcut.replace_wire_cut_nodes(g)
+        subgraphs, communication_graph = qcut.fragment_graph(g)
+
+        tapes = [qcut.graph_to_tape(sg) for sg in subgraphs]
+
+        assert tapes[0].wires == Wires([0, 1, 2, 3])
+        assert tapes[1].wires == Wires([1, 2, 0])
+
+        for tape in tapes:
+            for i, op in enumerate(tape.operations):
+                if isinstance(op, qcut.MeasureNode):
+                    try:
+                        next_op = tape.operations[i + 1]
+                        if isinstance(next_op, qcut.PrepareNode):
+                            assert op.wires != next_op.wires
+                    except IndexError:
+                        assert len(tape.operations) == i + 1
+
+    def test_mid_circuit_measurements_fragments(self):
+        """
+        Considers a circuit that is fragmented into subgraphs that
+        include mid-circuit measurements and tests that the subgraphs
+        are correctly converted to the expected tapes
+        """
+        g = qcut.tape_to_graph(mcm_tape)
+        qcut.replace_wire_cut_nodes(g)
+        subgraphs, communication_graph = qcut.fragment_graph(g)
+
+        tapes = [qcut.graph_to_tape(sg) for sg in subgraphs]
+
+        with qml.tape.QuantumTape() as tape_0:
+            qml.Hadamard(wires=[0])
+            qml.RX(0.432, wires=[0])
+            qml.RY(0.543, wires=[1])
+            qml.CNOT(wires=[0, 1])
+            qcut.MeasureNode(wires=[1])
+            qcut.PrepareNode(wires=[2])
+            qml.RZ(0.321, wires=[2])
+            qml.CNOT(wires=[0, 2])
+            qcut.MeasureNode(wires=[2])
+            qcut.PrepareNode(wires=[3])
+            qml.CNOT(wires=[0, 3])
+            qml.expval(qml.PauliZ(wires=[0]))
+
+        with qml.tape.QuantumTape() as tape_1:
+            qcut.PrepareNode(wires=[1])
+            qml.CNOT(wires=[1, 2])
+            qcut.MeasureNode(wires=[1])
+            qml.Hadamard(wires=[2])
+            qcut.PrepareNode(wires=[0])
+            qml.CNOT(wires=[0, 2])
+            qcut.MeasureNode(wires=[0])
+
+        expected_tapes = [tape_0, tape_1]
+
+        for tape, expected_tape in zip(tapes, expected_tapes):
+            compare_tapes(tape, expected_tape)
+
+    def test_multiple_conversions(self):
+        """
+        Tests that the original tape is unaffected by cutting pipeline and can
+        be used multiple times to give a consistent output.
+        """
+        # preserve original tape data for later comparison
+        copy_tape = copy.deepcopy(mcm_tape)
+
+        g1 = qcut.tape_to_graph(mcm_tape)
+        qcut.replace_wire_cut_nodes(g1)
+        subgraphs1, communication_graph1 = qcut.fragment_graph(g1)
+
+        tapes1 = [qcut.graph_to_tape(sg) for sg in subgraphs1]
+
+        g2 = qcut.tape_to_graph(mcm_tape)
+        qcut.replace_wire_cut_nodes(g2)
+        subgraphs2, communication_graph2 = qcut.fragment_graph(g2)
+
+        tapes2 = [qcut.graph_to_tape(sg) for sg in subgraphs2]
+
+        compare_tapes(copy_tape, mcm_tape)
+
+        for tape1, tape2 in zip(tapes1, tapes2):
+            compare_tapes(tape1, tape2)
+
+
 class TestContractTensors:
     """Tests for the contract_tensors function"""