Repository: tqec/tqec

Issue:
Enable import of rotated SketchUp 3D structures
**Problem**
You can rotate structures in SketchUp, but you cannot import rotated structures to TQEC. This is inconvenient if thinking about whole structures (currently: go back to SketchUp, rotate, and re-export) and more than inconvenient when only parts of a structure are rotated (currently: manually delete each rotated element in SketchUp, replace with the unrotated equivalent, re-export).

*[Labelled as a good first issue because it does not require full knowledge of operations taking place after import. It is also, well, my first issue.]*

**General proposed approach**
The general proposed solution is relatively straightforward:
1. Modify existing error handling [here](https://github.com/tqec/tqec/blob/64c0031cee9457d1162bac5b0a9cf798eecb0b3e/src/tqec/interop/collada/read_write.py#L96) to let rotations pass while still catching illegal rotations. 
2. Create a new function (I like functions) or class to get rotational information for each node and:
  2.1 If the node is not rotated: carry on.
  2.2 If the node is rotated: exchange node for the un-rotated equivalent.
3. Handle cases when a rotated block/pipe fails to clear TQEC's "round to integer" checks or adjust the said checks. 

**Syntax challenges**
I think understanding syntax is key for this issue. 

SketchUp encodes shapes and rotations into a matrix which, as far as I can tell, follows a standard [OpenGL syntax](https://community.khronos.org/t/get-direction-from-transformation-matrix-or-quat/65502/2). I like to think of it as having a box in front of me, with a corner designated as the origin (position given in 4th column) and 3 vectors projecting shape right/left, up/down, front/back (the first 3x3 bit).

```
[X.x] [X.y] [X.z] [POS.x]
[Y.x] [Y.y] [Y.z] [POS.y]
[Z.x] [Z.y] [Z.z] [POS.Z]
[    ] [    ] [    ] [US   ]
```
You don't need degree rotations to rotate anything. You just change the 3x3 vectors to get the box to "grow" in a different direction. So, for instance, below, a "zxo" block unrotated, and rotated. Note that the "url/ID" remains. This *is** the essence of the challenge. When creating the block/pipe, what matters for blockgraph is the ID/name, which does NOT change when you rotate things in SketchUp.

``` xml

<node id="ID2" name="instance_0">
    <matrix>  <!-- TQEC uses this to confirm shape is valid and get origin (4th column) information. -->
        1 0 0 0
        0 1 0 0
        0 0 1 0
        0 0 0 1
    </matrix>
  <instance_node url="#ID3" /> <!-- This links to blockgraph-compatible naming conventions. -->
</node>
  <node id="ID32" name="instance_1">
      <matrix>
          1 0 0 0
          0 0 1 0
          0 1 0 0
          0 0 0 1
      </matrix>
<instance_node url="#ID3" /> <!-- This links to blockgraph-compatible naming conventions. -->

<!-- Bunch of other things omitted -->

<library_nodes>
        <node id="ID3" name="zxo"> <!-- TQEC uses this to create actual block/pipe. -->

<!-- Bunch of other things omitted -->

```

## Action plan
I reckon best to take it in steps. It's a big challenge. The number of rotations possible is considerable. 

So, if there's agreement with the above, the first step would be to modify existing health checks:
- Modify but ultimately leave the current [identify check](https://github.com/tqec/tqec/blob/64c0031cee9457d1162bac5b0a9cf798eecb0b3e/src/tqec/interop/collada/read_write.py#L96) there to clear any non-rotations.
- If the identity check fails, examine more closely: 
  - Simplify matrix: Set origin as 0,0,0 and calculate directional vectors from there.
  - Reject if:
    - More than a single "1" or "-1" in any directional vector (each row in the first 3x3 bit) (object is sheared or scaled).
    - Any non-unit (1 or -1) rotation (these are partial rotations).

**Some footnotes**
- The likelihood of mistakes in the above is not non-existent. Correct at will – would save a lot of pain coding.
- I am assuming textures and other graphical details in the .dae file are essentially irrelevant for blockgraph. If this is NOT the case, things get far more complicated.
- I have some ideas but do not yet know what's the best way to match rotation to appropriate names/identities.

Hints from issue comments:
@nelimee: A few comments:

> rotations possible is considerable

Yes, but not really. Once you have correctly implement 3 rotations (+pi/2 around each of the 3 axes), you can build all the other valid rotations by repeating zero, once, twice or three times the +pi/2 rotation. It can be reduced even further because for anything that is not a Hadamard pipe: 

- a rotation of 3pi/2 is equivalent to a rotation of pi/2,
- a rotation of 2pi/2 = pi is equivalent to the identity.

> * I am assuming textures and other graphical details in the .dae file are essentially irrelevant for blockgraph. If this is NOT the case, things get far more complicated.

That seems to be a valid assumption. @inmzhang would know better than me though.

> I have some ideas but do not yet know what's the best way to match rotation to appropriate names/identities.

A function with the following signature should be enough to cover all the cases in my opinion:
```py
from typing import Literal

from tqec.utils.position import Direction3D

L = Literal["X", "Z", "O"]


def rotate(
    spec: tuple[L, L, L, Literal["H"] | None],
    axis: Direction3D,
    angle_pi_2: Literal[0, 1, 2, 3],
) -> tuple[L, L, L, Literal["H"] | None]:
    pass
```@jbolns: > Yes, but not really... 

Touché. We might have a different personal entry threshold for using the word "many" =D, but yes.

Thanks for the function suggestion. To avoid misunderstanding you due to function names, you mean this(https://github.com/tqec/tqec/blob/64c0031cee9457d1162bac5b0a9cf798eecb0b3e/src/tqec/position.py#L144) Direction3D or a separate to implement?
@nelimee: This `Direction3D` seems enough. Ideally it would be better named `Axis`, but:

- this will not be a function in the user API, so we can be a little more flexible on naming,
- `Direction3D` is also a good-enough naming, and it is clear that this is a 3-dimensional object,
- I do not see enough added value to create another structure just to represent an `Axis`.@inmzhang: > I am assuming textures and other graphical details in the .dae file are essentially irrelevant for blockgraph. If this is NOT the case, things get far more complicated.

When parsing a `BlockGraph` from a `.dae` file, the geometries and materials are irrelevant.

Thanks for the issue!@jbolns: Actually, come to think about it ( thanks @nelimee )... If angles need to be calculated anyway, might as well do it from the outset. So, same same, but using this from the beginning:

```
# Quick calculation of [rot_x, rot_y, rot_z] rotations against the identity
def calc_rotations_from_identity(B):
    rotations = []
    A = np.identity(3, dtype=int)
    for i, row in enumerate(B):
        cos_theta = np.dot(A[i], row) / (np.linalg.norm(A[i]) * np.linalg.norm(row))
        rads = np.arccos(np.clip(cos_theta, -1.0, 1.0))
        degs = np.degrees(rads)
        rotations.append(round(degs))
    return rotations

# Test 
B = np.array([
    [1, 0, 0, 0],
    [0, 0, -1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1]
    ])[:3, :3]

rotations = calc_rotations_from_identity(B)
print(rotations)  # (In this particular case) [0, 90, 0]
```

Due to how the foundational .dae matrix is built, (I think) rot_x, rot_y, rot_z will always be between 0 and 90. So, no need to worry about n*pi/2 rotations. Pass 90 (plus minus tolerance), reject the rest.

Health checks using the "rotations" array, then the other steps but having the rotations already in hand.

I think...@jbolns: ## Simple rotations enabled

I published a [new branch](https://github.com/tqec/tqec/tree/rotated_imports) that already enables import of rotated structures (simple cases). 
- Changes do NOT affect import of **un**rotated structures. These simply go through. 
- More tests needed, but need to clarify some things (below) before.

**Approach**
The approach is more algebraic than what I imagined and anything discussed above. 
1. Check for valid rotations using angles (supported in a function in `src\tqec\utils\rotations.py`). 
2. Rotate names algebraically using the rotation matrix (supported in a function in `src\tqec\utils\rotations.py`).

Apologies if the change of approach comes as a surprise. Everything above and a chat with @nelimee got me thinking. Idea then just came up, so I figured why not test it.

**Further testing**
I tested it a little. The rotated `.dae` in the assets folder works (at least on my computer, lol). Import succeeds. It is a simple structure with a simply rotation, but it works.

To run more tests I need to ask about the "round_or_fail" operation. It's giving me headaches even with **un**rotated structures.

I need to understand the purpose of this rounding better and, in particular, why the tolerance is so tiny.@nelimee: > To run more tests I need to ask about the "round_or_fail" operation. It's giving me headaches even with **un**rotated structures.
> 
> I need to understand the purpose of this rounding better and, in particular, why the tolerance is so tiny.

The original purpose of `round_or_fail` was to round floating point values that were supposed to be integers. These values came from the output of `LinearFunction.__call__`. We use `LinearFunction` to represent how a given quantity scales (mostly used for the shape of scalable `Template` instances, but also used for the number of repetitions of a given layer). 
For a reason I cannot remember exactly (maybe due to the computation of `intersection`?), we went from "a `LinearFunction` has a `slope` and an `offset` that are integers and are only defined over integers" to "`LinearFunction` instances have a `slope` and `offset` that can be floating points, are defined over `R`, and so return floating point numbers when evaluated". That change led to most (all?) of the `LinearFunction` instances used in `tqec` returning a floating-point number that is supposed to "exactly" (per floating-point definition) be an integer. Basically, we traded `2 * k + 2` with `k` an integer to `2.0 * k + 2.0` with `k` a floating-point number that is obtained from an integer. So the results of `LinearFunction.__call__` where floating-point numbers that were supposed to be **very** close to integers (or exactly the integer if the floating-point representation allows it). Hence the very small tolerance.@afowler: I expect the reason the tolerance is so tiny is because rotation was never
done before so decimal places were less likely to deviate significantly
from integer. We do of course want everything to be nice and straight and
integer coordinate described after rounding for easy import. I suspect you
can make the tolerance a bit bigger + achieve this rounding consistently,
even when rotations are used.

On Sat, Feb 1, 2025, 7:27 AM J ***@***.***> wrote:

> Simple rotations enabled
>
> I published a new branch
> <https://github.com/tqec/tqec/tree/rotated_imports> that already enables
> import of rotated structures (simple cases).
>
>    - Changes do NOT affect import of *un*rotated structures. These simply
>    go through.
>    - More tests needed, but need to clarify some things (below) before.
>
> *Approach*
> The approach is more algebraic than what I imagined and anything discussed
> above.
>
>    1. Check for valid rotations using angles (supported in a function in
>    src\tqec\utils\rotations.py).
>    2. Rotate names algebraically using the rotation matrix (supported in
>    a function in src\tqec\utils\rotations.py).
>
> Apologies if the change of approach comes as a surprise. Everything above
> and a chat with @nelimee <https://github.com/nelimee> got me thinking.
> Idea then just came up, so I figured why not test it.
>
> *Further testing*
> I tested it a little. The rotated .dae in the assets folder works (at
> least on my computer, lol). Import succeeds. It is a simple structure with
> a simply rotation, but it works.
>
> To run more tests I need to ask about the "round_or_fail" operation. It's
> giving me headaches even with *un*rotated structures.
>
> I need to understand the purpose of this rounding better and, in
> particular, why the tolerance is so tiny.
>
> —
> Reply to this email directly, view it on GitHub
> <https://github.com/tqec/tqec/issues/458#issuecomment-2628995225>, or
> unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAKAXTA2GIFFO4EO6PTCJCT2NTRURAVCNFSM6AAAAABWE37VACVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDMMRYHE4TKMRSGU>
> .
> You are receiving this because you are subscribed to this thread.Message
> ID: ***@***.***>
>
@jbolns: New commit pushed to [rotated_imports](https://github.com/tqec/tqec/tree/rotated_imports) branch. It enables imports of CNOTs rotated along all axes (x,y,z) and with all valid degree factors (90,180, 270).

Ran some tests.

Import and visualisation come out quite fine:
- Small matter with positioning along the main axis: the whole thing is shifted by a cube due to how the cubes are scaled.
- I'm not sure if this needs to be changed at all, as the structure is imported. 
- Additional robustness tests pending. 

Computations is a mixed bag:
- The following operations succeed (although I did not have time before today's meeting to check results in detail):
    - block_graph_rotated = BlockGraph.from_dae_file("assets/cnot_rotate_x_90.dae")´
    - correlation_surfaces_rotated = block_graph_rotated.find_correlation_surfaces()
    - compiled_computation_rotated = compile_block_graph(block_graph, observables=[correlation_surfaces[1]])
    - circuit_rotated = compiled_computation_rotated.generate_stim_circuit( ... )
- There is an error with sinter.plot_error_rate( ... )@jbolns: I'm not sure I have kept this sufficiently updated, so, update.

**Imports** more or less work now. Still running some tests before calling it, especially concerning that one line of code I mentioned in the call was bothering me a little despite seemingly working find.

**Simulations** still have some obstacles to figure out. There are two types of issues.

*Structures WITHOUT spatial cubes*
- Cube_specs is built [here](https://github.com/tqec/tqec/blob/6bd03ffc9bc8c4ef6b3d0e55ca3cfe1367c0f162/src/tqec/compile/compile.py#L336) using real rotated positions. E.g.: one of the specs in a CNOT rotated 180 degrees is: ZXX(0,0,-2).
- The "shift_to_min" [here](https://github.com/tqec/tqec/blob/6bd03ffc9bc8c4ef6b3d0e55ca3cfe1367c0f162/src/tqec/computation/block_graph.py#L222) re-writes the position. E.g.: the re-written position for that block is: ZXX(0,0,2).
- When you get to [here](https://github.com/tqec/tqec/blob/6bd03ffc9bc8c4ef6b3d0e55ca3cfe1367c0f162/src/tqec/compile/compile.py#L345), the `spec = cube_specs[cube]` bit does not work because ZXX(0,0,2) != ZXX(0,0,-2)

*Structures WITH spatial cubes*
- To get to the above, cubes need to be returned from [here](https://github.com/tqec/tqec/blob/6bd03ffc9bc8c4ef6b3d0e55ca3cfe1367c0f162/src/tqec/compile/specs/base.py#L48) as not spatial cubes.
- When a structure has a XXZ or ZZX, TQEC tries to find the edges for those cubes, [here](https://github.com/tqec/tqec/blob/6bd03ffc9bc8c4ef6b3d0e55ca3cfe1367c0f162/src/tqec/computation/_base_graph.py#L165).
- At this point, things get a little weird.
  - It won't find the edge between spatial nodes because it looks for edges that do not exist (so, for instance, beyond the structure).
  - My initial knee-jerk reaction is that, if time dimension changes from Z to something else, shouldn't the KIND corresponding to a spatial cubes need to change too?@inmzhang: The issue is that the `BlockGraph` is being shifted internally during compilation, but the `CorrelationSurface` is not. This is a bug. I previously fixed it in a commit within a closed PR: https://github.com/tqec/tqec/pull/437/commits/7d529859a663eebf01705eb772a818a7908ed5f3. Forgot to raise an issue then...

For now, don’t worry about the 90-degree simulation since the spatial cube compilation isn’t completed yet.@jbolns: Yeah, shifting both things should do the trick. 
Then I think we're sort of done, pending a few more tests with that line that's bugging me (but even if I find something here, the solution is as simple as lifting that line into a function of its own).@inmzhang: J, would it possible for you to review [this PR](https://github.com/tqec/tqec/pull/477) that fixes the correlation surface shift?

Solution patch:
diff --git a/src/tqec/compile/compile.py b/src/tqec/compile/compile.py
index ede2e3bd..803eaf40 100644
--- a/src/tqec/compile/compile.py
+++ b/src/tqec/compile/compile.py
@@ -8,6 +8,7 @@ from typing import Literal, Sequence, cast
 
 import stim
 
+from tqec.computation.zx_graph import ZXEdge, ZXNode
 from tqec.utils.coordinates import StimCoordinates
 from tqec.circuit.measurement_map import MeasurementRecordsMap
 from tqec.circuit.qubit_map import QubitMap
@@ -333,13 +334,15 @@ def compile_block_graph(
         raise TQECException(
             "Can not compile a block graph with open ports into circuits."
         )
-    cube_specs = {
-        cube: CubeSpec.from_cube(cube, block_graph) for cube in block_graph.nodes
-    }
 
     # 0. Set the minimum z of block graph to 0.(time starts from zero)
+    shift_z = -min(cube.position.z for cube in block_graph.nodes)
     block_graph = block_graph.shift_min_z_to_zero()
 
+    cube_specs = {
+        cube: CubeSpec.from_cube(cube, block_graph) for cube in block_graph.nodes
+    }
+
     # 1. Get the base compiled blocks before applying the substitution rules.
     blocks: dict[Position3D, CompiledBlock] = {}
     for cube in block_graph.nodes:
@@ -380,9 +383,33 @@ def compile_block_graph(
     if observables is not None:
         if observables == "auto":
             observables = block_graph.find_correlation_surfaces()
+        # need to shift the provided correlation surfaces if the block graph is shifted.
+        elif shift_z != 0:
+            observables = [
+                _shift_z_of_correlation_surface(observable, shift_z)
+                for observable in observables
+            ]
         obs_included = [
             compile_correlation_surface_to_abstract_observable(block_graph, surface)
             for surface in observables
         ]
 
     return CompiledGraph(layout_slices, obs_included)
+
+
+def _shift_z_of_correlation_surface(
+    correlation_surface: CorrelationSurface, shift_z: int
+) -> CorrelationSurface:
+    """Shift the z coordinate of the nodes in the correlation surface by the specified amount."""
+
+    def _shift_node(node: ZXNode) -> ZXNode:
+        return ZXNode(node.position.shift_by(dz=shift_z), node.kind, node.label)
+
+    def _shift_edge(edge: ZXEdge) -> ZXEdge:
+        return ZXEdge(_shift_node(edge.u), _shift_node(edge.v), edge.has_hadamard)
+
+    return CorrelationSurface(
+        nodes=frozenset(_shift_node(node) for node in correlation_surface.nodes),
+        span=frozenset(_shift_edge(edge) for edge in correlation_surface.span),
+        external_stabilizer=correlation_surface.external_stabilizer,
+    )
diff --git a/src/tqec/computation/block_graph.py b/src/tqec/computation/block_graph.py
index b6f39d86..00b3ae7b 100644
--- a/src/tqec/computation/block_graph.py
+++ b/src/tqec/computation/block_graph.py
@@ -231,6 +231,10 @@ class BlockGraph(ComputationGraph[Cube, Pipe]):
         if minz == 0:
             return deepcopy(self)
         new_graph = BlockGraph(self.name)
+        for cube in self.nodes:
+            new_graph.add_node(
+                Cube(cube.position.shift_by(dz=-minz), cube.kind, cube.label)
+            )
         for pipe in self.edges:
             u, v = pipe.u, pipe.v
             new_graph.add_edge(


Test patch:
diff --git a/src/tqec/compile/compile_test.py b/src/tqec/compile/compile_test.py
index 3f49d130..15c80b2e 100644
--- a/src/tqec/compile/compile_test.py
+++ b/src/tqec/compile/compile_test.py
@@ -23,6 +23,19 @@ SPECS: dict[str, tuple[BlockBuilder, SubstitutionBuilder]] = {
 }
 
 
+def test_shift_min_z_to_zero_during_compilation() -> None:
+    g = BlockGraph()
+    g.add_node(Cube(Position3D(0, 0, 1), ZXCube.from_str("ZXZ")))
+
+    correlation_surface_before_shift = g.find_correlation_surfaces()
+    compiled_graph = compile_block_graph(
+        g, observables=correlation_surface_before_shift
+    )
+    observables = compiled_graph.observables
+    assert len(observables) == 1
+    assert list(observables[0].top_readout_cubes)[0].position == Position3D(0, 0, 0)
+
+
 @pytest.mark.parametrize(
     ("spec", "kind", "k"),
     itertools.product(SPECS.keys(), ("ZXZ", "ZXX", "XZX", "XZZ"), (1,)),
diff --git a/src/tqec/computation/block_graph_test.py b/src/tqec/computation/block_graph_test.py
index 9b1f9b20..41e87b37 100644
--- a/src/tqec/computation/block_graph_test.py
+++ b/src/tqec/computation/block_graph_test.py
@@ -140,6 +140,12 @@ def test_block_graph_validate_color_match() -> None:
 
 
 def test_shift_min_z_to_zero() -> None:
+    g = BlockGraph()
+    g.add_node(Cube(Position3D(0, 0, 1), ZXCube.from_str("ZXZ")))
+    shifted = g.shift_min_z_to_zero()
+    assert shifted.num_nodes == 1
+    assert shifted.nodes[0].position == Position3D(0, 0, 0)
+
     g = BlockGraph()
     g.add_edge(
         Cube(Position3D(0, 0, -1), ZXCube.from_str("ZXZ")),