Repository: tqec/tqec

Issue:
`BlockGraph.get_abstract_observables` creates duplicates in presence of labels
## Describe the bug
It seems that `BlockGraph.get_abstract_observables` can create the same observables twice *if labels are present (at non-port nodes)*. The underlying correlation surfaces are different but seem to contain duplicate edges.

## Steps to reproduce the behavior:
The following code creates a block graph which should only have one correlation surface and hence one observable. It represents a logical qubit which gets moved to another place (see also pictures below). It is initialized and measured in the X-basis.

IMPORTANT: The error goes away (the asserts fail) if you remove the labels. They are there to indicate that "normally" there should go the ports. Only for simulation I fix to some particular kind of initialization and measurement.

```python
from tqec import Position3D, ZXNode, ZXGraph, ZXKind

# NOTE: the label changes the behaviour of the code (asserts fail if you remove both of them).
_in = ZXNode(Position3D(0, 0, 0), ZXKind.Z, "In")
_a = ZXNode(Position3D(0, 0, 1), ZXKind.Z)
_b = ZXNode(Position3D(1, 0, 1), ZXKind.Z)
_out = ZXNode(Position3D(1, 0, 2), ZXKind.Z, "Out")

g_move_zx = ZXGraph(name="move")
g_move_zx.add_edge(_in, _a)
g_move_zx.add_edge(_a, _b)
g_move_zx.add_edge(_b, _out)

g_move_block = g_move_zx.to_block_graph()

observables, correlation_surfaces = (
    g_move_block.get_abstract_observables()
)

# The following asserts (wrongly) succeed:

assert len(observables) == 2, "Actuall I would expect == 1."
assert observables[0] == observables[1]

assert len(correlation_surfaces) == 2, "Actuall I would expect == 1."
assert correlation_surfaces[0] != correlation_surfaces[1]
```

The following shows that both correlation surfaces have a duplicate edge:

```python
for s in correlation_surfaces:
    for e in s.span:
        print(e)
    print()
```

Output:

```
X(1,0,1)-X(1,0,2)
X(0,0,1)-X(1,0,1)
X(0,0,0)-X(0,0,1)
X(0,0,0)-X(0,0,1)

X(0,0,1)-X(1,0,1)
X(1,0,1)-X(1,0,2)
X(0,0,0)-X(0,0,1)
X(1,0,1)-X(1,0,2)
```

## Expected behavior
I did not expect that adding labels changes the correlation surfaces at all. In particular I did not expect to find the same observable twice instead of once. 

Looking at the images below it looks like the user is not expected to put labels on a non-port node. I think this should still work for the following use case: Suppose I want to model a general computation with actual inputs and outputs (ports) but then *interactively* I decide to briefly fix the inputs and outputs to do some quick simulation to check if everything looks alright. It is natural to just change the zx-kind briefly from `P` to e.g. `Z` without caring about the label. In that case the label could be ignored but it might still be nice to see it in the plots.

## Screenshots and MP4s
For completeness, this is how the zx-graph and its block-graph look like.

![moving_qubit_zx](https://github.com/user-attachments/assets/d005fbc5-0c9a-4bb7-8609-9b1bc1af3d91)

![moving_qubit_block](https://github.com/user-attachments/assets/f23fd4a2-df1e-4eed-b0d5-4a3a2daacb99)


## Browser info (please complete for frontend bugs):
NA

## Python dependency versions (please complete for backend bugs)

Run `pip freeze` and put the output in the `<details>` element below.


<details>
accessible-pygments==0.0.5
alabaster==1.0.0
antlr4-python3-runtime==4.13.2
anyio==4.8.0
argon2-cffi==23.1.0
argon2-cffi-bindings==21.2.0
arrow==1.3.0
asttokens==3.0.0
async-lru==2.0.4
attrs==24.3.0
babel==2.16.0
basedpyright==1.23.2
beautifulsoup4==4.12.3
bleach==6.2.0
certifi==2024.12.14
cffi==1.17.1
cfgv==3.4.0
charset-normalizer==3.4.1
click==8.1.8
comm==0.2.2
contourpy==1.3.1
coverage==7.6.10
cycler==0.12.1
debugpy==1.8.11
decorator==5.1.1
defusedxml==0.7.1
dill==0.3.9
distlib==0.3.9
docutils==0.21.2
duckdb==1.1.3
exceptiongroup==1.2.2
executing==2.1.0
fastjsonschema==2.21.1
filelock==3.16.1
fonttools==4.55.3
fqdn==1.5.1
h11==0.14.0
httpcore==1.0.7
httpx==0.28.1
identify==2.6.5
idna==3.10
imagesize==1.4.1
iniconfig==2.0.0
ipykernel==6.29.5
ipython==8.31.0
ipython-genutils==0.2.0
ipywidgets==8.1.5
isoduration==20.11.0
itsdangerous==2.2.0
jedi==0.19.2
Jinja2==3.1.5
json5==0.10.0
jsonpointer==3.0.0
jsonschema==4.23.0
jsonschema-specifications==2024.10.1
jupyter-events==0.11.0
jupyter-lsp==2.2.5
jupyter_client==8.6.3
jupyter_core==5.7.2
jupyter_server==2.15.0
jupyter_server_terminals==0.5.3
jupyterlab==4.3.4
jupyterlab_pygments==0.3.0
jupyterlab_server==2.27.3
jupyterlab_widgets==3.0.13
kiwisolver==1.4.8
lark==1.1.9
marimo==0.10.9
Markdown==3.7
markdown-it-py==3.0.0
MarkupSafe==3.0.2
matplotlib==3.10.0
matplotlib-inline==0.1.7
mdit-py-plugins==0.4.2
mdurl==0.1.2
mistune==3.1.0
mpmath==1.3.0
mypy==1.14.1
mypy-extensions==1.0.0
myst-parser==4.0.0
narwhals==1.21.0
nbclient==0.10.2
nbconvert==7.16.5
nbformat==5.10.4
nbsphinx==0.9.6
nest-asyncio==1.6.0
networkx==3.4.2
nodeenv==1.9.1
nodejs-wheel-binaries==22.12.0
notebook==7.3.2
notebook_shim==0.2.4
numpy==1.26.4
openqasm3==1.0.0
overrides==7.7.0
packaging==24.2
pandoc==2.4
pandocfilters==1.5.1
parso==0.8.4
pbr==6.1.0
pexpect==4.9.0
pillow==11.1.0
platformdirs==4.3.6
pluggy==1.5.0
plumbum==1.9.0
ply==3.11
polars==1.19.0
pre_commit==4.0.1
prometheus_client==0.21.1
prompt_toolkit==3.0.48
psutil==6.1.1
ptyprocess==0.7.0
pure_eval==0.2.3
pyarrow==18.1.0
pycollada==0.8
pycparser==2.22
pycryptosat==5.11.21
pydata-sphinx-theme==0.16.1
Pygments==2.19.0
PyMatching==2.2.1
pymdown-extensions==10.13
pyparsing==3.2.1
pyperclip==1.9.0
PySide6==6.8.1.1
PySide6_Addons==6.8.1.1
PySide6_Essentials==6.8.1.1
pytest==8.3.4
pytest-cov==6.0.0
python-dateutil==2.9.0.post0
python-json-logger==3.2.1
python-sat==1.8.dev13
PyYAML==6.0.2
pyzmq==26.2.0
pyzx==0.8.0
qiskit==1.3.1
qiskit-qasm3-import==0.5.1
referencing==0.35.1
requests==2.32.3
rfc3339-validator==0.1.4
rfc3986-validator==0.1.1
rpds-py==0.22.3
ruff==0.8.6
rustworkx==0.15.1
scipy==1.15.0
Send2Trash==1.8.3
shapely==2.0.6
shiboken6==6.8.1.1
sinter==1.14.0
six==1.17.0
sniffio==1.3.1
snowballstemmer==2.2.0
soupsieve==2.6
Sphinx==8.1.3
sphinxcontrib-applehelp==2.0.0
sphinxcontrib-devhelp==2.0.0
sphinxcontrib-htmlhelp==2.1.0
sphinxcontrib-jsmath==1.0.1
sphinxcontrib-mermaid==1.0.0
sphinxcontrib-qthelp==2.0.0
sphinxcontrib-serializinghtml==2.0.0
stack-data==0.6.3
starlette==0.45.2
stevedore==5.4.0
stim==1.14.0
symengine==0.13.0
sympy==1.13.3
terminado==0.18.1
tinycss2==1.4.0
tomli==2.2.1
tomlkit==0.13.2
tornado==6.4.2
tqdm==4.67.1
-e git+ssh://git@github.com/rainij/tqec.git@6b9b1aa830d9ecaacf26e41bc98e9af3344f6cfa#egg=tqec
tqecd==0.1.1
traitlets==5.14.3
types-networkx==3.4.2.20241227
types-python-dateutil==2.9.0.20241206
typing_extensions==4.12.2
uri-template==1.3.0
urllib3==2.3.0
uvicorn==0.34.0
virtualenv==20.28.1
wcwidth==0.2.13
webcolors==24.11.1
webencodings==0.5.1
websocket-client==1.8.0
websockets==14.1
widgetsnbextension==4.0.13
zxlive==0.2.0
</details>


## Additional context
None.

Hints from issue comments:
@inmzhang: Thanks for the issue, nice catch!

The problem arises because the label modifies the hash of the `ZXNode` and `ZXEdge`. When we start searching the correlation surface with a frontier node [`leaf.with_zx_flipped()`](https://github.com/tqec/tqec/blob/main/src/tqec/computation/correlation.py#L196-L200), the label field may be included. We then use that node to [construct edges](https://github.com/tqec/tqec/blob/main/src/tqec/computation/correlation.py#L278) in the correlation surface, and we [prune the search](https://github.com/tqec/tqec/blob/main/src/tqec/computation/correlation.py#L304) by checking the hash of the traversed edges.

The simple way to fix the issue is to discard the label field in the node when initializing the frontier of the search:

replace [this](https://github.com/tqec/tqec/blob/main/src/tqec/computation/correlation.py#L198) with
```py
_find_spans_with_flood_fill(zx_graph, {ZXNode(leaf.position, leaf.kind.with_zx_flipped())}, set()) or []
```

Alternatively, we could exclude the label from the hash of non-port nodes.

Would you like to make a PR to address this?
@rainij: > Would you like to make a PR to address this?

Yes would be a nice little issue to get to know this part of the code.

Due to work and other duties I might take until the weekend until I can address this. If this is no issue you can assign me :). And if I give no feedback during the next two weeks everybody can feel free to remind me of course :).

Solution patch:
diff --git a/src/tqec/computation/correlation.py b/src/tqec/computation/correlation.py
index 4de0fa49..a6bb95cc 100644
--- a/src/tqec/computation/correlation.py
+++ b/src/tqec/computation/correlation.py
@@ -4,8 +4,8 @@ the functions to find the correlation surfaces in the ZX graph."""
 from __future__ import annotations
 
 import itertools
+from collections.abc import Iterable
 from dataclasses import dataclass, field
-from typing import Iterable
 
 from tqec.computation.zx_graph import ZXEdge, ZXGraph, ZXKind, ZXNode
 from tqec.exceptions import TQECException
@@ -39,7 +39,7 @@ class CorrelationSurface:
     represented as a mapping from the the input/output labels to the logical operator type there.
 
     Attributes:
-        nodes: A set of ``ZXNode`` representing the logical operators appeared in the correlation surface.
+        nodes: A set of ``ZXNode`` representing the logical operators appearing in the correlation surface.
             For example, if either a logical X operator or Z operator has appeared at this node position in
             the span, then the node is of X or Z kind. If both X and Z logical operators have appeared at
             this node position in the span, then the node is of Y kind.
@@ -198,22 +198,30 @@ def _find_correlation_surfaces_from_leaf(
     # Z/X type node can only support the correlation surface with the opposite type.
     if leaf.is_zx_node:
         spans = (
-            _find_spans_with_flood_fill(zx_graph, {leaf.with_zx_flipped()}, set()) or []
+            _find_spans_with_flood_fill(
+                zx_graph, {ZXNode(leaf.position, leaf.kind.with_zx_flipped())}, set()
+            )
+            or []
         )
         return _construct_compatible_correlation_surfaces(zx_graph, spans)
+
     x_spans = (
         _find_spans_with_flood_fill(zx_graph, {ZXNode(leaf.position, ZXKind.X)}, set())
         or []
     )
+
     z_spans = (
         _find_spans_with_flood_fill(zx_graph, {ZXNode(leaf.position, ZXKind.Z)}, set())
         or []
     )
+
     # For the port node, try to construct both the x and z type correlation surfaces.
     if leaf.is_port:
         return _construct_compatible_correlation_surfaces(zx_graph, x_spans + z_spans)
+
     # For the Y type node, the correlation surface must be the product of the x and z type.
     assert leaf.is_y_node
+
     return _construct_compatible_correlation_surfaces(
         zx_graph, [sx | sz for sx, sz in itertools.product(x_spans, z_spans)]
     )
@@ -337,6 +345,7 @@ def _find_spans_with_flood_fill(
         spans = _find_spans_with_flood_fill(zx_graph, product_frontier, product_span)
         if spans is not None:
             final_spans.extend(spans)
+
     return final_spans or None
 
 


Test patch:
diff --git a/src/tqec/computation/correlation_test.py b/src/tqec/computation/correlation_test.py
index 677e2b6c..eadeee67 100644
--- a/src/tqec/computation/correlation_test.py
+++ b/src/tqec/computation/correlation_test.py
@@ -1,5 +1,7 @@
+import pytest
+
 from tqec.computation.correlation import CorrelationSurface
-from tqec.computation.zx_graph import ZXKind, ZXEdge, ZXGraph, ZXNode
+from tqec.computation.zx_graph import ZXEdge, ZXGraph, ZXKind, ZXNode
 from tqec.gallery.solo_node import solo_node_zx_graph
 from tqec.position import Position3D
 
@@ -14,27 +16,30 @@ def test_correlation_single_xz_node() -> None:
     assert surface.observables_at_nodes == {Position3D(0, 0, 0): ZXKind.Z}
 
 
-def test_correlation_two_xz_node() -> None:
-    for kind in [ZXKind.X, ZXKind.Z]:
-        g = ZXGraph()
-        g.add_edge(
-            ZXNode(Position3D(0, 0, 0), kind),
-            ZXNode(Position3D(0, 0, 1), kind),
+@pytest.mark.parametrize("label_u", [None, "foo"])
+@pytest.mark.parametrize("kind", [ZXKind.X, ZXKind.Z])
+def test_correlation_two_xz_nodes(kind: ZXKind, label_u: str | None) -> None:
+    g = ZXGraph()
+    g.add_edge(
+        ZXNode(Position3D(0, 0, 0), kind, label=label_u or ""),
+        ZXNode(Position3D(0, 0, 1), kind),
+    )
+    assert g.find_correlation_surfaces() == [
+        CorrelationSurface.from_span(
+            g,
+            frozenset(
+                [
+                    ZXEdge(
+                        ZXNode(Position3D(0, 0, 0), kind.with_zx_flipped()),
+                        ZXNode(Position3D(0, 0, 1), kind.with_zx_flipped()),
+                    )
+                ]
+            ),
         )
-        assert g.find_correlation_surfaces() == [
-            CorrelationSurface.from_span(
-                g,
-                frozenset(
-                    [
-                        ZXEdge(
-                            ZXNode(Position3D(0, 0, 0), kind.with_zx_flipped()),
-                            ZXNode(Position3D(0, 0, 1), kind.with_zx_flipped()),
-                        )
-                    ]
-                ),
-            )
-        ]
+    ]
+
 
+def test_correlation_two_xz_nodes_impossible() -> None:
     g = ZXGraph()
     g.add_edge(
         ZXNode(Position3D(0, 0, 0), ZXKind.X),