Repository: tqec/tqec

Issue:
Always try to fix shadowed faces during compilation
## Is your feature request related to a problem? Please describe.

The following code:

```py
cubes = [
    (Position3D(x=0, y=1, z=0), 'XXZ'),
    (Position3D(x=2, y=1, z=0), 'XXZ'),
    (Position3D(x=0, y=0, z=0), 'XZZ'),
    (Position3D(x=1, y=1, z=0), 'XXZ'),
    (Position3D(x=2, y=0, z=0), 'XZZ')
]
pipes = [
    (Position3D(x=0, y=1, z=0), Position3D(x=0, y=0, z=0)),
    (Position3D(x=0, y=1, z=0), Position3D(x=1, y=1, z=0)),
    (Position3D(x=2, y=1, z=0), Position3D(x=1, y=1, z=0)),
    (Position3D(x=2, y=1, z=0), Position3D(x=2, y=0, z=0))
]

b = BlockGraph()
for cube in cubes:
    b.add_cube(*cube)
for pipe in pipes:
    b.add_pipe(*pipe)
```
creates a block graph:

![Image](https://github.com/user-attachments/assets/3f76fce5-0691-49f1-bcfa-8feb8d298958)

However, it will results in compilation error (run on branch [feat/change-plaquette-invariant](https://github.com/tqec/tqec/tree/feat/change-plaquette-invariant)):

```txt
tqec.utils.exceptions.TQECException: I-shaped spatial junctions (i.e., spatial junctions with only two arms that are the opposite of each other: LEFT/RIGHT or UP/DOWN) should not use get_spatial_cube_qubit_template but rather use a conventional memory logical qubit with get_memory_qubit_template.
```

The `XXZ` cube at (1,1,0) is expected to be a non-spatial cube, while the faces along X axis are shadowed by connected pipes and do not really matter. As we will choose the template used for the cube depending on whether it's a spatial cube, we need to fix it by changing the cube kind to `ZXZ`. Currently, it can be done by calling `b = b.fix_shadowed_faces()`.

It suggests that we should always try to fix the shadowed faces before the compiling the circuits and gives the user the freedom to not care about shadowed faces.

## Describe the solution you'd like

Call `fix_shadowed_faces()` on `BlockGraph` at the start of the compilation pipeline. And we should remove the [warning](https://github.com/tqec/tqec/blob/main/src/tqec/interop/collada/read_write.py#L224) when importing a dae file since it will be an expected behavior and the users should never care about the shadowed faces. We should also ignore the shadowed faces during validating the block graph and it needs some changes in [BlockGraph.validate()](https://github.com/tqec/tqec/blob/main/src/tqec/computation/block_graph.py#L315).

Hints from issue comments:

Solution patch:
diff --git a/src/tqec/compile/compile.py b/src/tqec/compile/compile.py
index d003f59e..cd032f21 100644
--- a/src/tqec/compile/compile.py
+++ b/src/tqec/compile/compile.py
@@ -329,12 +329,24 @@ def compile_block_graph(
         A :class:`CompiledGraph` object that can be used to generate a
         ``stim.Circuit`` and scale easily.
     """
+    # All the ports should be filled before compiling the block graph.
     if block_graph.num_ports != 0:
         raise TQECException(
-            "Can not compile a block graph with open ports into circuits."
+            "Can not compile a block graph with open ports into circuits. "
+            "You might want to call `fill_ports` or `fill_ports_for_minimal_simulation` "
+            "on the block graph before compiling it."
         )
+    # Validate the graph can represent a valid computation.
+    block_graph.validate()
 
-    # 0. Set the minimum z of block graph to 0.(time starts from zero)
+    # Fix the shadowed faces of the cubes to avoid using spatial cubes
+    # when a non-spatial cube can be used at the same position.
+    # For example, when three XXZ cubes are connected in a row along the x-axis,
+    # the middle one can be replaced by a ZXX cube because the faces along the
+    # x-axis are shadowed by the connected pipes.
+    block_graph = block_graph.fix_shadowed_faces()
+
+    # Set the minimum z of block graph to 0.(time starts from zero)
     minz = min(cube.position.z for cube in block_graph.cubes)
     if minz != 0:
         block_graph = block_graph.shift_by(dz=-minz)
@@ -343,13 +355,13 @@ def compile_block_graph(
         cube: CubeSpec.from_cube(cube, block_graph) for cube in block_graph.cubes
     }
 
-    # 1. Get the base compiled blocks before applying the substitution rules.
+    # Get the base compiled blocks before applying the substitution rules.
     blocks: dict[Position3D, CompiledBlock] = {}
     for cube in block_graph.cubes:
         spec = cube_specs[cube]
         blocks[cube.position] = block_builder(spec)
 
-    # 2. Apply the substitution rules to the compiled blocks inplace.
+    # Apply the substitution rules to the compiled blocks inplace.
     pipes = block_graph.pipes
     time_pipes = [pipe for pipe in pipes if pipe.direction == Direction3D.Z]
     space_pipes = [pipe for pipe in pipes if pipe.direction != Direction3D.Z]
@@ -364,7 +376,7 @@ def compile_block_graph(
         blocks[pos1].update_layers(substitution.src)
         blocks[pos2].update_layers(substitution.dst)
 
-    # 3. Collect by time and create the blocks layout.
+    # Collect by time and create the blocks layout.
     min_z = min(pos.z for pos in blocks.keys())
     max_z = max(pos.z for pos in blocks.keys())
     layout_slices: list[BlockLayout] = [
@@ -378,7 +390,7 @@ def compile_block_graph(
         for z in range(min_z, max_z + 1)
     ]
 
-    # 4. Get the abstract observables to be included in the compiled circuit.
+    # Get the abstract observables to be included in the compiled circuit.
     obs_included: list[AbstractObservable] = []
     if observables is not None:
         if observables == "auto":
diff --git a/src/tqec/computation/block_graph.py b/src/tqec/computation/block_graph.py
index a39c0f60..2b7c7403 100644
--- a/src/tqec/computation/block_graph.py
+++ b/src/tqec/computation/block_graph.py
@@ -336,14 +336,14 @@ class BlockGraph:
     def _validate_locally_at_cube(self, cube: Cube) -> None:
         """Check the validity of the block structures locally at a cube."""
         pipes = self.pipes_at(cube.position)
-        # a). no fanout
+        # no fanout at ports
         if cube.is_port:
             if len(pipes) != 1:
                 raise TQECException(
                     f"Port at {cube.position} does not have exactly one pipe connected."
                 )
             return
-        # c). time-like Y
+        # time-like Y
         if cube.is_y_cube:
             if len(pipes) != 1:
                 raise TQECException(
@@ -355,13 +355,27 @@ class BlockGraph:
                 )
             return
 
+        assert isinstance(cube.kind, ZXCube)
         # Check the color matching conditions
         pipes_by_direction: dict[Direction3D, list[Pipe]] = {}
         for pipe in pipes:
             pipes_by_direction.setdefault(pipe.direction, []).append(pipe)
-        # d), f), g). Match color
-        for pipe in pipes:
-            pipe.check_compatible_with_cubes()
+        for direction in Direction3D.all_directions():
+            # the pair of faces are shadowed in the direction
+            # we do not care about the colors of shadowed faces
+            if len(pipes_by_direction.get(direction, [])) == 2:
+                continue
+            # faces at the same plane should have the same color
+            cube_color = cube.kind.get_basis_along(direction)
+            for ortho_dir in direction.orthogonal_directions:
+                for pipe in pipes_by_direction.get(ortho_dir, []):
+                    pipe_color = pipe.kind.get_basis_along(
+                        direction, pipe.at_head(cube.position)
+                    )
+                    if pipe_color != cube_color:
+                        raise TQECException(
+                            f"Cube {cube} has mismatched colors with pipe {pipe}."
+                        )
 
     def to_zx_graph(self) -> PositionedZX:
         """Convert the block graph to a positioned PyZX graph.
@@ -662,7 +676,7 @@ class BlockGraph:
                 pos_map[pipe.v.position],
                 cast(PipeKind, rotated_kind),
             )
-        return rotated.fix_shadowed_faces()
+        return rotated
 
     def fix_shadowed_faces(self) -> BlockGraph:
         """Fix the basis of those shadowed faces of the cubes in the graph.
diff --git a/src/tqec/computation/pipe.py b/src/tqec/computation/pipe.py
index 3a98c487..d123bb8e 100644
--- a/src/tqec/computation/pipe.py
+++ b/src/tqec/computation/pipe.py
@@ -238,30 +238,6 @@ class Pipe:
         """The direction along which the pipe connects the cubes."""
         return self.kind.direction
 
-    def check_compatible_with_cubes(self) -> None:
-        """Check if the pipe is compatible with the cubes it connects.
-
-        For compatibility, each cube (head and tail) must match the pipe's basis
-        along each direction, except for the direction of the pipe, if the cube is
-        of type :py:class:`~tqec.computation.cube.ZXCube`.
-
-        Raises:
-            TQECException: If the pipe is not compatible with the cubes.
-        """
-        for cube in self:
-            if cube.is_port or cube.is_y_cube:
-                continue
-            assert isinstance(cube.kind, ZXCube)
-            for direction in Direction3D.all_directions():
-                if direction == self.direction:
-                    continue
-                cube_basis = cube.kind.get_basis_along(direction)
-                pipe_basis = self.kind.get_basis_along(direction, cube == self.u)
-                if cube_basis != pipe_basis:
-                    raise TQECException(
-                        f"The pipe is not compatible with the cube {cube} along {direction} direction."
-                    )
-
     def at_head(self, position: Position3D) -> bool:
         """Whether the position is at the head (u) of the pipe."""
         if position == self.u.position:
@@ -273,3 +249,6 @@ class Pipe:
     def __iter__(self) -> Generator[Cube]:
         yield self.u
         yield self.v
+
+    def __str__(self) -> str:
+        return f"{self.u}--({self.kind})--{self.v}"
diff --git a/src/tqec/interop/collada/read_write.py b/src/tqec/interop/collada/read_write.py
index 59b143f2..b8de98ae 100644
--- a/src/tqec/interop/collada/read_write.py
+++ b/src/tqec/interop/collada/read_write.py
@@ -5,7 +5,6 @@ from __future__ import annotations
 import pathlib
 from dataclasses import dataclass
 from typing import BinaryIO, Iterable, cast
-import warnings
 
 import collada
 import collada.source
@@ -16,7 +15,7 @@ from tqec.computation.block_graph import BlockGraph, BlockKind, block_kind_from_
 from tqec.computation.cube import CubeKind, Port, YHalfCube
 from tqec.computation.pipe import PipeKind
 from tqec.utils.enums import Basis
-from tqec.utils.exceptions import TQECException, TQECWarning
+from tqec.utils.exceptions import TQECException
 from tqec.interop.collada._geometry import (
     BlockGeometries,
     Face,
@@ -219,14 +218,7 @@ def read_block_graph_from_dae_file(
             port_index += 1
         graph.add_pipe(head_pos, tail_pos, pipe_kind)
 
-    graph_fixed = graph.fix_shadowed_faces()
-    if graph_fixed != graph:
-        warnings.warn(
-            "Some shadowed faces have been fixed. "
-            "Check `BlockGraph.fix_shadowed_faces` for more details.",
-            TQECWarning,
-        )
-    return graph_fixed
+    return graph
 
 
 def write_block_graph_to_dae_file(
diff --git a/src/tqec/utils/position.py b/src/tqec/utils/position.py
index 7d70b364..aaba4fd4 100644
--- a/src/tqec/utils/position.py
+++ b/src/tqec/utils/position.py
@@ -205,6 +205,11 @@ class Direction3D(Enum):
             f"{source:=} and {sink:=}."
         )
 
+    @property
+    def orthogonal_directions(self) -> tuple[Direction3D, Direction3D]:
+        i = self.value
+        return Direction3D((i + 1) % 3), Direction3D((i + 2) % 3)
+
 
 @dataclass(frozen=True)
 class SignedDirection3D:


Test patch:
diff --git a/src/tqec/computation/block_graph_test.py b/src/tqec/computation/block_graph_test.py
index 5af3faff..3847971c 100644
--- a/src/tqec/computation/block_graph_test.py
+++ b/src/tqec/computation/block_graph_test.py
@@ -3,6 +3,7 @@ import pytest
 from tqec.computation.block_graph import BlockGraph
 from tqec.computation.cube import ZXCube
 from tqec.computation.pipe import PipeKind
+from tqec.gallery import cnot
 from tqec.utils.enums import Basis
 from tqec.utils.exceptions import TQECException
 from tqec.utils.position import Direction3D, Position3D
@@ -118,6 +119,18 @@ def test_block_graph_validate_3d_corner() -> None:
         g.validate()
 
 
+def test_block_graph_validate_ignore_shadowed_faces() -> None:
+    g = BlockGraph()
+    n1 = g.add_cube(Position3D(0, 0, 0), "XXZ")
+    n2 = g.add_cube(Position3D(1, 0, 0), "XXZ")
+    n3 = g.add_cube(Position3D(-1, 0, 0), "XXZ")
+    n4 = g.add_cube(Position3D(0, 0, 1), "ZXX")
+    g.add_pipe(n1, n2)
+    g.add_pipe(n1, n3)
+    g.add_pipe(n1, n4, "ZXO")
+    g.validate()
+
+
 def test_graph_shift() -> None:
     g = BlockGraph()
     g.add_cube(Position3D(0, 0, 1), "ZXZ")
@@ -221,3 +234,10 @@ def test_cnot_graph_rotation(obs_basis: Basis | None) -> None:
 
     # We need to shift the rotated graph in Z direction to match the two
     assert rg.shift_by(dz=2) == rg_from_scratch
+
+
+def test_block_graph_fix_shadowed_faces() -> None:
+    rotated_cnot = cnot().rotate(Direction3D.X, False)
+    fixed = rotated_cnot.fix_shadowed_faces()
+    assert fixed[Position3D(0, 2, -1)].kind == ZXCube.from_str("ZXX")
+    assert fixed[Position3D(1, 1, -2)].kind == ZXCube.from_str("ZXX")
diff --git a/src/tqec/computation/pipe_test.py b/src/tqec/computation/pipe_test.py
index 55af5462..de4641b1 100644
--- a/src/tqec/computation/pipe_test.py
+++ b/src/tqec/computation/pipe_test.py
@@ -3,7 +3,6 @@ import pytest
 from tqec.computation.cube import Cube, ZXCube
 from tqec.computation.pipe import Pipe, PipeKind
 from tqec.utils.enums import Basis
-from tqec.utils.exceptions import TQECException
 from tqec.utils.position import Direction3D, Position3D
 
 
@@ -66,16 +65,4 @@ def test_pipe() -> None:
     )
     assert pipe.direction == Direction3D.X
     assert pipe.u.position < pipe.v.position
-    pipe.check_compatible_with_cubes()
     assert list(iter(pipe)) == [pipe.u, pipe.v]
-
-
-def test_pipe_compatible() -> None:
-    pipe = Pipe(
-        Cube(Position3D(1, 0, 0), ZXCube.from_str("XXZ")),
-        Cube(Position3D(0, 0, 0), ZXCube.from_str("XXZ")),
-        PipeKind.from_str("OZX"),
-    )
-
-    with pytest.raises(TQECException, match="The pipe is not compatible"):
-        pipe.check_compatible_with_cubes()
diff --git a/src/tqec/interop/collada/read_write_test.py b/src/tqec/interop/collada/read_write_test.py
index bd0e29d5..3e44d3a6 100644
--- a/src/tqec/interop/collada/read_write_test.py
+++ b/src/tqec/interop/collada/read_write_test.py
@@ -30,12 +30,12 @@ def rotated_cnot(observable_basis: Basis | None = None) -> BlockGraph:
     nodes = [
         (Position3D(0, 0, 1), "P", "In_Control"),
         (Position3D(0, 1, 1), "ZXX", ""),
-        (Position3D(0, 2, 1), "ZXX", ""),
+        (Position3D(0, 2, 1), "ZZX", ""),
         (Position3D(0, 3, 1), "P", "Out_Control"),
         (Position3D(0, 1, 0), "ZXX", ""),
         (Position3D(0, 2, 0), "ZZX", ""),
         (Position3D(1, 0, 0), "P", "In_Target"),
-        (Position3D(1, 1, 0), "ZXX", ""),
+        (Position3D(1, 1, 0), "ZZX", ""),
         (Position3D(1, 2, 0), "ZZX", ""),
         (Position3D(1, 3, 0), "P", "Out_Target"),
     ]