QUBOInstance

class iqm.applications.qubo.QUBOInstance(qubo_object)

Bases: ProblemInstance

A problem instance class for generic QUBO problems.

This problem instance class should only be used for problems without any structure beyond having a QUBO cost function. Problems with constraints or more structure (such as maxcut, MIS, …) should use sub-classes (children) of QUBOInstance.

The class is initialized with a qubo_object variable, which stores the QUBO parameters. Valid qubo_object is either a 2D square ndarray, Graph or BinaryQuadraticModel. In the case of a Graph, the interactions need to be represented as the bias parameter of nodes / edges (treated as 0 if not present). Regardless of the type of qubo_object, the __init__() method internally saves the problem description as bqm, which is a BinaryQuadraticModel.

Parameters:

qubo_object (ndarray | Graph | BinaryQuadraticModel) – Either a square ndarray, a Graph or a BinaryQuadraticModel describing the QUBO problem.

Attributes

bqm	The BinaryQuadraticModel representation of the problem instance.
dim	The dimension of the problem (i.e., the number of binary variables).
qubo_graph	The QUBO graph of the problem instance.
qubo_matrix	The QUBO matrix of the problem instance.

Methods

fix_variables(variables)	Fixes (assigns) some of the problem variables.
quality(bit_str)	Accepts a bitstring (representing a solution) and returns that solution's quality / energy.

property dim: int

The dimension of the problem (i.e., the number of binary variables).

property qubo_matrix: ndarray

The QUBO matrix of the problem instance.

The matrix is obtained from the internal variable bqm. If the QUBO cost function of the problem variables \(x_i \in \{0, 1\}\) is described as:

\[C = \sum_{i<j} x_i Q_{ij} x_j + \sum_{i} x_i Q_{ii} x_i\]

Then the output of this method is the square matrix \(Q_{ij}\) as ndarray.

• The diagonal entries corresponds to the local fields acting on the variables.

• The entries above the diagonal correspond to the interactions between variables.

• The entries below the diagonal are empty.

property qubo_graph: Graph

The QUBO graph of the problem instance.

The nodes / edges of the graph have a bias parameter containing the local field / interaction strength of the corresponding variable(s). Variable pairs without interaction aren’t connected by edges in the graph.

property bqm: BinaryQuadraticModel

The BinaryQuadraticModel representation of the problem instance.

This variable is defined in __init__() and is used throughout the class to calculate such quantities as dim or qubo_matrix lazily.

fix_variables(variables)

Fixes (assigns) some of the problem variables.

Warning: For problems that come from a graph (such as maxcut), this doesn’t change the original graph, only the derived QUBO formulation (i.e., the BQM variable)!

Parameters:

variables (list[Hashable] | dict[Hashable, int]) – Either a list of variables (which get all fixed to the value 1) or a dictionary with keys equal to the variables to fix and whose values are equal to the values to fix them to (either 1 or 0).

Raises:

ValueError – If one of the variables has already been fixed previously to a different value.

Return type:

None

quality(bit_str)

Accepts a bitstring (representing a solution) and returns that solution’s quality / energy.

Parameters:

bit_str (str) – The bitstring whose quality is being calculated.

Returns:

The energy of the input bitstring.

Return type:

float