Repository: PennyLaneAI/pennylane
Pull request #7111 (2025-03-18 21:19:41)

[FTQC] Improve robustness of GraphStatePrep wire mapping
**Context:** The order of the nodes in a graph is not well defined since the graph structures used for defining qubit connectivity are inherently *unordered* data structures. Mapping the nodes in the graph to the *ordered* sequence of wires can therefore result in ambiguity. This is especially troublesome given that NetworkX uses Python `dict` objects to store a graph's adjacency list. Python `dict` objects are insertion-ordered ([since Python 3.7](https://docs.python.org/3/whatsnew/3.7.html#summary-release-highlights)), therefore it's possible to define the same graph structure with different internal node ordering, depending on the order in which the nodes were inserted into the graph.

`GraphStatePrep` requires a robust, deterministic method to map node labels to wire indices that do not depend on such things as the node-insertion order into the graph.

**Description of the Change:** To ensure this mapping is reliable and deterministic, the sequence of wires is mapped to the list of graph nodes *sorted in ascending order*. Additional tests and documentation explaining node ordering have also been added.

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://app.codecov.io/gh/PennyLaneAI/pennylane/pull/7111?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 99.60%. Comparing base [(`9c36698`)](https://app.codecov.io/gh/PennyLaneAI/pennylane/commit/9c36698c887e30abbbb0e73ec9187f9c1a397107?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI) to head [(`cda1aa9`)](https://app.codecov.io/gh/PennyLaneAI/pennylane/commit/cda1aa959ed8b01a5e9b8a5642ea15a6d29ff420?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).

<details><summary>Additional details and impacted files</summary>


```diff
@@           Coverage Diff           @@
##           master    #7111   +/-   ##
=======================================
  Coverage   99.60%   99.60%           
=======================================
  Files         496      496           
  Lines       47341    47340    -1     
=======================================
- Hits        47154    47153    -1     
  Misses        187      187           
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/PennyLaneAI/pennylane/pull/7111?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=PennyLaneAI).

<details><summary>🚀 New features to boost your workflow: </summary>

- ❄ [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
</details>

Patch:
diff --git a/pennylane/ftqc/graph_state_preparation.py b/pennylane/ftqc/graph_state_preparation.py
index 3e7a72777..19a9eb29d 100644
--- a/pennylane/ftqc/graph_state_preparation.py
+++ b/pennylane/ftqc/graph_state_preparation.py
@@ -47,11 +47,15 @@ class GraphStatePrep(Operation):
         (:class:`~.pennylane.CZ` gate) operation.
 
     Args:
-        graph (Union[QubitGraph, networkx.Graph]): QubitGraph or networkx.Graph object mapping qubit to wires.
-        one_qubit_ops (Operation): Operator to prepare the initial state of each qubit. Default to :class:`~.pennylane.H`.
-        two_qubit_ops (Operation): Operator to entangle nearest qubits. Default to :class:`~.pennylane.CZ`.
-        wires (Optional[Wires]): Wires the operator applies on. Wires will be mapped 1:1 to graph nodes. Optional only `graph`
-          is a QubitGraph. If no wires are provided, the ``children`` of the provided ``QubitGraph`` will be used as wires.
+        graph (Union[QubitGraph, networkx.Graph]): QubitGraph or networkx.Graph object mapping qubit
+            to wires. The node labels of ``graph`` must be sortable.
+        one_qubit_ops (Operation): Operator to prepare the initial state of each qubit. Defaults to
+            :class:`~.pennylane.Hadamard`.
+        two_qubit_ops (Operation): Operator to entangle nearest qubits. Defaults to
+            :class:`~.pennylane.CZ`.
+        wires (Optional[Wires]): Wires the operator applies on. Wires are be mapped 1:1 to the graph
+            nodes sorted in ascending order. Optional only `graph` is a QubitGraph. If no wires are
+            provided, the ``children`` of the provided ``QubitGraph`` will be used as wires.
 
     .. todo::
 
@@ -99,6 +103,72 @@ class GraphStatePrep(Operation):
         2: ──Y─╰X────│──╭●─┤  Probs
         3: ──Y───────╰X─╰X─┤  Probs
 
+    .. details::
+        :title: A Note on Node Ordering
+
+        The graph structures used for defining qubit connectivity are inherently *unordered* data
+        structures. Mapping the nodes in the graph to the *ordered* sequence of wires can therefore
+        result in ambiguity. To ensure this mapping is reliable and deterministic, the sequence of
+        wires is mapped to the list of graph nodes sorted in ascending order.
+
+        Consider the following example:
+
+        .. code-block:: python3
+
+            import networkx as nx
+            import pennylane as qml
+            from pennylane.ftqc import GraphStatePrep
+
+            dev = qml.device("default.qubit")
+
+            @qml.qnode(dev)
+            def circuit(graph, wires):
+                GraphStatePrep(graph=graph, one_qubit_ops=qml.H, two_qubit_ops=qml.CZ, wires=wires)
+                return qml.state()
+
+        Defining a graph structure and drawing the circuit shows how the graph node labels have been
+        mapped to wires:
+
+        >>> g1 = nx.Graph([("a", "b"), ("b", "c"), ("c", "d")])  # (a) -- (b) -- (c) -- (d)
+        >>> print(qml.draw(circuit, level="device")(g1, wires=range(4)))
+        0: ──H─╭●───────┤  State
+        1: ──H─╰Z─╭●────┤  State
+        2: ──H────╰Z─╭●─┤  State
+        3: ──H───────╰Z─┤  State
+
+        In other words, ``GraphStatePrep`` has defined the node-label-to-wire mapping::
+
+            {"a": 0, "b": 1, "c": 2, "d": 3}
+
+        which corresponds to the graph structure with wire indices::
+
+            (0) -- (1) -- (2) -- (3)
+
+        as shown in the circuit diagram with ``CZ`` operations applied along each edge in the graph.
+
+        Drawing the circuit for a graph with the same structure but with different node labels
+        gives:
+
+        >>> g2 = nx.Graph([("b", "a"), ("a", "c"), ("c", "d")])  # (b) -- (a) -- (c) -- (d)
+        >>> print(qml.draw(circuit, level="device")(g2, wires=range(4)))
+        0: ──H─╭Z─╭●────┤  State
+        1: ──H─╰●─│─────┤  State
+        2: ──H────╰Z─╭●─┤  State
+        3: ──H───────╰Z─┤  State
+
+        As before, ``GraphStatePrep`` defined the node-label-to-wire mapping to be::
+
+            {"a": 0, "b": 1, "c": 2, "d": 3}
+
+        but now, this corresponds to the graph structure with wire indices::
+
+            (1) -- (0) -- (2) -- (3)
+
+        as shown in the circuit diagram.
+
+        While these two circuit might appear to be the same, they are indeed distinct for this
+        sequence of wires, and result in different state vectors. It is therefore important to
+        remember that the node labels influence how nearest-neighbour wires are interpreted.
     """
 
     def __init__(
@@ -171,12 +241,21 @@ class GraphStatePrep(Operation):
 
         op_list = []
 
-        edges = graph.edge_labels if isinstance(graph, QubitGraph) else graph.edges
         nodes = graph.node_labels if isinstance(graph, QubitGraph) else graph.nodes
+        try:
+            sorted_nodes = sorted(nodes)
+        except TypeError as e:
+            # Attempting to sort a list with a mix of incompatible types results in a TypeError:
+            # >>> sorted([0, 'a'])
+            # TypeError: '<' not supported between instances of 'str' and 'int'
+            raise TypeError(
+                "GraphStatePrep requires the node labels of the input graph to be sortable"
+            ) from e
+
+        wire_map = dict(zip(sorted_nodes, wires))
 
-        if set(wires) != set(nodes):
-            wire_map = dict(zip(nodes, wires))
-            edges = [(wire_map[edge[0]], wire_map[edge[1]]) for edge in edges]
+        edges = graph.edge_labels if isinstance(graph, QubitGraph) else graph.edges
+        edges = [(wire_map[edge[0]], wire_map[edge[1]]) for edge in edges]
 
         for wire in wires:
             op_list.append(one_qubit_ops(wires=wire))


Test patch:
diff --git a/tests/ftqc/test_ftqc_graph_state_prep.py b/tests/ftqc/test_ftqc_graph_state_prep.py
index f8cbea3dc..f936cf26b 100644
--- a/tests/ftqc/test_ftqc_graph_state_prep.py
+++ b/tests/ftqc/test_ftqc_graph_state_prep.py
@@ -287,3 +287,341 @@ class TestGraphStatePrep:
                 one_qubit_ops=one_qubit_ops,
                 two_qubit_ops=two_qubit_ops,
             )
+
+
+class TestGraphStateInvariantUnderInternalGraphOrdering:
+    """Additional tests of graph-state preparation to ensure that the resulting state is invariant
+    under the internal ordering of the nodes and edges in the graph.
+
+    In other words, identical graph structures, regardless of the order in which the nodes and edges
+    are stored in memory, should result in the same state.
+
+    At the time of writing, NetworkX graphs use built-in Python dictionaries to store a graph's
+    adjacency list. As of Python 3.7, `dict` objects are insertion-ordered:
+
+        https://docs.python.org/3/whatsnew/3.7.html
+
+    Hence, the order in which nodes and edges are inserted into the NetworkX graph object will
+    affect the access order when iterating over the set of nodes and the set of edges. Graph data
+    structures are inherently unordered, therefore differences in the access order for the same
+    graph structure should not affect the state returned by GraphStatePrep.
+    """
+
+    @pytest.mark.parametrize(
+        "graph",
+        [
+            # Permute the node order in the adjacency list
+            nx.Graph({1: {0, 2}, 2: {1, 3}, 3: {2}, 0: {1}}),
+            nx.Graph({2: {1, 3}, 3: {2}, 0: {1}, 1: {0, 2}}),
+            nx.Graph({3: {2}, 0: {1}, 1: {0, 2}, 2: {1, 3}}),
+            nx.Graph({0: {1}, 1: {0, 2}, 3: {2}, 2: {1, 3}}),
+            nx.Graph({0: {1}, 2: {1, 3}, 1: {0, 2}, 3: {2}}),
+            nx.Graph({1: {0, 2}, 0: {1}, 2: {1, 3}, 3: {2}}),
+        ],
+    )
+    @pytest.mark.parametrize("one_qubit_op", [qml.H, qml.X, qml.Y, qml.Z, qml.S, qml.SX])
+    @pytest.mark.parametrize("two_qubit_op", [qml.CZ])
+    def test_graph_state_invariant_under_internal_ordering_1d_chain_same_wires_indices(
+        self, graph, one_qubit_op, two_qubit_op
+    ):
+        """Test that the state returned by GraphStatePrep is invariant under the internal ordering
+        of the nodes and edges in the graph.
+
+        The graph structure is a 1D chain and the sets of node and wire labels are the same.
+        """
+        # Graph structure: (0) -- (1) -- (2) -- (3)
+        graph_ref = nx.Graph({0: {1}, 1: {0, 2}, 2: {1, 3}, 3: {2}})
+
+        # The sequence of wires is constant
+        wires = [0, 1, 2, 3]
+
+        self._check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op)
+
+    @pytest.mark.parametrize(
+        "graph",
+        [
+            # Permute the node order in the adjacency list
+            nx.Graph({"b": {"a", "c"}, "c": {"b", "d"}, "d": {"c"}, "a": {"b"}}),
+            nx.Graph({"c": {"b", "d"}, "d": {"c"}, "a": {"b"}, "b": {"a", "c"}}),
+            nx.Graph({"d": {"c"}, "a": {"b"}, "b": {"a", "c"}, "c": {"b", "d"}}),
+            nx.Graph({"a": {"b"}, "b": {"a", "c"}, "d": {"c"}, "c": {"b", "d"}}),
+            nx.Graph({"a": {"b"}, "c": {"b", "d"}, "b": {"a", "c"}, "d": {"c"}}),
+            nx.Graph({"b": {"a", "c"}, "a": {"b"}, "c": {"b", "d"}, "d": {"c"}}),
+        ],
+    )
+    @pytest.mark.parametrize("one_qubit_op", [qml.H, qml.X, qml.Y, qml.Z, qml.S, qml.SX])
+    @pytest.mark.parametrize("two_qubit_op", [qml.CZ])
+    def test_graph_state_invariant_under_internal_ordering_1d_chain_diff_wires_indices(
+        self, graph, one_qubit_op, two_qubit_op
+    ):
+        """Test that the state returned by GraphStatePrep is invariant under the internal ordering
+        of the nodes and edges in the graph.
+
+        The graph structure is a 1D chain and the sets of node and wire labels are different.
+        """
+        # Graph structure: ("a") -- ("b") -- ("c") -- ("d")
+        graph_ref = nx.Graph({"a": {"b"}, "b": {"a", "c"}, "c": {"b", "d"}, "d": {"c"}})
+
+        # The sequence of wires is constant
+        wires = [0, 1, 2, 3]
+
+        self._check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op)
+
+    @pytest.mark.parametrize(
+        "graph",
+        [
+            # Permute the node order in the adjacency list
+            nx.Graph({1: {0, 3}, 2: {0, 3}, 3: {1, 2}, 0: {1, 2}}),
+            nx.Graph({2: {0, 3}, 3: {1, 2}, 0: {1, 2}, 1: {0, 3}}),
+            nx.Graph({3: {1, 2}, 0: {1, 2}, 1: {0, 3}, 2: {0, 3}}),
+            nx.Graph({0: {1, 2}, 1: {0, 3}, 3: {1, 2}, 2: {0, 3}}),
+            nx.Graph({0: {1, 2}, 2: {0, 3}, 1: {0, 3}, 3: {1, 2}}),
+            nx.Graph({1: {0, 3}, 0: {1, 2}, 2: {0, 3}, 3: {1, 2}}),
+        ],
+    )
+    @pytest.mark.parametrize("one_qubit_op", [qml.H, qml.X, qml.Y, qml.Z, qml.S, qml.SX])
+    @pytest.mark.parametrize("two_qubit_op", [qml.CZ])
+    def test_graph_state_invariant_under_internal_ordering_2d_grid_same_wires_indices(
+        self, graph, one_qubit_op, two_qubit_op
+    ):
+        """Test that the state returned by GraphStatePrep is invariant under the internal ordering
+        of the nodes and edges in the graph.
+
+        The graph structure is a 2D grid and the sets of node and wire labels are the same.
+        """
+        # Graph structure: (0) -- (1)
+        #                   |      |
+        #                  (2) -- (3)
+        graph_ref = nx.Graph({0: {1, 2}, 1: {0, 3}, 2: {0, 3}, 3: {1, 2}})
+
+        # The sequence of wires is constant
+        wires = [0, 1, 2, 3]
+
+        self._check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op)
+
+    @pytest.mark.parametrize(
+        "graph",
+        [
+            # Permute the node order in the adjacency list
+            nx.Graph(
+                {
+                    (0, 1): {(0, 0), (1, 1)},
+                    (1, 0): {(0, 0), (1, 1)},
+                    (1, 1): {(0, 1), (1, 0)},
+                    (0, 0): {(1, 0), (0, 1)},
+                }
+            ),
+            nx.Graph(
+                {
+                    (1, 0): {(0, 0), (1, 1)},
+                    (1, 1): {(0, 1), (1, 0)},
+                    (0, 0): {(1, 0), (0, 1)},
+                    (0, 1): {(0, 0), (1, 1)},
+                }
+            ),
+            nx.Graph(
+                {
+                    (1, 1): {(0, 1), (1, 0)},
+                    (0, 0): {(1, 0), (0, 1)},
+                    (0, 1): {(0, 0), (1, 1)},
+                    (1, 0): {(0, 0), (1, 1)},
+                }
+            ),
+        ],
+    )
+    @pytest.mark.parametrize("one_qubit_op", [qml.H, qml.X, qml.Y, qml.Z, qml.S, qml.SX])
+    @pytest.mark.parametrize("two_qubit_op", [qml.CZ])
+    def test_graph_state_invariant_under_internal_ordering_2d_grid_diff_wires_indices(
+        self, graph, one_qubit_op, two_qubit_op
+    ):
+        """Test that the state returned by GraphStatePrep is invariant under the internal ordering
+        of the nodes and edges in the graph.
+
+        The graph structure is a 2D grid and the sets of node and wire labels are different.
+        """
+        # Graph structure: (0,0) -- (0,1)
+        #                    |        |
+        #                  (1,0) -- (1,1)
+        graph_ref = nx.Graph(
+            {
+                (0, 0): {(1, 0), (0, 1)},
+                (0, 1): {(0, 0), (1, 1)},
+                (1, 0): {(0, 0), (1, 1)},
+                (1, 1): {(0, 1), (1, 0)},
+            }
+        )
+
+        # The sequence of wires is constant
+        wires = [0, 1, 2, 3]
+
+        self._check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op)
+
+    @pytest.mark.parametrize(
+        "graph",
+        [
+            # Permute the node order in the adjacency list
+            nx.Graph(
+                {
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                }
+            ),
+            nx.Graph(
+                {
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                }
+            ),
+            nx.Graph(
+                {
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                }
+            ),
+            nx.Graph(
+                {
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                }
+            ),
+            nx.Graph(
+                {
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                }
+            ),
+            nx.Graph(
+                {
+                    6: {2, 4, 7},
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                }
+            ),
+            nx.Graph(
+                {
+                    7: {3, 5, 6},
+                    0: {1, 2, 4},
+                    1: {0, 3, 5},
+                    2: {0, 3, 6},
+                    3: {1, 2, 7},
+                    4: {0, 5, 6},
+                    5: {1, 4, 7},
+                    6: {2, 4, 7},
+                }
+            ),
+        ],
+    )
+    @pytest.mark.parametrize("one_qubit_op", [qml.H, qml.X, qml.Y, qml.Z, qml.S, qml.SX])
+    @pytest.mark.parametrize("two_qubit_op", [qml.CZ])
+    def test_graph_state_invariant_under_internal_ordering_3d_grid_same_wires_indices(
+        self, graph, one_qubit_op, two_qubit_op
+    ):
+        """Test that the state returned by GraphStatePrep is invariant under the internal ordering
+        of the nodes and edges in the graph.
+
+        The graph structure is a 3D chain and the sets of node and wire labels are the same.
+        """
+        # Graph structure:    (4)-----(5)
+        #                     /|      /|
+        #                  (0)-----(1) |
+        #                   | (6)---|-(7)
+        #                   | /     | /
+        #                  (2)-----(3)
+        graph_ref = nx.Graph(
+            {
+                0: {1, 2, 4},
+                1: {0, 3, 5},
+                2: {0, 3, 6},
+                3: {1, 2, 7},
+                4: {0, 5, 6},
+                5: {1, 4, 7},
+                6: {2, 4, 7},
+                7: {3, 5, 6},
+            }
+        )
+
+        # The sequence of wires is constant
+        wires = [0, 1, 2, 3, 4, 5, 6, 7]
+
+        self._check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op)
+
+    @staticmethod
+    def _check_graphs_yield_same_state(graph, graph_ref, wires, one_qubit_op, two_qubit_op):
+        """Helper function for the above tests.
+
+        Creates a minimal circuit that returns the state resulting from GraphStatePrep. It then
+        executes this circuit using the input graphs and asserts that the resulting states are
+        equal. ``graph_ref`` is the assumed to be the reference graph that yields the state that is
+        known to be correct.
+        """
+        # Sanity check: ensure that the graphs have the same adjacency list
+        assert (
+            graph.adj == graph_ref.adj
+        ), "Internal error: all graphs defined in this test should have the same adjacency list"
+
+        dev = qml.device("default.qubit")
+
+        @qml.qnode(dev)
+        def circuit(graph):
+            GraphStatePrep(
+                graph=graph, wires=wires, one_qubit_ops=one_qubit_op, two_qubit_ops=two_qubit_op
+            )
+            return qml.state()
+
+        result_ref = circuit(graph_ref)
+        result = circuit(graph)
+        assert np.all(result_ref == result)
+
+    def test_unsortable_graph_node_labels_raise_type_error(self):
+        """Test that using a graph with unsortable node labels (in this case, the node labels are a
+        mix of integers and strings) as input to GraphStatePrep raises a TypeError.
+        """
+        # Graph structure: (0) -- (a) -- (1)
+        graph = nx.Graph({0: {"a"}, "a": (0, 1), 1: {"a"}})
+        dev = qml.device("default.qubit")
+
+        @qml.qnode(dev)
+        def circuit():
+            GraphStatePrep(graph=graph, wires=[0, 1, 2])
+            return qml.state()
+
+        with pytest.raises(
+            TypeError,
+            match="GraphStatePrep requires the node labels of the input graph to be sortable",
+        ):
+            circuit()