## `eigenkit.optimization`

Combinatorial optimisation with the core of the library.

Write a problem as an `Ising` or `QUBO` model, then solve it with `QAOA`, the Quantum Approximate Optimization Algorithm. The ansatz uses the gates of the core, the angles are optimised with `minimize_expectation`, and the solution is read from the distribution of bitstrings of the optimised state. The package uses only NumPy and SciPy, needs no PyTorch, and works with any backend.

Example

```python
from eigenkit.optimization import max_cut, QAOA

problem = max_cut([(0, 1), (1, 2), (2, 0), (2, 3)])
result = QAOA(layers=2).solve(problem)
print(result.best_bitstring, result.best_energy)
```

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

### `OptimizationResult`

Bases: `ValueEquality`

The result of a run of the Quantum Approximate Optimization Algorithm (QAOA).

The result is read-only. Assigning to a field raises `FrozenInstanceError`, and writing into an array field raises `ValueError`. This prevents a mistyped `=` (instead of `==`) or an in-place edit from leaving a result whose scalar fields describe a different run from the arrays it holds. To get a writable copy of an array, use `np.array(result.field)`.

Results compare by value, including their arrays. They are not hashable, because a result is a collection of numbers and not a key, and a correct hash of a float array is expensive to compute.

Attributes:

| Name                 | Type              | Description                                                                                                                         |
| -------------------- | ----------------- | ----------------------------------------------------------------------------------------------------------------------------------- |
| `best_bitstring`     | `tuple[int, ...]` | The configuration with the lowest energy that was found, as a tuple of bits.                                                        |
| `best_energy`        | `float`           | Its energy for the problem being solved. This is the answer to report: QAOA samples, so the best sample is better than the average. |
| `expectation`        | `float`           | The mean energy of the final state. Compare it with best_energy to see how concentrated the distribution is.                        |
| `optimal_parameters` | `ndarray`         | The angles γ and β that the optimiser settled on.                                                                                   |
| `probabilities`      | `ndarray`         | The probability of every basis state, of length 2\*\*n.                                                                             |
| `n_iterations`       | `int`             | The number of iterations of the optimiser.                                                                                          |
| `success`            | `bool`            | Whether the optimiser reported convergence.                                                                                         |

#### `__post_init__()`

Make the array fields read-only.

Freezing the dataclass prevents a field from being reassigned, but it does not prevent writing into the array that the field holds, and a result that has been written into still reports the scalar values of the original run. The result therefore keeps its own copies, so the arrays it was built from can still be changed by the caller. To get a writable copy, use `np.array(result.optimal_parameters)`.

### `QAOA`

Bases: `BaseQuantumSolver`

The Quantum Approximate Optimization Algorithm (QAOA) solver.

It solves an `Ising` or `QUBO` problem.

Parameters:

| Name           | Type           | Description                                                                                        | Default                                                                             |
| -------------- | -------------- | -------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------- |
| `layers`       | `int`          | The depth p of QAOA. Default: 1.                                                                   | `1`                                                                                 |
| `provider`     | `ProviderSpec` | The backend. Default: "numpy", the reference NumPy simulator.                                      | `'numpy'`                                                                           |
| `optimizer`    | `Optimizer`    | A SciPy method name, "spsa", or a custom callable (see minimize_expectation). Default: "L-BFGS-B". | `'L-BFGS-B'`                                                                        |
| `random_state` | \`int          | None\`                                                                                             | The seed of the random initial angles. With None, they are not seeded. Default: 42. |

#### `solve(problem, *, initial_parameters=None, top_k=None, **minimize_kwargs)`

Optimise the QAOA angles and read the answer from the final state.

Parameters:

| Name                 | Type      | Description                                                                          | Default                                                                                                                                                                                                                                                              |
| -------------------- | --------- | ------------------------------------------------------------------------------------ | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| `problem`            | \`QUBO    | Ising\`                                                                              | The problem to minimise.                                                                                                                                                                                                                                             |
| `initial_parameters` | \`ndarray | None\`                                                                               | The initial angles γ and β, of shape (2 * layers,). They are random when they are not given. Default: None.                                                                                                                                                          |
| `top_k`              | \`int     | None\`                                                                               | How many of the most probable bitstrings to score with the energy of the problem. The best of them is returned as best_bitstring, and the others are not returned. Default: None, which scores the 64 most probable bitstrings, or all of them when there are fewer. |
| `**minimize_kwargs`  | `Any`     | Other keyword arguments, passed to minimize_expectation, for example max_iterations. | `{}`                                                                                                                                                                                                                                                                 |

Returns:

| Type                 | Description                                                                           |
| -------------------- | ------------------------------------------------------------------------------------- |
| `OptimizationResult` | An OptimizationResult with the best bitstring, its energy and the final distribution. |

Raises:

| Type         | Description                 |
| ------------ | --------------------------- |
| `ValueError` | If top_k is smaller than 1. |

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

### `qaoa_ansatz(hamiltonian, num_qubits, layers)`

Build the standard QAOA circuit.

QAOA is the Quantum Approximate Optimization Algorithm. The circuit starts in `|+⟩^n`, then applies `layers` repetitions of the cost unitary `exp(-i γ_l H_C)` and the mixer `exp(-i β_l Σ_i X_i)`. It has `2 * layers` weights, in the order `[γ_0, β_0, γ_1, β_1, ...]`.

Parameters:

| Name          | Type         | Description                                                                        | Default    |
| ------------- | ------------ | ---------------------------------------------------------------------------------- | ---------- |
| `hamiltonian` | `Observable` | The cost Hamiltonian.                                                              | *required* |
| `num_qubits`  | `int`        | The number of qubits, one per variable.                                            | *required* |
| `layers`      | `int`        | The depth of QAOA, which is the number of pairs of a cost layer and a mixer layer. | *required* |

Returns:

| Type          | Description                                                    |
| ------------- | -------------------------------------------------------------- |
| `CircuitSpec` | The ansatz, as a CircuitSpec with 2 * layers trainable angles. |