Binary Quadratic Models

Binary quadratic models (BQMs) are described under Binary Quadratic Models.

BQM Classes

BinaryQuadraticModel(*args, **kwargs) Encodes a binary quadratic model.
AdjArrayBQM([vartype]) A binary quadratic model structured as two c++ vectors.
AdjDictBQM(*args[, vartype]) A binary quadratic model structured as a dict-of-dicts.
AdjMapBQM([vartype]) A binary quadratic model where the neighborhoods are c++ maps.
AdjVectorBQM([vartype]) A binary quadratic model where the neighborhoods are c++ vectors.

Functions

Generic constructor:

as_bqm(*args[, cls, copy]) Convert the input to a binary quadratic model.

Generating BQMs:

chimera_anticluster(m[, n, t, multiplier, …]) Generate an anticluster problem on a Chimera lattice.
combinations(n, k[, strength, vartype]) Generate a BQM that is minimized when k of n variables are selected.
frustrated_loop(graph, num_cycles[, R, …]) Generate a frustrated loop problem.
randint(graph, vartype[, low, high, cls, seed]) Generate a binary quadratic model with random biases and offset.
ran_r(r, graph[, cls, seed]) Generate an Ising model for a RANr problem.
uniform(graph, vartype[, low, high, cls, seed]) Generate a binary quadratic model with random biases and offset.

Fixing variables:

fix_variables(bqm[, sampling_mode]) Determine assignments for some variables of a binary quadratic model.

Traversing as a graph:

connected_components(bqm) Yields sets of connected variables.
bfs_variables(bqm, source) Yields variables in breadth-first search order.

Converting to and from other data structures:

to_networkx_graph(bqm[, …]) Convert a binary quadratic model to NetworkX graph format.
from_networkx_graph(G[, vartype, …]) Create a binary quadratic model from a NetworkX graph.

See also: serialization functions

Usage

In Ocean, there are four objects that represent BQMs, differentiated by the data structure used to encode their structure and biases.

The documentation for each class outlines some of the advantages and disadvantages of the different representations.

All of the BQM types use an adjacency structure, in which each variable tracks its own linear bias and its neighborhood. For instance, given a BQM,

\[E(x) = .5 x_0 - 3 x_1 - x_0 x_1 + x_0 x_2 + 2 x_0 x_3 + x_2 x_3\]

its graph and adjacency representations are

Adjacency Structure

The adjacency structure of a 4-variable binary quadratic model.

The performance of various operations will depend on which binary quadratic model implementation you are using. Let v be the number of variables in the BQM

Complexity of various operations
  AdjArrayBQM AdjDictBQM AdjMapBQM AdjVectorBQM
add_variable n/a O(1) [1] O(1) [2] O(1) [2]
add_interaction n/a O(1) [3] O(log v) O(v)
get_linear O(1) O(1) [1] O(1) O(1)
get_quadratic O(log v) O(1) [3] O(log v) O(log v)
num_variables O(1) O(1) O(1) O(1)
num_interactions O(v) O(v) O(v) O(v)
[1](1, 2) Average case, amortized worst case is O(v)
[2](1, 2) Amortized
[3](1, 2) Average case, amortized worst case is O(v^2)

It is worth noting that although the AdjDictBQM is superior in terms of complexity, in practice it is much slower for large BQMs.