## `eigenkit.orthogonal.topology`

Gate layouts of orthogonal networks built from RBS (Givens) rotations.

A `Topology` says which pairs of wires each layer of RBS gates acts on. It holds only data and uses no numerical library. The same topology gives a dense orthogonal matrix (`orthogonal_matrix`), a quantum circuit and a PyTorch module, so the three views always agree on the order of the gates and of the angles.

The pyramid, butterfly and X layouts are the three quantum orthogonal layers of Cherrat et al., "Quantum Vision Transformers", Quantum 8, 1265 (2024), Figs. 7-9 and Table 1. The diagonal layout is one diagonal of the X circuit, which the same paper ran on hardware as the "\\ circuit". The brick layout alternates even and odd nearest-neighbour pairs.

Example

```python
from eigenkit.orthogonal import butterfly, pyramid, topology

t = butterfly(8)
t.n_angles, t.depth  # (12, 3)
pyramid(8).n_angles  # 28
topology("x", 8).depth  # 7
```

### `Topology`

The gate layout of an orthogonal network on `n` wires.

Each layer is a tuple of wire pairs `(i, j)` with `i < j`. The pairs of one layer are disjoint, so their RBS gates commute and run in parallel. Within a layer the pairs are sorted by `i`. The angles of the network are laid out layer by layer and, inside a layer, in the order of the pairs, which is the order `orthogonal_matrix` and the circuit blocks read them in.

`reflection=True` adds a final Z gate on the last wire. On the unary basis it negates the last row of the matrix, so the network reaches orthogonal matrices with determinant -1 (Cherrat et al., Appendix B).

Attributes:

| Name         | Type                                      | Description                                                                                                                                     |
| ------------ | ----------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------- |
| `n`          | `int`                                     | The number of wires: qubits for the circuit, rows and columns of the matrix.                                                                    |
| `layers`     | `tuple[tuple[tuple[int, int], ...], ...]` | The pairs of each layer, in the order the layers are applied. A wire may be any integer type and is stored as int; a float raises a ValueError. |
| `name`       | `str`                                     | A label, used in repr and error messages.                                                                                                       |
| `reflection` | `bool`                                    | Whether a final Z gate acts on the last wire. Default: False.                                                                                   |

#### `depth`

The number of layers of RBS gates. The final Z gate is not counted.

#### `n_angles`

The number of RBS gates, which is the number of angles.

#### `nearest_neighbour`

Whether every gate acts on adjacent wires `(i, i + 1)`.

#### `pairs()`

Every pair, in the order of the angles.

### `brick(n, depth)`

The brick-wall layout: nearest-neighbour pairs, even and odd layers in turn.

Layer `$t$` holds the pairs `$(i, i + 1)$` with `$i \equiv t \pmod 2$`. For `$n = 2$`, which has no odd pair, every layer is the pair `$(0, 1)$`.

Parameters:

| Name    | Type  | Description                       | Default    |
| ------- | ----- | --------------------------------- | ---------- |
| `n`     | `int` | The width, at least 2.            | *required* |
| `depth` | `int` | The number of layers, at least 1. | *required* |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description                                        |
| ------------ | -------------------------------------------------- |
| `ValueError` | If n is smaller than 2 or depth is smaller than 1. |

### `butterfly(n)`

The butterfly layout of Cherrat et al. (Fig. 8), the Cooley-Tukey FFT pattern.

Level `$l$` pairs every wire `$i$` with `$i \oplus 2^l$` (bitwise XOR). The levels run from 0 to `$\log_2 n - 1$`, so the first level couples neighbours and the last one couples wires `$n / 2$` apart. Fig. 8 draws the levels in the opposite order; the two are the same network up to reversing the bits of the wire index.

It has `$(n / 2) \log_2 n$` angles and depth `$\log_2 n$`, and needs gates between distant wires.

Parameters:

| Name | Type  | Description                              | Default    |
| ---- | ----- | ---------------------------------------- | ---------- |
| `n`  | `int` | The width, a power of two of at least 2. | *required* |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description                               |
| ------------ | ----------------------------------------- |
| `ValueError` | If n is not a power of two of at least 2. |

Example

```python
from eigenkit.orthogonal import butterfly

butterfly(4).layers  # (((0, 1), (2, 3)), ((0, 2), (1, 3)))
```

### `butterfly_pairs(n, level)`

The pairs of one butterfly level: `(i, i | 2**level)` for every `i` without that bit, sorted by `i`.

Parameters:

| Name    | Type  | Description                              | Default    |
| ------- | ----- | ---------------------------------------- | ---------- |
| `n`     | `int` | The width, a power of two of at least 2. | *required* |
| `level` | `int` | The level, from 0 to (\\log_2 n - 1).    | *required* |

Returns:

| Type    | Description                                                            |
| ------- | ---------------------------------------------------------------------- |
| `Layer` | tuple\[tuple[int, int], ...\]: The n // 2 disjoint pairs of the level. |

Raises:

| Type         | Description                                                         |
| ------------ | ------------------------------------------------------------------- |
| `ValueError` | If n is not a power of two of at least 2, or level is out of range. |

### `diagonal(n)`

One diagonal of the X layout, the "\\ circuit" of Cherrat et al.

Layer `$t$` holds the single pair `$(t, t + 1)$`. It has `$n - 1$` angles and depth `$n - 1$`, and uses only adjacent wires.

Parameters:

| Name | Type  | Description            | Default    |
| ---- | ----- | ---------------------- | ---------- |
| `n`  | `int` | The width, at least 2. | *required* |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description             |
| ------------ | ----------------------- |
| `ValueError` | If n is smaller than 2. |

### `pyramid(n, reflection=False)`

The pyramid layout of Landman et al. (Cherrat et al., Fig. 7).

Layer `$t$` holds the pairs `$(i, i + 1)$` with `$i \equiv t \pmod 2$` and `$i \le \min(t, 2n - 4 - t)$`. The first gate acts on wires 0 and 1, and the apex of the pyramid is the gate on the last two wires.

It has `$n(n - 1)/2$` angles and depth `$2n - 3$`, uses only adjacent wires, and reaches every rotation in `$\mathrm{SO}(n)$`. With `reflection=True` a final Z gate on the last wire extends it to all of `$\mathrm{O}(n)$`.

Parameters:

| Name         | Type   | Description                                                       | Default    |
| ------------ | ------ | ----------------------------------------------------------------- | ---------- |
| `n`          | `int`  | The width, at least 2.                                            | *required* |
| `reflection` | `bool` | Whether to add the final Z gate on the last wire. Default: False. | `False`    |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description             |
| ------------ | ----------------------- |
| `ValueError` | If n is smaller than 2. |

### `topology(name, n, **kwargs)`

Build a named layout.

Parameters:

| Name       | Type           | Description                                                                              | Default    |
| ---------- | -------------- | ---------------------------------------------------------------------------------------- | ---------- |
| `name`     | `TopologyName` | One of "butterfly", "pyramid", "x", "diagonal" and "brick".                              | *required* |
| `n`        | `int`          | The width.                                                                               | *required* |
| `**kwargs` | `Any`          | Passed to the factory, such as reflection for the pyramid or depth for the brick layout. | `{}`       |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description                                                      |
| ------------ | ---------------------------------------------------------------- |
| `ValueError` | If name is not a known layout, or "brick" comes without a depth. |

### `x(n)`

The X layout of Cherrat et al. (Fig. 9): the two diagonals of the pyramid.

Layer `$t$` holds the pairs `$(t, t + 1)$` and `$(n - 2 - t, n - 1 - t)$`. The two diagonals cross in the middle layer, where they share one gate.

It has `$2n - 3$` angles and depth `$n - 1$`, and uses only adjacent wires.

`n` must be even. Cherrat et al. define the X layout only for even widths, and for odd `n` no nearest-neighbour layout of depth `$n - 1$` connects every input wire to every output wire: the two diagonals would need the middle wire in the same layer. For an odd width, use `pyramid` or `diagonal`, which accept any `n`, or pad the width to an even number yourself.

Parameters:

| Name | Type  | Description                              | Default    |
| ---- | ----- | ---------------------------------------- | ---------- |
| `n`  | `int` | The width, an even number of at least 2. | *required* |

Returns:

| Name       | Type       | Description |
| ---------- | ---------- | ----------- |
| `Topology` | `Topology` | The layout. |

Raises:

| Type         | Description                    |
| ------------ | ------------------------------ |
| `ValueError` | If n is odd or smaller than 2. |
