Skip to content

problems

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

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.