Ising, QUBO and Binary Quadratic Models¶

The binary quadratic model (BQM) class contains Ising and quadratic unconstrained binary optimization (QUBO) models used by samplers such as the D-Wave system.

The Ising model is an objective function of \(N\) variables \(f s=[s_1,...,s_N]\) corresponding to physical Ising spins, where \(h_i\) are the biases and \(J_{i,j}\) the couplings (interactions) between spins.

\[\text{Ising:} \qquad E(\bf{s}|\bf{h},\bf{J}) = \left\{ \sum_{i=1}^N h_i s_i + \sum_{i<j}^N J_{i,j} s_i s_j \right\} \qquad\qquad s_i\in\{-1,+1\}\]

The QUBO model is an objective function of \(N\) binary variables represented as an upper-diagonal matrix \(Q\), where diagonal terms are the linear coefficients and the nonzero off-diagonal terms the quadratic coefficients.

\[\text{QUBO:} \qquad E(\bf{x}| \bf{Q}) = \sum_{i\le j}^N x_i Q_{i,j} x_j \qquad\qquad x_i\in \{0,1\}\]

The BinaryQuadraticModel class can contain both these models and its methods provide convenient utilities for working with, and interworking between, the two representations of a problem.

Class¶

class BinaryQuadraticModel(**kwargs)[source]¶

Encodes a binary quadratic model.

Binary quadratic model is the superclass that contains the Ising model and the QUBO.

Parameters:

linear (dict[variable, bias]) – Linear biases as a dict, where keys are the variables of the binary quadratic model and values the linear biases associated with these variables. A variable can be any python object that is valid as a dictionary key. Biases are generally numbers but this is not explicitly checked.
quadratic (dict[(variable, variable), bias]) – Quadratic biases as a dict, where keys are 2-tuples of variables and values the quadratic biases associated with the pair of variables (the interaction). A variable can be any python object that is valid as a dictionary key. Biases are generally numbers but this is not explicitly checked. Interactions that are not unique are added.
offset (number) – Constant energy offset associated with the binary quadratic model. Any input type is allowed, but many applications assume that offset is a number. See BinaryQuadraticModel.energy().
vartype (Vartype/str/set) –
Variable type for the binary quadratic model. Accepted input values:
- Vartype.SPIN, 'SPIN', {-1, 1}
- Vartype.BINARY, 'BINARY', {0, 1}
**kwargs – Any additional keyword parameters and their values are stored in BinaryQuadraticModel.info.

Notes

The BinaryQuadraticModel class does not enforce types on biases and offsets, but most applications that use this class assume that they are numeric.

Examples

This example creates a binary quadratic model with three spin variables.

>>> bqm = dimod.BinaryQuadraticModel({0: 1, 1: -1, 2: .5},
...                                  {(0, 1): .5, (1, 2): 1.5},
...                                  1.4,
...                                  dimod.SPIN)

This example creates a binary quadratic model with non-numeric variables (variables can be any hashable object).

>>> bqm = dimod.BinaryQuadraticModel({'a': 0.0, 'b': -1.0, 'c': 0.5},
...                                  {('a', 'b'): -1.0, ('b', 'c'): 1.5},
...                                  1.4,
...                                  dimod.SPIN)
>>> len(bqm)
3
>>> 'b' in bqm
True

linear¶: dict[variable, bias] – Linear biases as a dict, where keys are the variables of the binary quadratic model and values the linear biases associated with these variables.

quadratic¶: dict[(variable, variable), bias] – Quadratic biases as a dict, where keys are 2-tuples of variables, which represent an interaction between the two variables, and values are the quadratic biases associated with the interactions.

offset¶: number – The energy offset associated with the model. Same type as given on instantiation.

vartype¶: Vartype – The model’s type. One of Vartype.SPIN or Vartype.BINARY.

adj¶: dict – The model’s interactions as nested dicts. In graphic representation, where variables are nodes and interactions are edges or adjacencies, keys of the outer dict (adj) are all the model’s nodes (e.g. v) and values are the inner dicts. For the inner dict associated with outer-key/node ‘v’, keys are all the nodes adjacent to v (e.g. u) and values are quadratic biases associated with the pair of inner and outer keys (u, v).

info¶: dict – A place to store miscellaneous data about the binary quadratic model as a whole.

SPIN¶: Vartype – An alias of Vartype.SPIN for easier access.

BINARY¶: Vartype – An alias of Vartype.BINARY for easier access.

Examples

This example creates an instance of the BinaryQuadraticModel class for the K4 complete graph, where the nodes have biases set equal to their sequential labels and interactions are the concatenations of the node pairs (e.g., 23 for u,v = 2,3).

>>> import dimod
>>> linear = {1: 1, 2: 2, 3: 3, 4: 4}
>>> quadratic = {(1, 2): 12, (1, 3): 13, (1, 4): 14,
...              (2, 3): 23, (2, 4): 24,
...              (3, 4): 34}
>>> offset = 0.0
>>> vartype = dimod.BINARY
>>> bqm_k4 = dimod.BinaryQuadraticModel(linear, quadratic, offset, vartype)
>>> bqm_k4.info = {'Complete K4 binary quadratic model.'}
>>> bqm_k4.info.issubset({'Complete K3 binary quadratic model.',
...                       'Complete K4 binary quadratic model.',
...                       'Complete K5 binary quadratic model.'})
True
>>> bqm_k4.adj.viewitems()   # Show all adjacencies  
[(1, {2: 12, 3: 13, 4: 14}),
 (2, {1: 12, 3: 23, 4: 24}),
 (3, {1: 13, 2: 23, 4: 34}),
 (4, {1: 14, 2: 24, 3: 34})]
>>> bqm_k4.adj[2]            # Show adjacencies for node 2  
{1: 12, 3: 23, 4: 24}
>>> bqm_k4.adj[2][3]         # Show the quadratic bias for nodes 2,3 
23

Vartype Properties¶

`BinaryQuadraticModel.binary`	`BinaryQuadraticModel` – An instance of the QUBO model subclass of the `BinaryQuadraticModel` superclass, corresponding to a binary quadratic model with binary variables.
`BinaryQuadraticModel.spin`	`BinaryQuadraticModel` – An instance of the Ising model subclass of the `BinaryQuadraticModel` superclass, corresponding to a binary quadratic model with spins as its variables.

Methods¶

Construction Shortcuts¶

BinaryQuadraticModel.empty(vartype) Create an empty binary quadratic model.

Adding and Removing Variables and Interactions¶

`BinaryQuadraticModel.add_variable`(v, bias[, …])	Add variable v and/or its bias to a binary quadratic model.
`BinaryQuadraticModel.add_variables_from`(linear)	Add variables and/or linear biases to a binary quadratic model.
`BinaryQuadraticModel.add_interaction`(u, v, bias)	Add an interaction and/or quadratic bias to a binary quadratic model.
`BinaryQuadraticModel.add_interactions_from`(…)	Add interactions and/or quadratic biases to a binary quadratic model.
`BinaryQuadraticModel.add_offset`(offset)	Add specified value to the offset of a binary quadratic model.
`BinaryQuadraticModel.remove_variable`(v)	Remove variable v and all its interactions from a binary quadratic model.
`BinaryQuadraticModel.remove_variables_from`(…)	Remove specified variables and all of their interactions from a binary quadratic model.
`BinaryQuadraticModel.remove_interaction`(u, v)	Remove interaction of variables u, v from a binary quadratic model.
`BinaryQuadraticModel.remove_interactions_from`(…)	Remove all specified interactions from the binary quadratic model.
`BinaryQuadraticModel.remove_offset`()	Set the binary quadratic model’s offset to zero.
`BinaryQuadraticModel.update`(bqm[, ignore_info])	Update one binary quadratic model from another.

Transformations¶

`BinaryQuadraticModel.contract_variables`(u, v)	Enforce u, v being the same variable in a binary quadratic model.
`BinaryQuadraticModel.fix_variable`(v, value)	Fix the value of a variable and remove it from a binary quadratic model.
`BinaryQuadraticModel.flip_variable`(v)	Flip variable v in a binary quadratic model.
`BinaryQuadraticModel.relabel_variables`(mapping)	Relabel variables of a binary quadratic model as specified by mapping.
`BinaryQuadraticModel.scale`(scalar)	Multiply by the specified scalar all the biases and offset of a binary quadratic model.

Change Vartype¶

BinaryQuadraticModel.change_vartype(**kwargs) Create a binary quadratic model with the specified vartype.

Copy¶

BinaryQuadraticModel.copy() Create a copy of a BinaryQuadraticModel.

Energy¶

BinaryQuadraticModel.energy(sample) Determine the energy of the specified sample of a binary quadratic model.

Converting to other types¶

`BinaryQuadraticModel.from_coo`(obj, vartype)	Deserialize a binary quadratic model from a COOrdinate_ format encoding.
`BinaryQuadraticModel.from_ising`(h, J[, offset])	Create a binary quadratic model from an Ising problem.
`BinaryQuadraticModel.from_json`(obj)	Deserialize a binary quadratic model from a JSON encoding.
`BinaryQuadraticModel.from_numpy_matrix`(mat)	Create a binary quadratic model from a NumPy matrix.
`BinaryQuadraticModel.from_qubo`(Q[, offset])	Create a binary quadratic model from a QUBO model.
`BinaryQuadraticModel.from_pandas_dataframe`(bqm_df)	Create a binary quadratic model from a QUBO model formatted as a pandas DataFrame.
`BinaryQuadraticModel.to_coo`([fp])	Serialize the binary quadratic model to a COOrdinate_ format encoding.
`BinaryQuadraticModel.to_ising`()	Converts a binary quadratic model to Ising format.
`BinaryQuadraticModel.to_json`([fp])	Serialize the binary quadratic model using JSON.
`BinaryQuadraticModel.to_networkx_graph`([…])	Convert a binary quadratic model to NetworkX graph format.
`BinaryQuadraticModel.to_numpy_matrix`([…])	Convert a binary quadratic model to NumPy matrix format.
`BinaryQuadraticModel.to_qubo`()	Convert a binary quadratic model to QUBO format.
`BinaryQuadraticModel.to_pandas_dataframe`()	Convert a binary quadratic model to pandas DataFrame format.