# Orthogonal Networks

An **orthogonal network** is a circuit of RBS gates. An RBS gate acts on two wires `$(i, j)$`, `$i < j$`: it rotates the states `$|01\rangle$` and `$|10\rangle$` by an angle `$\theta$` and leaves `$|00\rangle$` and `$|11\rangle$` alone. On those two states it is the Givens rotation

```math
\mathrm{RBS}(\theta) =
\begin{pmatrix} \cos\theta & \sin\theta \\ -\sin\theta & \cos\theta \end{pmatrix}
```

(Cherrat et al., Quantum 2024, Eq. 1). RBS gates keep the number of 1s fixed, so on the **unary basis**, where exactly one wire is 1, a network of them acts as an `$n \times n$` orthogonal matrix. The matrix stays orthogonal for every value of the angles: there is no constraint to enforce, and the angles train with any optimiser.

`eigenkit.orthogonal` uses only NumPy and needs no other framework. One layout gives two views that agree exactly:

- the **matrix**, `orthogonal_matrix(topology, theta)`, a dense NumPy array;
- the **circuit**, the `RBSNetwork` block, which runs on every provider.

## Topologies

A `Topology` lists the pairs of wires that each layer of gates acts on. The pairs of one layer are disjoint, so their gates run in parallel. The angles are laid out layer by layer and, inside a layer, in the order of the pairs.

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

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

| Factory           | Angles                             | Depth              | Width `$n$`          | Wires used |
| ----------------- | ---------------------------------- | ------------------ | -------------------- | ---------- |
| `butterfly(n)`    | `$(n/2)\log_2 n$`                  | `$\log_2 n$`       | a power of two       | any pair   |
| `pyramid(n)`      | `$n(n-1)/2$`                       | `$2n-3$`           | any, at least 2      | adjacent   |
| `x(n)`            | `$2n-3$`                           | `$n-1$`            | **even**, at least 2 | adjacent   |
| `diagonal(n)`     | `$n-1$`                            | `$n-1$`            | any, at least 2      | adjacent   |
| `brick(n, depth)` | about `$(n/2)\cdot\mathrm{depth}$` | `$\mathrm{depth}$` | any, at least 2      | adjacent   |

The butterfly, pyramid and X rows are the three quantum orthogonal layers of Cherrat et al. (Table 1, Figs. 7-9). The pyramid comes from Landman et al. (Quantum 2022) and reaches every rotation in `$\mathrm{SO}(n)$`; `pyramid(n, reflection=True)` adds a final Z gate on the last wire, which reaches the matrices with determinant `$-1$` too, so all of `$\mathrm{O}(n)$`. The brick layout alternates the even pairs `$(0, 1), (2, 3), \dots$` and the odd pairs `$(1, 2), (3, 4), \dots$`, so its layers hold `$\lfloor n/2 \rfloor$` and `$\lfloor (n-1)/2 \rfloor$` gates in turn; for `$n = 2$` every layer is the pair `$(0, 1)$`. The diagonal layout is one diagonal of X, which Cherrat et al. ran on hardware as the "\\ circuit". You can also build a `Topology` from your own layers.

X needs an even width

`x(n)` raises a `ValueError` for an odd `$n$`. Cherrat et al. define the X layout only for even widths, and for an odd width no layout of adjacent gates with 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(n)` or `diagonal(n)`, which accept any `$n$`, or pad the width to an even number.

The butterfly needs a power-of-two width and never pads it: any other width raises a `ValueError`.

## The matrix

`orthogonal_matrix(topology, theta)` starts from the identity and applies the layers in order, updating the two rows of every pair of a layer at once. The cost is `$O(\mathrm{depth}\cdot n^2)$`. Zero angles give the identity, which `identity_angles(topology)` returns.

```python
import numpy as np

from eigenkit.orthogonal import orthogonal_matrix, orthogonal_matrix_jacobian, x

t = x(6)
theta = np.random.default_rng(0).normal(size=t.n_angles)
W = orthogonal_matrix(t, theta)
np.allclose(W.T @ W, np.eye(6))  # True
dW = orthogonal_matrix_jacobian(t, theta)  # shape (n_angles, 6, 6)
```

## The circuit

`RBSNetwork(topology)` is a block, so it combines with the other blocks through `Circuit` and `assemble`. It takes one trainable weight per gate. Each RBS gate on wires `$(i, j)$` is built from gates every backend runs:

```math
\mathrm{RBS}_{ij}(\theta) =
H_i \, \mathrm{CNOT}_{ij} \, H_j \, R_Y^{(i)}(-\theta) \, R_Y^{(j)}(\theta) \,
H_j \, \mathrm{CNOT}_{ij} \, H_i
```

Each angle enters only `RY` rotations, so the two-term parameter-shift rule gives its exact gradient.

Qubit 0 is the most significant bit of the statevector, so the unary state with wire `$k$` set is the basis state `$2^{\,n-1-k}$`. Started on wire `$c$`, the network leaves the amplitude `$W_{rc}$` on wire `$r$`, on every provider.

To feed a vector in, put a `UnaryLoader` in front. It applies an X gate and then `$n - 1$` RBS gates, and loads `$x / \lVert x \rVert$` into the unary basis (Johri et al., 2021). Its angles are non-linear functions of `$x$`, so the block takes them as inputs, and `unary_loader_angles(x, layout)` computes them. The three layouts are those of Cherrat et al., Fig. 14:

| `layout`          | Depth        | Width `$n$`    | Wires used |
| ----------------- | ------------ | -------------- | ---------- |
| `"parallel"`      | `$\log_2 n$` | a power of two | any pair   |
| `"diagonal"`      | `$n - 1$`    | any            | adjacent   |
| `"semi_diagonal"` | `$n / 2$`    | even           | adjacent   |

`unary_readout(n)` gives the observables `$Z_0, \dots, Z_{n-1}$`, and `unary_probabilities` turns their values into the probability of each wire,

```math
p_i = \frac{1 - \langle Z_i \rangle}{2} = \frac{(Wx)_i^2}{\lVert x \rVert^2}.
```

With zero angles `$W = I$`, so this circuit returns `$x_i^2 / \lVert x \rVert^2$`:

```python
import numpy as np

from eigenkit import Circuit
from eigenkit.orthogonal import (
    RBSNetwork,
    UnaryLoader,
    butterfly,
    unary_loader_angles,
    unary_probabilities,
    unary_readout,
)

t = butterfly(8)
circuit = Circuit(
    [UnaryLoader(8, layout="parallel"), RBSNetwork(t)],
    observables=unary_readout(8),
)
x = np.random.default_rng(1).normal(size=8)
theta = np.zeros(t.n_angles)
p = unary_probabilities(circuit(theta, unary_loader_angles(x, layout="parallel")))
```

### From trained angles to a circuit

`to_block(topology, theta)` fixes the angles as constants, and `to_circuit(topology, theta, loader="diagonal", provider=...)` builds the whole circuit: loader, network and readout. Its inputs are the loader angles, and it runs on any provider, a simulator or hardware. To train the angles of the circuit itself, as a layer of a PyTorch model, use `OrthogonalQNN` (see [Layers](https://docs.kit.eigenorbit.com/user-guide/layers/#orthogonalqnn)).

```python
import numpy as np

from eigenkit.orthogonal import (
    orthogonal_matrix,
    pyramid,
    to_circuit,
    unary_loader_angles,
    unary_probabilities,
)

t = pyramid(4)
theta = np.random.default_rng(0).normal(size=t.n_angles)
x = np.array([1.0, 2.0, -0.5, 0.3])
circuit = to_circuit(t, theta)
p = unary_probabilities(circuit(np.zeros(0), unary_loader_angles(x)))
np.allclose(p, (orthogonal_matrix(t, theta) @ x) ** 2 / (x @ x))  # True
```

## PyTorch modules

`eigenkit.orthogonal.torch` needs the `torch` extra. Its modules hold the angles as an `nn.Parameter` and rebuild the matrix from them, so it is orthogonal at every training step, with no projection and no penalty:

- `Orthogonal(n, topology="butterfly", init="identity")` provides `matrix()` and rotates an input along one axis, `forward(x, dim=-1)`: a batch `(B, n)`, or a feature map `(B, n, H, W)` with `dim=1`.
- `OrthogonalConv1x1(n, bias=True)` is an orthogonal 1x1 convolution.
- `PartitionedOrthogonal(width, stages=2)` takes any width: it splits it into powers of two (`$588 = 512 + 64 + 8 + 4$`), rotates each part, and mixes the parts with fixed permutations between stages.

`init="identity"` starts at the identity, and `init="random", std=0.1` draws `torch.randn(n_angles) * std`. In eval mode with autograd off the matrix is cached, and `freeze_matrix()`, or the `frozen()` context, fixes it so that gradients reach only the input, as an input-space attack needs. `singular_values()` and `orthogonality_error()` check the matrix in float64.

```python
import torch

from eigenkit.orthogonal.torch import Orthogonal

rotation = Orthogonal(8, "x", init="random", std=0.5)
x = torch.randn(4, 8)
torch.allclose(rotation(x).norm(dim=1), x.norm(dim=1))  # True
rotation.singular_values()  # (1.0, 1.0) to float32 precision, about 1e-7
```

The default `mode="materialise"` builds the dense matrix, which costs `$O(\mathrm{depth}\cdot n^2)$`, and it is refused with a `ValueError` when `$\mathrm{depth}\cdot n^2 > 2^{31}$`: a pyramid wider than 1024 needs `mode="apply"`, which applies the rotations to the input layer by layer.

Each module documents the exact torch operations it runs, and the tests pin them bit for bit. Changing one of them is a breaking change.

### Orthogonal fine-tuning

`OrthogonalAdapter(layer)` wraps a pretrained `nn.Linear` or `nn.Conv2d`, freezes it, and trains only the angles of a rotation `$R$` of its weight: `$W' = RW$` on the output channels (`side="out"`) or `$W' = WR^\top$` on the input channels (`side="in"`). `$R$` starts at the identity, so the adapted model starts at the pretrained function, and `$RW$` keeps every singular value of `$W$`: the Lipschitz constant of the layer never changes. With the butterfly layout, a width that is not a power of two gets a `PartitionedOrthogonal` automatically.

```python
import torch
import torch.nn as nn

from eigenkit.orthogonal.torch import (
    apply_orthogonal_adapters,
    merge_adapters,
    trainable_parameters,
)

model = nn.Sequential(nn.Linear(16, 32), nn.ReLU(), nn.Linear(32, 10))
apply_orthogonal_adapters(model, ["0", "2"], topology="pyramid")
optimiser = torch.optim.Adam(trainable_parameters(model), lr=1e-2)
# ... train ...
merge_adapters(model)  # plain nn.Linear layers again
```

Train an adapted model with a training loop of your own, as above. The estimators `GenericClassifier` and `GenericRegressor` re-initialise every layer in `fit()` (see [Estimators](https://docs.kit.eigenorbit.com/user-guide/estimators/index.md)), which would replace the pretrained weights with random ones, so an adapter refuses to be re-initialised and `fit()` raises a `RuntimeError`.

`target_modules` takes qualified names or a predicate `(name, module) -> bool`. `fold_bn(conv, bn)` folds an eval-mode BatchNorm into the convolution before it, so that a convolution and its BatchNorm can be adapted as one layer. The [certified fine-tuning example](https://docs.kit.eigenorbit.com/examples/orthogonal-certified-fine-tuning/index.md) compares butterfly adapters with head-only training, LoRA and full fine-tuning from axial to coronal CT slices.

### Certified robustness

An orthogonal network keeps the Lipschitz constant of the model known, and a known Lipschitz constant gives a certificate. If the features in front of a linear head with rows `$w_k$` are `$L$`-Lipschitz, and the logits are `$z$`, no input perturbation of L2 norm below

```math
r = \min_{j \ne p} \frac{z_p - z_j}{L \, \lVert w_p - w_j \rVert}
```

can change the predicted class `$p$`. `eigenkit.orthogonal.torch` has the pieces:

- `LLNHead(in_features, out_features)`, a linear head with unit-norm rows, and `MaxMin(pairing="adjacent" | "halves")`, a 1-Lipschitz activation that keeps the norm. The two pairings are different functions: `"adjacent"` sorts channels `$2k$` and `$2k + 1$` (GroupSort), `"halves"` pairs channel `$k$` with `$k + C/2$` (the MinMax of BRONet).
- `lipschitz_bound(model)`, an upper bound on `$L$` for an `nn.Sequential` of `Linear`, `Conv2d`, orthogonal and 1-Lipschitz layers. An orthogonal adapter leaves it unchanged. A convolution must pad with `"zeros"`, or with `"circular"` no wider than `$d\,(k - 1)/2$` on each axis, for dilation `$d$` and kernel size `$k$`: wider circular padding, `"reflect"` and `"replicate"` feed a pixel to one kernel offset more than once and raise a `ValueError`.
- `certified_radius(logits, head_weight, L)`, which returns the prediction, the margin and the radius of every row, in float64; `certified_accuracy(correct, radius, eps)`, the fraction correct and certified beyond `eps`; and `cert_ce(logits, y, head_weight, L, eps)`, a cross-entropy that trains for a margin beyond `eps`.

```python
import torch
import torch.nn as nn

from eigenkit.orthogonal.torch import (
    LLNHead,
    MaxMin,
    OrthogonalConv1x1,
    cert_ce,
    certified_accuracy,
    certified_radius,
    lipschitz_bound,
)

features = nn.Sequential(OrthogonalConv1x1(16, init="random"), MaxMin(), nn.Flatten())
head = LLNHead(16 * 4 * 4, 10)
L = lipschitz_bound(features)  # 1.0: an orthogonal layer and MaxMin

x, y = torch.randn(32, 16, 4, 4), torch.randint(0, 10, (32,))
logits = head(features(x))
loss = cert_ce(logits, y, head.get_weight(), L, eps=0.1)
cert = certified_radius(logits, head.get_weight(), L)
certified_accuracy(cert.pred == y, cert.radius, eps=0.1)
```

## Limits

- The circuit simulates a statevector of `$2^n$` amplitudes, so it is practical up to about 20 wires. The matrix is the same map restricted to the unary basis and scales to thousands of wires.
- The matrix costs `$O(\mathrm{depth}\cdot n^2)$`. For a pyramid the depth is `$2n - 3$`, so a dense pyramid matrix grows as `$n^3$`.
- A circuit measures the probabilities `$(Wx)_i^2 / \lVert x \rVert^2$`, not the signed values `$(Wx)_i$`.

## API reference

### `eigenkit.orthogonal`

Orthogonal networks built from RBS (Givens) rotations.

An RBS gate rotates the two states `$|01\rangle$` and `$|10\rangle$` of a pair of wires by an angle. A network of RBS gates keeps the number of 1s fixed, so on the unary basis it acts as an orthogonal matrix, and it stays orthogonal for every value of its angles. A `Topology` fixes which pairs the gates act on: the butterfly, pyramid and X layouts of Cherrat et al. (Quantum 2024), one diagonal of X, a brick wall, or any layout of your own.

This package uses only NumPy and belongs to the framework-free core of the library. `orthogonal_matrix` gives the dense matrix of a layout, `RBSNetwork` and `UnaryLoader` give the quantum circuit, and `to_circuit` turns trained angles into a circuit that runs on any provider.

The PyTorch modules (`Orthogonal`, `OrthogonalConv1x1`, `PartitionedOrthogonal`) and the fine-tuning adapters live in `eigenkit.orthogonal.torch`, which needs the `torch` extra. Their names are also available here, and are imported the first time one is accessed, so importing this package does not import PyTorch. They are listed in `__all__`, so `from eigenkit.orthogonal import *` *does* import PyTorch.

Example

```python
from eigenkit.orthogonal import identity_angles, orthogonal_matrix, pyramid

t = pyramid(4)
orthogonal_matrix(t, identity_angles(t))  # the 4 x 4 identity
```

#### `RBSNetwork`

An orthogonal network of RBS gates, as a circuit block on the wires `0` to `topology.n - 1`.

The gates follow `topology.pairs()`, layer by layer, and gate `k` takes angle `k`. With `reflection=True` in the topology, a final Z gate acts on the last wire. Restricted to the unary basis the block is the matrix `orthogonal_matrix(topology, theta)`.

Without `angles` the block takes `topology.n_angles` trainable weights. With `angles` it takes none, and the angles are fixed `Constant`s, which is how classically trained angles become a circuit (see `to_block`).

Parameters:

| Name       | Type                | Description      | Default                                                                   |
| ---------- | ------------------- | ---------------- | ------------------------------------------------------------------------- |
| `topology` | `Topology`          | The gate layout. | *required*                                                                |
| `angles`   | \`tuple[float, ...] | None\`           | Fixed angles, one per gate, or None for trainable weights. Default: None. |

##### `build(n_qubits)`

Build the gates of this block for a circuit with `n_qubits` qubits.

Parameters:

| Name       | Type  | Description                                                                                            | Default    |
| ---------- | ----- | ------------------------------------------------------------------------------------------------------ | ---------- |
| `n_qubits` | `int` | The number of qubits of the circuit being assembled. The qubits from topology.n on are left unchanged. | *required* |

Returns:

| Name         | Type         | Description                                         |
| ------------ | ------------ | --------------------------------------------------- |
| `IRFragment` | `IRFragment` | The gates, with local weight indices starting at 0. |

##### `from_dict(d)`

Rebuild a block from the output of `to_dict()`.

Parameters:

| Name | Type   | Description                         | Default    |
| ---- | ------ | ----------------------------------- | ---------- |
| `d`  | `dict` | A dictionary returned by to_dict(). | *required* |

Returns:

| Name         | Type         | Description        |
| ------------ | ------------ | ------------------ |
| `RBSNetwork` | `RBSNetwork` | The rebuilt block. |

##### `required_qubits()`

Return `topology.n`, one qubit per wire.

##### `to_dict()`

Return a description of this block that can be saved as JSON.

Returns:

| Name   | Type   | Description                                            |
| ------ | ------ | ------------------------------------------------------ |
| `dict` | `dict` | The topology, the fixed angles (or None) and the type. |

#### `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.

#### `UnaryLoader`

Load a vector `$x \in \mathbb{R}^n$` into the unary basis:

```math
|x\rangle = \sum_i \frac{x_i}{\lVert x \rVert} \, e_i
```

The loader of Johri et al. (2021): an X gate, then `$n - 1$` RBS gates whose angles depend on `$x$`. The three layouts are those of Cherrat et al., Fig. 14:

- `"parallel"`: a binary tree from wire 0, depth `$\log_2 n$`; `n` must be a power of two, and the gates act on distant wires;
- `"diagonal"`: a chain from wire 0 to wire `$n - 1$`, depth `$n - 1$`; any `n`, adjacent wires only;
- `"semi_diagonal"`: two chains from the middle, depth `$n / 2$`; `n` must be even, adjacent wires only.

The angles are non-linear functions of `$x$` that the `Parameter` tree cannot express, so the block takes them as `$n - 1$` inputs, computed by `unary_loader_angles(x, layout)`. It takes no weights.

The estimators `CustomQuantumClassifier` and `CustomQuantumRegressor` do not take this block yet: they read the number of circuit inputs from an `Encoding` or `Reuploading` block only, so a circuit that loads its inputs with a `UnaryLoader` raises a `ValueError` in `fit()`, even with `in_features` given. Run such a circuit with `Circuit` or `TorchCircuit`, or use the `OrthogonalQNN` layer, which computes the loader angles itself.

Parameters:

| Name     | Type           | Description                           | Default      |
| -------- | -------------- | ------------------------------------- | ------------ |
| `n`      | `int`          | The width, at least 2.                | *required*   |
| `layout` | `LoaderLayout` | The gate layout. Default: "diagonal". | `'diagonal'` |

##### `build(n_qubits)`

Build the gates of this block for a circuit with `n_qubits` qubits.

Parameters:

| Name       | Type  | Description                                                                                   | Default    |
| ---------- | ----- | --------------------------------------------------------------------------------------------- | ---------- |
| `n_qubits` | `int` | The number of qubits of the circuit being assembled. The qubits from n on are left unchanged. | *required* |

Returns:

| Name         | Type         | Description                                        |
| ------------ | ------------ | -------------------------------------------------- |
| `IRFragment` | `IRFragment` | The gates, with local input indices starting at 0. |

##### `from_dict(d)`

Rebuild a block from the output of `to_dict()`.

Parameters:

| Name | Type   | Description                         | Default    |
| ---- | ------ | ----------------------------------- | ---------- |
| `d`  | `dict` | A dictionary returned by to_dict(). | *required* |

Returns:

| Name          | Type          | Description        |
| ------------- | ------------- | ------------------ |
| `UnaryLoader` | `UnaryLoader` | The rebuilt block. |

##### `required_qubits()`

Return `n`, one qubit per component of `x`.

##### `to_dict()`

Return a description of this block that can be saved as JSON.

Returns:

| Name   | Type   | Description                         |
| ------ | ------ | ----------------------------------- |
| `dict` | `dict` | The width, the layout and the type. |

#### `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. |

#### `identity_angles(topology)`

The angles that give the identity matrix: all zeros.

Parameters:

| Name       | Type       | Description | Default    |
| ---------- | ---------- | ----------- | ---------- |
| `topology` | `Topology` | The layout. | *required* |

Returns:

| Type      | Description                                                |
| --------- | ---------------------------------------------------------- |
| `ndarray` | np.ndarray: A float64 array of shape (topology.n_angles,). |

#### `loader_depth(n, layout='diagonal')`

The number of layers of RBS gates of a unary loader, the X gate not counted.

It is `$\log_2 n$` for `"parallel"`, `$n - 1$` for `"diagonal"` and `$n / 2$` for `"semi_diagonal"` (Cherrat et al., Fig. 14, count the X gate too).

Parameters:

| Name     | Type           | Description                      | Default      |
| -------- | -------------- | -------------------------------- | ------------ |
| `n`      | `int`          | The width.                       | *required*   |
| `layout` | `LoaderLayout` | The layout. Default: "diagonal". | `'diagonal'` |

Returns:

| Name  | Type  | Description |
| ----- | ----- | ----------- |
| `int` | `int` | The depth.  |

#### `orthogonal_matrix(topology, theta)`

Build the `$n \times n$` orthogonal matrix of a network of RBS gates.

Numerical contract: starting from `W = eye(n)`, each layer, in order, takes the next `k` angles (`k` = the number of pairs in the layer), with `c = cos(θ)[:, None]` and `s = sin(θ)[:, None]`, and replaces the rows `W[i] <- c*W[i] + s*W[j]` and `W[j] <- -s*W[i] + c*W[j]` for all its pairs at once, from the rows before the update. With `reflection=True` the last row is negated at the end. These are the operations, in this order, of the torch module of the same topology, so both give the same matrix.

The cost is `$O(\mathrm{depth} \cdot n^2)$`.

Parameters:

| Name       | Type           | Description                                                                                                                                             | Default    |
| ---------- | -------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------- | ---------- |
| `topology` | `Topology`     | The layout.                                                                                                                                             | *required* |
| `theta`    | `array - like` | The angles, of shape (topology.n_angles,), in the order of topology.pairs(). A float32 array gives a float32 matrix, and any other input a float64 one. | *required* |

Returns:

| Type      | Description                                         |
| --------- | --------------------------------------------------- |
| `ndarray` | np.ndarray: The orthogonal matrix, of shape (n, n). |

Raises:

| Type         | Description                                 |
| ------------ | ------------------------------------------- |
| `ValueError` | If theta has the wrong shape or is complex. |

#### `orthogonal_matrix_jacobian(topology, theta)`

The derivative of `orthogonal_matrix` with respect to each angle.

It is exact: the derivative of one RBS gate is spliced between the product of the layers before it and the product of the layers after it. The cost is `$O(n_{\mathrm{angles}} \, n^2 + \mathrm{depth} \cdot n^3)$`.

Parameters:

| Name       | Type           | Description                                | Default    |
| ---------- | -------------- | ------------------------------------------ | ---------- |
| `topology` | `Topology`     | The layout.                                | *required* |
| `theta`    | `array - like` | The angles, of shape (topology.n_angles,). | *required* |

Returns:

| Type      | Description                                                          |
| --------- | -------------------------------------------------------------------- |
| `ndarray` | np.ndarray: A float64 array of shape (n_angles, n, n), where entry k |
| `ndarray` | is (\\partial W / \\partial \\theta_k).                              |

Raises:

| Type         | Description                                 |
| ------------ | ------------------------------------------- |
| `ValueError` | If theta has the wrong shape or is complex. |

#### `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. |

#### `to_block(topology, theta)`

An `RBSNetwork` block with fixed angles.

Parameters:

| Name       | Type           | Description                                                                  | Default    |
| ---------- | -------------- | ---------------------------------------------------------------------------- | ---------- |
| `topology` | `Topology`     | The gate layout.                                                             | *required* |
| `theta`    | `array - like` | The angles, of shape (topology.n_angles,), in the order of topology.pairs(). | *required* |

Returns:

| Name         | Type         | Description                    |
| ------------ | ------------ | ------------------------------ |
| `RBSNetwork` | `RBSNetwork` | A block that takes no weights. |

Raises:

| Type         | Description                                                |
| ------------ | ---------------------------------------------------------- |
| `ValueError` | If theta is not a real vector of topology.n_angles angles. |

#### `to_circuit(topology, theta, loader='diagonal', provider='numpy')`

A runnable circuit: a unary loader, the network with fixed angles, and the unary readout.

The circuit takes no weights. With a loader, its inputs are the `$n - 1$` loader angles of `unary_loader_angles(x, loader)`, and its outputs are `$\langle Z_i \rangle$`, from which `unary_probabilities` gives `$(Wx)_i^2 / \lVert x \rVert^2$`.

Parameters:

| Name       | Type           | Description                                                                            | Default                                                                                          |
| ---------- | -------------- | -------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------ |
| `topology` | `Topology`     | The gate layout.                                                                       | *required*                                                                                       |
| `theta`    | `array - like` | The angles, of shape (topology.n_angles,).                                             | *required*                                                                                       |
| `loader`   | \`LoaderLayout | None\`                                                                                 | The layout of the UnaryLoader, or None for a circuit with the network alone, which starts from ( |
| `provider` | `ProviderSpec` | The backend, as for Circuit: a name, a config or a backend instance. Default: "numpy". | `'numpy'`                                                                                        |

Returns:

| Name      | Type      | Description                           |
| --------- | --------- | ------------------------------------- |
| `Circuit` | `Circuit` | The compiled NumPy-interface circuit. |

#### `unary_loader_angles(x, layout='diagonal')`

The input angles of `UnaryLoader` that load `$x / \lVert x \rVert$`.

Each gate splits the amplitude on its owner wire between the wires it keeps and the wires it passes on. With `$v_S$` the signed value `$x_s$` when `$S$` is one wire `$s$` and the norm `$\lVert x_S \rVert$` otherwise, the angle is `$\operatorname{atan2}(-v_{\mathrm{pass}}, v_{\mathrm{keep}})$` when the amplitude moves to a higher wire and `$\operatorname{atan2}(v_{\mathrm{pass}}, v_{\mathrm{keep}})$` when it moves to a lower one.

Parameters:

| Name     | Type           | Description                                                                                                                       | Default      |
| -------- | -------------- | --------------------------------------------------------------------------------------------------------------------------------- | ------------ |
| `x`      | `array - like` | One vector of shape (n,) or a batch of shape (B, n). It does not need to be normalised, and its scale does not change the angles. | *required*   |
| `layout` | `LoaderLayout` | The loader layout. Default: "diagonal".                                                                                           | `'diagonal'` |

Returns:

| Type      | Description                                              |
| --------- | -------------------------------------------------------- |
| `ndarray` | np.ndarray: The angles, of shape (n - 1,) or (B, n - 1). |

Raises:

| Type         | Description                                                                 |
| ------------ | --------------------------------------------------------------------------- |
| `ValueError` | If a vector is zero or not finite, or the layout does not accept the width. |

#### `unary_probabilities(expectations)`

Convert the expectation values of `unary_readout` into probabilities.

Parameters:

| Name           | Type           | Description                                       | Default    |
| -------------- | -------------- | ------------------------------------------------- | ---------- |
| `expectations` | `array - like` | The values (\\langle Z_i \\rangle), of any shape. | *required* |

Returns:

| Type      | Description                                                       |
| --------- | ----------------------------------------------------------------- |
| `ndarray` | np.ndarray: ((1 - \\langle Z_i \\rangle) / 2), of the same shape. |

#### `unary_readout(n)`

The observables `$Z_0, \dots, Z_{n-1}$` that read a unary state out.

On a unary state `$\sum_i a_i e_i$`, `$\langle Z_i \rangle = 1 - 2 a_i^2$`, so the probability of wire `$i$` is `$p_i = (1 - \langle Z_i \rangle) / 2$` (see `unary_probabilities`). After a `UnaryLoader` and an `RBSNetwork`, `$p_i = (Wx)_i^2 / \lVert x \rVert^2$`.

Parameters:

| Name | Type  | Description          | Default    |
| ---- | ----- | -------------------- | ---------- |
| `n`  | `int` | The number of wires. | *required* |

Returns:

| Type               | Description                                    |
| ------------------ | ---------------------------------------------- |
| `list[Observable]` | list\[Observable\]: One Z observable per wire. |

#### `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. |
