Binary Quadratic Models

For an introduction to BQMs, see 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

Ocean represents BQMs with four objects that differ in the data structures used to encode the BQM.

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

All these BQM implementations use an adjacency structure in which each variable tracks its own linear bias and its neighborhood. The figure below shows the graph and adjacency representations for an example 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\]
Adjacency Structure

Adjacency structure of a 4-variable binary quadratic model.

The performance of various operations depends on your selected BQM implementation; the following table compares the complexity for a BQM of v variables.

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.