Repository: PennyLaneAI/pennylane
Pull request #2107 (2022-01-18 19:20:36)

Add tape to graph conversion for circuit cutting
**Context:**
A key aspect of circuit cutting will be to allow users to request automatic cut locations, this relies on graph partitioning algorithms which requires a specific multigraph representation of circuits.

**Description of the Change:**
Add a tape-to-graph method to the `qcut.compiler`

**Benefits:**
Enables conversion of tapes to custom graph representations

**Possible Drawbacks:**
Some potential overlap with work already done for `qml.CircuitGraph` (whose representation of wires as edges is not sufficient for graph partitioning needs)

**Related GitHub Issues:**


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/2107?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
> Merging [#2107](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (f441f10) into [sc-13389-a-user-can-specify-wire-cut-locations-during](https://codecov.io/gh/PennyLaneAI/pennylane/commit/7e3f493abb429112de79b32d8d71c17a052d29c1?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) (7e3f493) will **decrease** coverage by `2.28%`.
> The diff coverage is `77.41%`.

[![Impacted file tree graph](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/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/2107?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI)

```diff
@@                                    Coverage Diff                                    @@
##           sc-13389-a-user-can-specify-wire-cut-locations-during    #2107      +/-   ##
=========================================================================================
- Coverage                                                  99.19%   96.90%   -2.29%     
=========================================================================================
  Files                                                        229      228       -1     
  Lines                                                      17539    17435     -104     
=========================================================================================
- Hits                                                       17397    16896     -501     
- Misses                                                       142      539     +397     
```


| [Impacted Files](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) | Coverage Δ | |
|---|---|---|
| [pennylane/qcut/\_\_init\_\_.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3FjdXQvX19pbml0X18ucHk=) | `100.00% <ø> (+100.00%)` | :arrow_up: |
| [pennylane/qcut/compiler.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3FjdXQvY29tcGlsZXIucHk=) | `77.41% <77.41%> (ø)` | |
| [pennylane/interfaces/batch/jax.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2ludGVyZmFjZXMvYmF0Y2gvamF4LnB5) | `0.00% <0.00%> (-100.00%)` | :arrow_down: |
| [pennylane/interfaces/jax.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2ludGVyZmFjZXMvamF4LnB5) | `0.00% <0.00%> (-97.44%)` | :arrow_down: |
| [pennylane/devices/default\_qubit\_jax.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL2RldmljZXMvZGVmYXVsdF9xdWJpdF9qYXgucHk=) | `0.00% <0.00%> (-96.63%)` | :arrow_down: |
| [pennylane/qnn/cost.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3Fubi9jb3N0LnB5) | `42.85% <0.00%> (-57.15%)` | :arrow_down: |
| [pennylane/math/multi\_dispatch.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL21hdGgvbXVsdGlfZGlzcGF0Y2gucHk=) | `76.68% <0.00%> (-23.32%)` | :arrow_down: |
| [pennylane/transforms/classical\_jacobian.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL3RyYW5zZm9ybXMvY2xhc3NpY2FsX2phY29iaWFuLnB5) | `77.08% <0.00%> (-22.92%)` | :arrow_down: |
| [pennylane/math/utils.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL21hdGgvdXRpbHMucHk=) | `81.81% <0.00%> (-18.19%)` | :arrow_down: |
| [pennylane/math/is\_independent.py](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI#diff-cGVubnlsYW5lL21hdGgvaXNfaW5kZXBlbmRlbnQucHk=) | `88.50% <0.00%> (-11.50%)` | :arrow_down: |
| ... and [18 more](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107/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/2107?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/2107?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI). Last update [7e3f493...f441f10](https://codecov.io/gh/PennyLaneAI/pennylane/pull/2107?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).

zeyueN: After having played with the dags a bit, I think it does have everything I need for auto wire cuts. One minor comment, it feels like having a dedicated dag class could make things a bit easier to work with (instead of working directly with the networkx graph whose interface is a bit awkward, especially when accessing custom attributes). 

Patch:
diff --git a/doc/releases/changelog-dev.md b/doc/releases/changelog-dev.md
index 405f61e95..57e6eec2e 100644
--- a/doc/releases/changelog-dev.md
+++ b/doc/releases/changelog-dev.md
@@ -52,6 +52,9 @@
   A `WireCut` operator has been added for manual wire cut placement
   when constructing a QNode.
   [(#2093)](https://github.com/PennyLaneAI/pennylane/pull/2093)
+  A method for converting a quantum tape to a directed multigraph that is amenable
+  to graph partitioning algorithms for circuit cutting has been added.
+  [(#2107)](https://github.com/PennyLaneAI/pennylane/pull/2107)
 
 * The `RotosolveOptimizer` has been generalized to arbitrary frequency spectra
   in the cost function. Also note the changes in behaviour listed under *Breaking
diff --git a/pennylane/transforms/qcut.py b/pennylane/transforms/qcut.py
new file mode 100644
index 000000000..561c4258b
--- /dev/null
+++ b/pennylane/transforms/qcut.py
@@ -0,0 +1,85 @@
+# Copyright 2022 Xanadu Quantum Technologies Inc.
+#
+# 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.
+"""
+This module provides the circuit cutting functionality that allows large
+circuits to be distributed across multiple devices.
+"""
+
+from networkx import MultiDiGraph
+from pennylane.measure import MeasurementProcess
+from pennylane.operation import Operator, Tensor
+from pennylane.tape import QuantumTape
+
+
+def _add_operator_node(graph: MultiDiGraph, op: Operator, order: int, wire_latest_node: dict):
+    """
+    Helper function to add operators as nodes during tape to graph conversion.
+    """
+    graph.add_node(op, order=order)
+    for wire in op.wires:
+        if wire_latest_node[wire] is not None:
+            parent_op = wire_latest_node[wire]
+            graph.add_edge(parent_op, op, wire=wire)
+        wire_latest_node[wire] = op
+
+
+def tape_to_graph(tape: QuantumTape) -> MultiDiGraph:
+    """
+    Converts a quantum tape to a directed multigraph.
+
+    Args:
+        tape (QuantumTape): tape to be converted into a directed multigraph
+
+    Returns:
+        graph (MultiDiGraph): a directed multigraph that captures the circuit
+        structure of the input tape
+
+    **Example**
+
+    Consider the following tape:
+
+    .. code-block:: python
+
+        with qml.tape.QuantumTape() as tape:
+            qml.RX(0.4, wires=0)
+            qml.RY(0.9, wires=0)
+            qml.CNOT(wires=[0, 1])
+            qml.expval(qml.PauliZ(1))
+
+    Its corresponding circuit graph can be found using
+
+    >>> tape_to_graph(tape)
+    <networkx.classes.multidigraph.MultiDiGraph at 0x7fe41cbd7210>
+    """
+    graph = MultiDiGraph()
+
+    wire_latest_node = {w: None for w in tape.wires}
+
+    for order, op in enumerate(tape.operations):
+        _add_operator_node(graph, op, order, wire_latest_node)
+
+    order += 1  # pylint: disable=undefined-loop-variable
+    for m in tape.measurements:
+        obs = getattr(m, "obs", None)
+        if obs is not None and isinstance(obs, Tensor):
+            for o in obs.obs:
+                m_ = MeasurementProcess(m.return_type, obs=o)
+
+                _add_operator_node(graph, m_, order, wire_latest_node)
+
+        else:
+            _add_operator_node(graph, m, order, wire_latest_node)
+            order += 1
+
+    return graph


Test patch:
diff --git a/tests/transforms/test_qcut.py b/tests/transforms/test_qcut.py
new file mode 100644
index 000000000..e531b73e5
--- /dev/null
+++ b/tests/transforms/test_qcut.py
@@ -0,0 +1,235 @@
+# Copyright 2022 Xanadu Quantum Technologies Inc.
+#
+# 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.
+"""
+Unit tests for the `pennylane.qcut` package.
+"""
+import numpy as np
+import pennylane as qml
+import pytest
+from pennylane.transforms import qcut
+
+with qml.tape.QuantumTape() as tape:
+    qml.RX(0.432, wires=0)
+    qml.RY(0.543, wires="a")
+    qml.CNOT(wires=[0, "a"])
+    qml.CRZ(0.5, wires=["a", 0])
+    qml.RZ(0.240, wires=0)
+    qml.RZ(0.133, wires="a")
+    qml.expval(qml.PauliZ(wires=[0]))
+
+
+class TestTapeToGraph:
+    """
+    Tests conversion of tapes to graph representations that are amenable to
+    partitioning algorithms for circuit cutting
+    """
+
+    def test_converted_graph_nodes(self):
+        """
+        Tests that the conversion of a tape gives a graph containing the
+        expected nodes
+        """
+
+        g = qcut.tape_to_graph(tape)
+        nodes = list(g.nodes)
+
+        ops = tape.operations
+
+        assert len(nodes) == len(ops) + len(tape.observables)
+        for op, node in zip(ops, nodes[:-1]):
+            assert op == node
+        assert tape.observables[0] == nodes[-1].obs
+
+    def test_converted_graph_edges(self):
+        """
+        Tests that the conversion of a tape gives a graph containing the
+        expected edges
+        """
+        g = qcut.tape_to_graph(tape)
+        edges = list(g.edges)
+
+        num_wires_connecting_gates = 7
+        assert len(edges) == num_wires_connecting_gates
+
+        ops = tape.operations
+
+        expected_edge_connections = [
+            (ops[0], ops[2], 0),
+            (ops[1], ops[2], 0),
+            (ops[2], ops[3], 0),
+            (ops[2], ops[3], 1),
+            (ops[3], ops[4], 0),
+            (ops[3], ops[5], 0),
+            (ops[4], tape.measurements[0], 0),
+        ]
+
+        for edge, expected_edge in zip(edges, expected_edge_connections):
+            assert edge == expected_edge
+
+    def test_node_order_attribute(self):
+        """
+        Tests that the converted nodes contain the correct order attribute
+        """
+
+        g = qcut.tape_to_graph(tape)
+        node_data = list(g.nodes(data=True))
+
+        expected_node_order = [
+            {"order": 0},
+            {"order": 1},
+            {"order": 2},
+            {"order": 3},
+            {"order": 4},
+            {"order": 5},
+        ]
+
+        for data, expected_order in zip(node_data, expected_node_order):
+            assert data[-1] == expected_order
+
+    def test_edge_wire_attribute(self):
+        """
+        Tests that the converted edges contain the correct wire attribute
+        """
+
+        g = qcut.tape_to_graph(tape)
+        edge_data = list(g.edges(data=True))
+
+        expected_edge_wires = [
+            {"wire": 0},
+            {"wire": "a"},
+            {"wire": "a"},
+            {"wire": 0},
+            {"wire": 0},
+            {"wire": "a"},
+            {"wire": 0},
+        ]
+
+        for data, expected_wire in zip(edge_data, expected_edge_wires):
+            assert data[-1] == expected_wire
+
+    @pytest.mark.parametrize(
+        "obs,expected_obs",
+        [
+            (
+                qml.PauliZ(0) @ qml.PauliZ(2),
+                [qml.expval(qml.PauliZ(wires=[0])), qml.expval(qml.PauliZ(wires=[2]))],
+            ),
+            (
+                qml.Projector([0, 1], wires=[0, 1]),
+                [qml.expval(qml.Projector([0, 1], wires=[0, 1]))],
+            ),
+            (
+                qml.Hamiltonian([1, 2], [qml.PauliZ(1), qml.PauliZ(2) @ qml.PauliX(0)]),
+                [
+                    qml.expval(
+                        qml.Hamiltonian([1, 2], [qml.PauliZ(1), qml.PauliZ(2) @ qml.PauliX(0)])
+                    )
+                ],
+            ),
+            (
+                qml.Hermitian(np.array([[1, 0], [0, -1]]), wires=[0]),
+                [qml.expval(qml.Hermitian(np.array([[1, 0], [0, -1]]), wires=[0]))],
+            ),
+            (
+                qml.Projector([0, 1], wires=[0, 1]) @ qml.Projector([1, 0], wires=[0, 2]),
+                [
+                    qml.expval(qml.Projector([0, 1], wires=[0, 1])),
+                    qml.expval(qml.Projector([1, 0], wires=[0, 2])),
+                ],
+            ),
+        ],
+    )
+    def test_observable_conversion(self, obs, expected_obs):
+        """
+        Tests that a variety of observables in a tape are correctly converted to
+        observables contained within the graph nodes
+        """
+
+        with qml.tape.QuantumTape() as tape:
+            qml.RX(0.432, wires=0)
+            qml.RY(0.543, wires=2)
+            qml.CNOT(wires=[0, 1])
+            qml.RZ(0.240, wires=0)
+            qml.RZ(0.133, wires=1)
+            qml.expval(obs)
+
+        g = qcut.tape_to_graph(tape)
+        nodes = list(g.nodes)
+
+        node_observables = [node for node in nodes if hasattr(node, "return_type")]
+
+        for node_obs, exp_obs in zip(node_observables, expected_obs):
+            assert node_obs.wires == exp_obs.wires
+            assert node_obs.obs.name == exp_obs.obs.name
+
+    @pytest.mark.parametrize(
+        "measurement,expected_measurement",
+        [
+            (qml.expval(qml.PauliZ(wires=[0])), "Expectation"),
+            (qml.sample(qml.PauliZ(wires=[0])), "Sample"),
+            (qml.var(qml.PauliZ(wires=[0])), "Variance"),
+            (qml.probs(wires=0), "Probability"),
+            (qml.state(), "State"),
+            (qml.density_matrix([0]), "State"),
+        ],
+    )
+    def test_measurement_conversion(self, measurement, expected_measurement):
+        """
+        Tests that measurements are correctly converted
+        """
+
+        with qml.tape.QuantumTape() as tape:
+            qml.RX(0.432, wires=0)
+            qml.RY(0.543, wires=2)
+            qml.CNOT(wires=[0, 1])
+            qml.RZ(0.240, wires=0)
+            qml.RZ(0.133, wires=1)
+            qml.apply(measurement)
+
+        g = qcut.tape_to_graph(tape)
+        nodes = list(g.nodes)
+
+        node_observables = [node for node in nodes if hasattr(node, "return_type")]
+
+        assert node_observables[0].return_type.name == expected_measurement
+
+    def test_multiple_observables(self):
+        """
+        Tests that a tape containing multiple measurements is correctly
+        converted to a graph
+        """
+
+        with qml.tape.QuantumTape() as tape:
+            qml.RX(0.432, wires=0)
+            qml.RY(0.543, wires=2)
+            qml.CNOT(wires=[0, 1])
+            qml.RZ(0.240, wires=0)
+            qml.RZ(0.133, wires=1)
+            qml.expval(qml.PauliZ(wires=[0]))
+            qml.expval(qml.PauliX(wires=[1]) @ qml.PauliY(wires=[2]))
+
+        expected_obs = [
+            qml.expval(qml.PauliZ(wires=[0])),
+            qml.expval(qml.PauliX(wires=[1])),
+            qml.expval(qml.PauliY(wires=[2])),
+        ]
+
+        g = qcut.tape_to_graph(tape)
+        nodes = list(g.nodes)
+
+        node_observables = [node for node in nodes if hasattr(node, "return_type")]
+
+        for node_obs, exp_obs in zip(node_observables, expected_obs):
+            assert node_obs.wires == exp_obs.wires
+            assert node_obs.obs.name == exp_obs.obs.name