optimization

`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

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` `dataclass`

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` `property`

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` `dataclass`

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`.	`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.	required
`initial_parameters`	`ndarray \| None`	The initial angles `γ` and `β`, of shape `(2 * layers,)`. They are random when they are not given. Default: `None`.	`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.	`None`
`**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` `dataclass`

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` `property`

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`.	`None`
`num_nodes`	`int \| None`	The number of nodes. Default: `None`, which takes it from the edges.	`None`

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.

optimization

eigenkit.optimization

Ising dataclass

num_vars property

brute_force()

energy(bits)

to_hamiltonian()

OptimizationResult dataclass

__post_init__()

QAOA

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

QUBO dataclass

num_vars property

brute_force()

energy(bits)

to_hamiltonian()

to_ising()

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

qaoa_ansatz(hamiltonian, num_qubits, layers)

`eigenkit.optimization`

`Ising` `dataclass`

`num_vars` `property`

`brute_force()`

`energy(bits)`

`to_hamiltonian()`

`OptimizationResult` `dataclass`

`__post_init__()`

`QAOA`

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

`QUBO` `dataclass`

`num_vars` `property`

`brute_force()`

`energy(bits)`

`to_hamiltonian()`

`to_ising()`

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

`qaoa_ansatz(hamiltonian, num_qubits, layers)`