## `eigenkit.optimization.problems`

Combinatorial problems as Ising and QUBO models, and their qubit Hamiltonians.

QUBO means quadratic unconstrained binary optimisation. The mapping convention is that the spin `s_i = +1` is the qubit state `|0⟩` and `s_i = -1` is `|1⟩`, which are the eigenvalues of `Z`. So a bitstring `b`, with qubit values `b_i ∈ {0, 1}`, corresponds to `s_i = 1 - 2 b_i`. `to_hamiltonian()` returns the pair `(Observable, offset)`. The Pauli sum holds only the `Z` and `ZZ` terms, and the constant is kept apart, because the Pauli backends reject terms made only of the identity. The solver adds `offset` back to `⟨H⟩`.

### `Ising`

An Ising problem, which minimises `Σ h_i s_i + Σ_{i<j} J_ij s_i s_j + constant`.

The minimum is taken over `s ∈ {+1, -1}^n`. Only the strict upper triangle of `J` (`i < j`) is used.

Attributes:

| Name       | Type      | Description                                                                                                                                                                                         |
| ---------- | --------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `h`        | `ndarray` | The linear field, of shape (n,), with one bias per spin.                                                                                                                                            |
| `J`        | `ndarray` | The coupling matrix, of shape (n, n). Only the strict upper triangle is read, so a symmetric matrix and its upper half give the same problem, and the entries on or below the diagonal are ignored. |
| `constant` | `float`   | An energy offset added to every configuration. It shifts the reported energy without changing which configuration wins. Default: 0.0.                                                               |

#### `num_vars`

The number of spins, read from the length of `h`.

#### `brute_force()`

Find the exact minimum by trying every assignment.

This is practical only for a small `n`.

Returns:

| Name        | Type              | Description                            |
| ----------- | ----------------- | -------------------------------------- |
| `bitstring` | `tuple[int, ...]` | The assignment with the lowest energy. |
| `energy`    | `float`           | Its energy.                            |

#### `energy(bits)`

Return the energy of one assignment.

The bits are converted to spins with `s = 1 - 2b`, so a `0` is the spin `+1` and a `1` is the spin `-1`.

Parameters:

| Name   | Type            | Description                                          | Default    |
| ------ | --------------- | ---------------------------------------------------- | ---------- |
| `bits` | `Iterable[int]` | One bit per variable, in the order of the variables. | *required* |

Returns:

| Type    | Description                                    |
| ------- | ---------------------------------------------- |
| `float` | The energy of the assignment for this problem. |

#### `to_hamiltonian()`

Return the qubit Hamiltonian of the problem, with the constant kept apart.

The Hamiltonian is `Σ h_i Z_i + Σ_{i<j} J_ij Z_i Z_j`.

Returns:

| Name         | Type         | Description                        |
| ------------ | ------------ | ---------------------------------- |
| `observable` | `Observable` | The Hamiltonian, as an Observable. |
| `offset`     | `float`      | The constant of the problem.       |

Raises:

| Type         | Description                             |
| ------------ | --------------------------------------- |
| `ValueError` | If every coefficient of the model is 0. |

### `QUBO`

A quadratic unconstrained binary optimisation (QUBO) problem.

It minimises `xᵀQx + constant` over `x ∈ {0, 1}^n`.

Attributes:

| Name       | Type      | Description                                                                                                           |
| ---------- | --------- | --------------------------------------------------------------------------------------------------------------------- |
| `Q`        | `ndarray` | The cost matrix, of shape (n, n). The diagonal entries are the linear terms, because x_i² = x_i for binary variables. |
| `constant` | `float`   | An energy offset added to every configuration. Default: 0.0.                                                          |

#### `num_vars`

The number of binary variables, read from the shape of `Q`.

#### `brute_force()`

Find the exact minimum by trying every assignment.

This is practical only for a small `n`.

Returns:

| Name        | Type              | Description                            |
| ----------- | ----------------- | -------------------------------------- |
| `bitstring` | `tuple[int, ...]` | The assignment with the lowest energy. |
| `energy`    | `float`           | Its energy.                            |

#### `energy(bits)`

Return the energy of one assignment.

Parameters:

| Name   | Type            | Description                                          | Default    |
| ------ | --------------- | ---------------------------------------------------- | ---------- |
| `bits` | `Iterable[int]` | One bit per variable, in the order of the variables. | *required* |

Returns:

| Type    | Description                                    |
| ------- | ---------------------------------------------- |
| `float` | The energy of the assignment for this problem. |

#### `to_hamiltonian()`

Return the qubit Hamiltonian of the problem, through `to_ising()`.

Returns:

| Name         | Type         | Description                        |
| ------------ | ------------ | ---------------------------------- |
| `observable` | `Observable` | The Hamiltonian, as an Observable. |
| `offset`     | `float`      | The constant of the problem.       |

#### `to_ising()`

Convert the problem exactly to an `Ising` model, with `x_i = (1 - s_i) / 2`.

Returns:

| Type    | Description                 |
| ------- | --------------------------- |
| `Ising` | The equivalent Ising model. |

### `max_cut(edges, weights=None, num_nodes=None)`

Build the Ising model of the MaxCut problem for a weighted graph.

The problem is written as an energy to minimise. The spin assignment with the lowest energy is a maximum cut, and the cut value of a bitstring is `-ising.energy(bits)`.

Parameters:

| Name        | Type                        | Description                              | Default                                                                  |
| ----------- | --------------------------- | ---------------------------------------- | ------------------------------------------------------------------------ |
| `edges`     | `Sequence[tuple[int, int]]` | The edges of the graph, as pairs (i, j). | *required*                                                               |
| `weights`   | \`Sequence[float]           | None\`                                   | One weight per edge. Default: None, which gives every edge the weight 1. |
| `num_nodes` | \`int                       | None\`                                   | The number of nodes. Default: None, which takes it from the edges.       |

Returns:

| Type    | Description                                       |
| ------- | ------------------------------------------------- |
| `Ising` | The Ising problem whose minimum is a maximum cut. |