API Documentation

API Documentation#

This page documents the classes and methods contained in the qubolite package.

QUBO#

The base class for QUBO instances is qubo.

class qubo(m: numpy.ndarray)[source]#

Bases: object

Standard class for QUBO instances. This is mainly a wrapper around an upper triangular NumPy matrix with lots of helpful methods. The passed array must be of the shape (n, n) for any positive n. The linear coefficients lie along the diagonal. A non-triangular matrix will be converted, i.e., the lower triangle will be transposed and added to the upper triangle.

Parameters:: m (np.ndarray) – Array containing the QUBO parameters.

Examples

If you have linear and quadratic coefficients in separate arrays, e.g., lin with shape (n,) and qua with shape (n, n), they can be combined to a qubo instance through qubo(np.diag(lin) + qua).

absmax()[source]#

Returns the largest parameter by absolute value. This is equivalent to the infinity norm of the QUBO matrix.

Returns:: largest parameter by absolute value.
Return type:: float

as_int(bits=32)[source]#

Scales and rounds the QUBO parameters to fit a given number of bits. The number format is assumed to be signed integer, therefore b bits yields a value range of -2**(b-1) to 2**(b-1)-1.

Parameters:: bits (int, optional) – Number of bits to represent the parameters. Defaults to 32.
Returns:: QUBO instance with scaled and rounded parameters.
Return type:: qubo

clamp(partial_assignment: dict)[source]#

Create QUBO instance equivalent to this but with a subset of variables fixed (_clamped_) to constant values. Warning: This method is deprecated. Use assignment.partial_assignment.apply() instead!

Parameters:

partial_assignment (dict, optional) – Dictionary mapping variable indices (counting from 0) to constant values 0 or 1. Defaults to None, which does nothing and returns a copy of this QUBO instance.

Returns:

Clamped QUBO instance. const (float): Constant offset value, which must be added to the

QUBO energy to obtain the original energy.

free (list): List of indices which the variable indices of the new: QUBO instance correspond to (i.e., those indices that were not clamped).

Return type:

qubo

copy()[source]#

Create a copy of this instance.

Returns:: Copy of this QUBO instance.
Return type:: qubo

dx(x: numpy.ndarray)[source]#

Discrete derivative w.r.t. x: The element at index i gives the QUBO energy change upon flipping the value of x[i].

Parameters:

x (np.ndarray) – Bit vector w.r.t. which the discrete derivative is calculated. Can be an array of multiple bit vectors.

Returns:

Vector of discrete derivatives of this QUBO instance: w.r.t. x.

Return type:

numpy.ndarray

dx2(x: numpy.ndarray)[source]#

2nd discrete derivative w.r.t. x: Returns a matrix where the element at index (i, j) gives the QUBO energy change upon flipping both x[i] and x[j] simultaneously. The 1st discrete derivative is along the diagonal.

Parameters:

x (np.ndarray) – Bit vector w.r.t. which the discrete derivative is calculated. Must have shape (n,).

Returns:

Array of shape (n, n) containing the 2nd discrete: derivatives of this QUBO instance w.r.t. x.

Return type:

numpy.ndarray

Examples

Let Δ = Q.dx2(x), then Δ[i, j] is the same as Q(flip_index(x, [i, j])) - Q(x) (see qubolite.bitvec.flip_index()).

dynamic_range(decibel=False)[source]#

Calculate the dynamic range (DR) of the QUBO parameters, i.e., the logarithmic ratio between the largest and the smallest difference between all pairs of unique parameter values.

Parameters:: decibel (bool, optional) – If True, outputs the DR in the unit decibels. Defaults to False, which outputs the DR in bits.
Returns:: Dynamic range value.
Return type:: float

classmethod from_dict(qubo_dict, n=None, relabel=True)[source]#

Create QUBO instance from a dictionary mapping variable indices to QUBO parameters. Note that, by default, unused variables are eliminated, e.g., the dictionary {(0,): 2, (100,): -3} yields a QUBO instance of size n=2. If you want to use the dictionary keys as variable indices as-is, set relabel=False.

Parameters:

qubo_dict (dict) – Dictionary mapping indices to QUBO parameters.
n (int, optional) – Specifies QUBO size. If None, the size is derived from the number of variable names.
relabel (bool, optional) – Indicate whether the variables should be used as indices as-is, instead of removing unused variables. This works only for integer keys.

Returns:

QUBO instance with parameters taken from dictionary. dict: Dictionary mapping the names of the variables used in the

input dictionary to the indices of the QUBO instance. If relabel=False, this dictionary will be an identity map.

Return type:

qubo

classmethod from_ising(linear, quadratic, offset=0.0)[source]#

Create QUBO instance from Ising model parameters. In an Ising model, the binary variables \(\boldsymbol x\in\lbrace 0,1,\rbrace\) are replaced with bipolar variables \(\boldsymbol s\in\lbrace -1,+1\rbrace\). The two models are computationally equivalent and can be converted into each other by variable substitution \(\boldsymbol s\mapsto 2\boldsymbol x+1\).

Parameters:

linear (list | numpy.ndarray) – Linear coefficients, often denoted by \(\boldsymbol h\); also called external field in physics.
quadratic (list | numpy.ndarray) – Quadratic coefficients, often denoted by \(\boldsymbol J\); also called interactions in physics. If linear has shape (n,), this array must have shape (n, n).
offset (float, optional) – Constant offset added to the energy value. Defaults to 0.0.

Returns:

Tuple containing qubo instance and a new offset value (float).

classmethod load(path: str)[source]#

Load QUBO instance from disk.

Parameters:: path (str) – QUBO file path.
Raises:: RuntimeError – Raised if the file contains no valid QUBO.
Returns:: QUBO instance loaded from disk.
Return type:: qubo

classmethod load_qbsolv(path: str)[source]#

Load a QUBO instance from a file saved in the .qubo file format used by D-Wave’s qbsolv package.

Parameters:: path (str) – QUBO file path.
Raises:: RuntimeError – Raised if an invalid line is encountered
Returns:: QUBO instance loaded from disk.
Return type:: qubo

property num_couplings#

Return the number of non-zero quadratic coefficients of this QUBO instance.

Returns:: Number of non-zero quadratic coefficients.
Return type:: int

pairwise_marginals(temp=1.0, fast=True)[source]#

Compute the marginal probabilities for each variable pair to assume the value (1, 1) under the Gibbs distribution induced by this QUBO instance. Note that this operation’s runtime is exponential in QUBO size.

Parameters:

temp (float, optional) – Temperature parameter of the Gibbs distribution. Defaults to 1.0.
fast (bool, optional) – Internally create array of all bit vectors. This is faster, but requiers memory space exponential in the QUBO size. Defaults to True.

Returns:

Upper triangular matrix of probabilities.

Return type:

numpy.ndarray

partition_function(log=False, temp=1.0, fast=True)[source]#

Calculate the partition function of the Ising model induced by this QUBO instance. That is, return the sum of exp(-Q(x)/temp) over all bit vectors x. Note that this is infeasibly slow for QUBO sizes much larger than 20.

Parameters:

log (bool, optional) – Return the natural log of the partition function instead. Defaults to False.
temp (float, optional) – Temperature parameter of the Gibbs distribution. Defaults to 1.0.
fast (bool, optional) – Internally create array of all bit vectors. This is faster, but requiers memory space exponential in the QUBO size. Defaults to True.

Returns:

Value of the partition function, or the log partition: function if log=True.

Return type:

float

probabilities(temp=1.0, out=None, unnormalized=False, fast=True)[source]#

Compute the complete vector of probabilities for observing a vector x under the Gibbs distribution induced by this QUBO instance. The entries of the resulting array are sorted in lexicographic order by bit vector, e.g. for size 3: [000, 100, 010, 110, 001, 101, 011, 111]. Note that this method requires memory space exponential in QUBO size, which quickly becomes infeasible, depending on your system. If n is the QUBO size, the output will have size 2**n.

Parameters:

temp (float, optional) – Temperature parameter of the Gibbs distribution. Defaults to 1.0.
out (numpy.ndarray, optional) – Array to write the probabilities to. Defaults to None, which creates a new array.
unnormalized (bool, optional) – Return the unnormalized probabilities. Defaults to False.
fast (bool, optional) – Internally create array of all bit vectors. This is faster, but requiers memory space exponential in the QUBO size. Defaults to True.

Returns:

Array containing probabilities.

Return type:

numpy.ndarray

property properties#

classmethod random(n: int, distr='normal', density=1.0, full_matrix=False, random_state=None, **kwargs)[source]#

Create a QUBO instance with parameters sampled from a random distribution.

Parameters:

n (int) – QUBO size
distr (str, optional) – Distribution from which the parameters are sampled. Possible values are 'normal', 'uniform' and 'triangular'. Additional keyword arguments will be passed to the corresponding methods from numpy.random. Defaults to 'normal'.
density (float, optional) – Expected density of the parameter matrix. Each parameter is set to 0 with probability 1-density. Defaults to 1.0.
full_matrix (bool, optional) – Indicate if the full n×n matrix should be sampled and then folded into upper triangle form, or if the triangular matrix should be sampled directly. Defaults to False.
random_state (optional) – A numerical or lexical seed, or a NumPy random generator. Defaults to None.

Raises:

ValueError – Raised if the distr argument is unknown.

Returns:

Random QUBO instance

Return type:

qubo

round(*args)[source]#

Rounds the QUBO parameters to the nearest integers.

Returns:: QUBO instance with rounded parameters.
Return type:: qubo

save(path: str, atol=1e-16)[source]#

Save the QUBO instance to disk. If the file exists, it will be overwritten.

Parameters:

path (str) – Target file path.
atol (float, optional) – Parameters with absolute value below this value will be treated as 0. Defaults to 1e-16.

save_qbsolv(path: str, atol=1e-16)[source]#

Save this QUBO instance using the .qubo file format used by D-Wave’s qbsolv package.

Parameters:

path (str) – Target file path.
atol (float, optional) – Parameters with absolute value below this value will be treated as 0. Defaults to 1e-16.

scale(factor)[source]#

Scale the QUBO parameters by a constant factor.

Parameters:: factor (float) – Scaling factor.
Returns:: QUBO instance with scaled parameters.
Return type:: qubo

spectral_gap(return_optimum=False, max_threads=256)[source]#

Calculate the spectral gap of this QUBO instance. Here, this is defined as the difference between the lowest and second-to lowest QUBO energy value across all bit vectors. Note that the QUBO instance must be solved for calculating this value, therefore only QUBOs of sizes up to about 30 are feasible in practice.

Parameters:

return_optimum (bool, optional) – If True, returns the minimizing bit vector of this QUBO instance (which is calculated anyway). Defaults to False.
max_threads (int) – Upper limit for the number of threads created by the brute-force solver. Defaults to 256.

Raises:

ValueError – Raised if this QUBO instance is too large to be solved
by brute force on the given system. –

Returns:

Spectral gap. x (numpy.ndarray, optional): Minimizing bit vector.

Return type:

sgap (float)

support_graph()[source]#

Return this QUBO instance’s support graph. Its nodes are the set of binary variables, and there is an edge between every pair of variables that has a non-zero parameter.

Returns:: _description_
Return type:: _type_

to_dict(names=None, double_indices=True, atol=1e-16)[source]#

Create a dictionary mapping variable indices to QUBO parameters. Contains entries only for non-zero parameters.

Parameters:

names (dict, optional) – Dictionary mapping variables indices (counting from 0) to names. By default, just the integer indices are used.
double_indices (bool, optional) – If True, use (i, i) as the key for diagonal entries, otherwise (i,). Defaults to True.
atol (float, optional) – Parameters with absolute value below this value will be treated as 0. Defaults to 1e-16.

Returns:

Dictionary containing QUBO parameters.

Return type:

dict

Examples

>>> Q = qubo.random(4, density=0.25).round(1)
>>> Q
qubo([[ 0.6,  0. ,  0.5,  0. ],
      [ 0. ,  0. , -0.4,  0. ],
      [ 0. ,  0. ,  0. , -0.3],
      [ 0. ,  0. ,  0. ,  0. ]])
>>> Q.to_dict()
{(0, 0): 0.6, (0, 2): 0.5, (1, 2): -0.4, (2, 3): -0.3}

to_ising(offset=0.0)[source]#

Convert this QUBO instance to an Ising model with variables \(\boldsymbol s\in\lbrace -1,+1\rbrace\) instead of \(\boldsymbol x\in\lbrace 0,1\rbrace\).

Parameters:

offset (float, optional) – Constant offset value added to the energy. Defaults to 0.0.

Returns:

Tuple containing

linear coefficients (external field) with shape (n,)
quadratic coefficients (interactions) with shape (n, n)
new offset (float)

to_posiform()[source]#

Compute the unique posiform representation of this QUBO instance, using the approach described in section 2.1 of [1]. The result is a tuple of an array P of shape (2, n, n), where n is the QUBO size, and a constant offset value. All entries of the array are positive. P[0] contains the coefficients for the literals Xi*Xj, and Xi on the diagonal, while P[1] contains the coefficients for Xi*!Xj (! denoting negation), and !Xi on the diagonal. See the paper for further infos.

Returns:: Posiform coefficients (see above) float: Constant offset value
Return type:: numpy.ndarray

unique_parameters()[source]#

Return the unique parameter values of this QUBO instance.

Returns:

Array containing the unique parameter values, sorted: in ascending order.

Return type:

numpy.ndarray

Bit Vectors#

The submodule bitvec contains useful methods for working with bit vectors, which in qubolite are just NumPy arrays containing the values 0.0 and 1.0.

all_bitvectors(n: int)[source]#

Generate all bit vectors of size n in lexicographical order, starting from all zeros. The least significant bit is at index 0. Note that always the same array object is yielded, so to persist the bit vectors you need to make copies.

Parameters:: n (int) – Number of bits.
Yields:: numpy.ndarray – Array of shape (n,) containing a bit vector.

Exapmles:

This method can be used to obtain all possible energy values for a given QUBO instance:

>>> Q = qubo.random(3)
>>> for x in all_bitvectors(3):
...     print(to_string(x), '->', Q(x))
...
000 -> 0.0
100 -> 0.6294629779101759
010 -> 0.1566040993504083
110 -> 0.5098350500036248
001 -> 1.5430218546339793
101 -> 3.9359808951564057
011 -> 2.1052824965032304
111 -> 4.222009509768697

all_bitvectors_array(n: int)[source]#

Create an array containing all bit vectors of size n in lexicographical order.

Parameters:: n (int) – Size of bit vectors.
Returns:: Array of shape (2**n, n)
Return type:: numpy.ndarray

flip_index(x, index, in_place=False)[source]#

Flips the values of a given bit vector at the specified index or indices.

Parameters:

x (numpy.ndarray) – Bit vector(s).
index (int | list | numpy.ndarray) – Index or list of indices where to flip the binary values.
in_place (bool, optional) – If True, modify the bit vector in place. The return value will be a reference to the input array. Defaults to False.

Returns:

Bit vector(s) with the indices flipped at the specified: positions. If in_place=True, this will be a reference to the input array, otherwise a copy.

Return type:

numpy.ndarray

Examples

The following inverts the first and last bits of all given bitvectors:

>>> x = from_expression('**10')
>>> x
array([[0., 0., 1., 0.],
       [1., 0., 1., 0.],
       [0., 1., 1., 0.],
       [1., 1., 1., 0.]])
>>> flip_index(x, [0, -1])
array([[1., 0., 1., 1.],
       [0., 0., 1., 1.],
       [1., 1., 1., 1.],
       [0., 1., 1., 1.]])

from_dict(d: dict, n=None)[source]#

Convert a dictionary to a bit vector. The dictionary should map indices (int) to binary values (0 or 1). If n is specified, the vector is padded with zeros to length n.

Parameters:

d (dict) – Dictionary containing index to bit assignments.
n (int, optional) – Length of the bit vector. Defaults to None, which uses the highest index in d as length.

Returns:

Bit vector.

Return type:

numpy.ndarray

from_string(string: str)[source]#

Convert a string consisting of 0 and 1 to a bit vector.

Parameters:: string (str) – Binary string.
Returns:: Bit vector.
Return type:: numpy.ndarray

Examples

This method is useful to quickly convert binary strings to numpy array:

>>> from_string('100101')
array([1., 0., 0., 1., 0., 1.])

random(n: int, size=None, random_state=None)[source]#

Create an array containing random bit vectors.

Parameters:

n (int) – Number of bits per bit vector.
size (int | tuple, optional) – Number of bit vectors to sample, or tuple representing a shape. Defaults to None, which returns a single bit vector (shape (n,)).
random_state (optional) – A numerical or lexical seed, or a NumPy random generator. Defaults to None.

Returns:

Random bit vector(s).

Return type:

numpy.ndarray

to_dict(bitvec: numpy.typing.ArrayLike)[source]#

Convert a bit vector to a dictionary mapping index (int) to bit value (0 or 1).

Parameters:: bitvec (ArrayLike) – Bit vector of shape (n,).
Returns:: Dictionary representation of the bit vector.
Return type:: dict

Examples

This function is useful especially when working with D-Wave’s Python packages, as they often use this format.

>>> to_dict(from_string('10101100'))
{0: 1, 1: 0, 2: 1, 3: 0, 4: 1, 5: 1, 6: 0, 7: 0}

to_string(bitvec: numpy.typing.ArrayLike)[source]#

Convert a bit vector to a string. If an array of bit vectors (shape (m, n)) is passed, a numpy.ndarray containing string objects is returned, one for each row.

Parameters:: bitvec (ArrayLike) – Bit vector (n,) or array of bit vectors (m, n)
Returns:: Binary string
Return type:: string

Partial Assignment#

The submodule assignment implements a powerful tool that allows for partial assignments of bit vectors and, consequently, QUBO instances. This means that, given a bit vector of length n, a partial assignment fixes a subset of bits to either constant 0 or 1, or to the (inverse) value of other variables.

class partial_assignment(s: str | None = None, n: int | None = None, *, graph: networkx.DiGraph | None = None)[source]#

Bases: object

This class represents bit vectors of a fixed size n where a number of bits at certain positions are either fixed to a constant value (0 or 1), or tied to the value of another bit (or its inverse). The bits that are not fixed or tied are called free variables.

The preferred way to instantiate a partial assignment is through the str argument or through a bit vector expression (see assignment.partial_assignment.from_expression()). However, you can specify a partial assignment graph using the graph argument.

Parameters:

s (str, optional) – String representation of a partial assignment; see examples below for the format.
n (int, optional) – The minimum number of bits of the bit vector; e.g., if only x2 = 1 is specified, by setting n=5, the partial assignment will have 5 bits (i.e., **1**). If None (default), use the highest bit index to determine the size. If the highest index is greater than n, then it will be used instead of n.
graph (networkx.DiGraph, optional) – Directed graph representing a partial variable assignment. The nodes must be labeled "x0", "x1", etc., up to some n-1 for all bit variables. Additionally, there must be a node labeled "1". An edge from "x3" to "1" means that bit 3 is fixed to 1, and an edge from "x5" to "x4" means that bit 5 is tied to bit 4. Every edge must have a boolean attribute inverse which indicates if the relation holds inversely, i.e., an edge from "x3" to "x4" with inverse=True means that bit 3 is always the opposite of bit 4. The preferred way to create instances is through from_expression or from_string. Only use the constructor if you know what you are doing. If specified, s and n will be ignored.

Examples

The string representation of a partial assignment consists of a list of bit assignments separated by semicola (;). A bit assignment consists of a variable or a comma-separated list of bit variables followed by = or != and then a single bit variable or 0 or 1. A bit variable consists of the letter x followed by a non-negative integer denoting the bit index. Additionally you can specify ranges of consecutive bit variables like x{<i>-<j>}, where <i> and <j> are the start and stop index (inclusive) respectively. The following lines are all valid strings:

x0 = 1 x2, x3, x5 != x8; x6 = 0 x4=x3;x10=1 x{2-6}, x8 = x0; x7 != x0

The partial assignment can then be instantiated like this:

>>> PA = partial_assignment('x4!=x5; x1=0', n=10)
>>> PA
x1 = 0; x5 != x4
>>> PA.to_expression()
*0***[!4]****

all()[source]#

Generate all vectors matching this given partial assignment.

Returns:

Array containing all bit vectors that match this: partial assignment. If n is the size of this assignment and m the number of free variables, the resulting shape will be (2**m, n).

Return type:

numpy.ndarray

apply(*args, **kwargs)[source]#

assign_constant(*args, **kwargs)[source]#

assign_index(*args, **kwargs)[source]#

expand(x: numpy.ndarray)[source]#

Fill the free variables of this partial assignments with bits provided by x.

Parameters:

x (np.ndarray) – Bits to fill the free variables of this partial assignment with. Must have shape (m?, n), where n is the number of free variables of this partial assignment, as given by the property num_free.

Returns:

(Array of) bit vector(s) expanded by the partial: assignment. The shape is (m?, s), where s is the size of this partial assignment as given by the property size.

Return type:

numpy.ndarray

property fixed#

property free#

classmethod from_expression(expr: str)[source]#

Generate a partial assignment from a string containing a bit vector expression. Such an expression consists of a sequence of these tokens: 0 - a constant 0, 1 - a constant 1, * - all combinations of 0 and 1, [i] - the same as the bit at index i, [!i] - the inverse of the bit at index i.

The last two tokens are called references, with i being their pointing index (counting from 0), where i refers to the i-th token of the bitvector expression itself. Note that a RuntimeError is raised if there is a circular reference chain.

If a token is repeated, you can use specify a number of repetitions in curly braces, e.g., *{5} is the same as *****. This also works with references.

Parameters:

expr (str) – Bit vector expression.

Returns:

The partial assignment described by the: expression.

Return type:

partial_assignment

Examples

This function is useful for generating arrays of bit vectors with a prescribed structure. For instance, “all bit vectors of length 4 that start with 1 and where the last two bits are the same” can be expressed as

>>> PA = from_expression('1**[2]')
>>> PA
x0 = 1; x3 = x2
>>> PA.all()
array([[1., 0., 0., 0.],
...    [1., 1., 0., 0.],
...    [1., 0., 1., 1.],
...    [1., 1., 1., 1.]])

classmethod infer(X: numpy.ndarray)[source]#

match(x: numpy.ndarray)[source]#

Check if a given bit vector or array of bit vectors matches this partial assignment, i.e., if it represents a valid realization.

Parameters:: x (np.ndarray) – Bit vector or array of bit vectors of shape (m?, n).
Returns:: Boolean np.ndarray of shape (m?,) or single Boolean value indicating if the bit vectors match this partial assignment.

property num_fixed#

property num_free#

random(*args, **kwargs)[source]#

classmethod simplify_expression(expr: str)[source]#

property size#

Total number of bits described by the partial assignment, including fixed/tied and free bits.

Returns:: Number of bits.
Return type:: int

to_expression(*args, **kwargs)[source]#

to_matrix(*args, **kwargs)[source]#

Preprocessing#

The submodule preprocessing contains pre-processing methods for QUBO.

qpro_plus(Q: qubo)[source]#

Implements the routine applying rules described in Glover et al. (2018) for reducing the QUBO size by applying logical implications.

Parameters:: Q (qubo) – QUBO instance to be reduced.
Returns:: Instance of assignment.partial_assignment representing the reduction. See example.

Example

>>> import qubolite as ql
>>> Q = ql.qubo.random(32, density=0.2, random_state='example')
>>> PA = ql.preprocessing.qpro_plus(Q)
>>> print(f'{PA.num_fixed} variables were eliminated!')
9 variables were eliminated!
>>> Q_reduced, offset = PA.apply(Q)
>>> Q_reduced.n
23
>>> x = ql.bitvec.from_string('10011101011011110001011')
>>> Q_reduced(x)+offset
-0.5215481745331401
>>> Q(PA.expand(x))
-0.5215481745331385

reduce_dynamic_range(Q: qubo, iterations=100, heuristic='greedy0', random_state=None, decision='heuristic', callback=None, **kwargs)[source]#

Iterative procedure for reducing the dynammic range of a given QUBO, while preserving an optimum, described in Mücke et al. (2023). For this, at every step we choose a specific QUBO weight and change it according to some heuristic.

Parameters:

Q (qubolite.qubo) – QUBO
iterations (int, optional) – Number of iterations. Defaults to 100.
heuristic (str, optional) – Used heuristic for computing weight change. Possible heuristics are ‘greedy0’, ‘greedy’ and ‘order’. Defaults to ‘greedy0’.
random_state (optional) – A numerical or lexical seed, or a NumPy random generator. Defaults to None.
decision (str, optional) – Method for deciding which QUBO weight to change next. Possibilities are ‘random’ and ‘heuristic’. Defaults to ‘heuristic’.
callback (optional) – Callback function which obtains the following inputs after each step: i (int), j (int) , change (float), current matrix order (MatrixOrder), current iteration (int). Defaults to None.
**kwargs (optional) – Keyword arguments for determining the upper and lower bound computations of the optimal QUBO value.

Keyword Arguments:

change_diff (float) – Distance to optimum for avoiding numerical madness. Defaults to 1e-8.
upper_bound (str) – Method for upper bound, possibilities are ‘local_descent’ and ‘sample’. Defaults to ‘local_descent’.
lower_bound (str) – Method for lower bound, possibilities are ‘roof_dual’ and ‘min_sum’. Defaults to ‘roof_dual’.
upper_bound_kwargs (dict) – Additional keyword arguments for upper bound method.
lower_bound_kwargs (dict) – Additional keyword arguments for lower bound method.

Returns:

Compressed QUBO with reduced dynamic range.

Return type:

qubolite.qubo

Solving#

qubolite provides the following methods for solving (exactly or approximately) QUBO instances to obtain their minimizing vector and minimal energy.

anneal(Q: qubo, samples=1, iters=100, max_threads=256, return_raw=False, random_state=None)[source]#

Perform Gibbs sampling with magic annealing schedule.

Parameters:

Q (qubo) – QUBO instance.
samples (int, optional) – Sample size. Defaults to 1.
iters (int, optional) – Number of iterations. Defaults to 100.
max_threads (int) – Upper limit for the number of threads. Defaults to 256. This value is capped to the actual number of hardware threads.
return_raw (bool, optional) – If true, returns the raw Gibbs samples without wrapping them in a BinarySample object. Defaults to false.
random_state (optional) – A numerical or lexical seed, or a NumPy random generator. Defaults to None.

Returns:

Random sample.

Return type:

BinarySample

brute_force(Q: qubo, max_threads=256)[source]#

Solve QUBO instance exactly by brute force. Note that this method is infeasible for instances with a size beyond around 30.

Parameters:

Q (qubo) – QUBO instance to solve.
max_threads (int) – Upper limit for the number of threads. Defaults to 256.

Raises:

ValueError – Raised if the QUBO size is too large to be brute-forced on the present system.

Returns:

A tuple containing the minimizing vector (numpy.ndarray) and the minimal energy (float).

local2_descent(Q: qubo, x=None, random_state=None)[source]#

Starting from a given bit vector, find improvements in the 2-neighborhood and follow them until a local optimum is found. If no initial vector is specified, a random vector is sampled. At each step, the method greedily flips up to two bits that yield the greatest energy improvement.

Parameters:

Q (qubo) – QUBO instance.
x (numpy.ndarray, optional) – Initial bit vector. Defaults to None.
random_state (optional) – A numerical or lexical seed, or a NumPy random generator. Defaults to None.

Returns: