Binary Quadratic Models¶
For an introduction to BQMs, see Binary Quadratic Models.
BQM Classes¶

Encodes a binary quadratic model. 

A binary quadratic model structured as two C++ vectors. 

A binary quadratic model structured as a dictofdicts. 

A binary quadratic model where the neighborhoods are C++ maps. 

A binary quadratic model where the neighborhoods are C++ vectors. 
Functions¶
Generic constructor:

Convert the input to a binary quadratic model. 
Generating BQMs:

Generate an anticluster problem on a Chimera lattice. 

Generate a BQM that is minimized when k of n variables are selected. 

Generate a frustratedloop problem. 

Generate a binary quadratic model with random biases and offset. 

Generate an Ising model for a RANr problem. 

Generate a binary quadratic model with random biases and offset. 
Fixing variables:

Determine assignments for some variables of a binary quadratic model. 
Traversing as a graph:

Yields sets of connected variables. 

Yields variables in breadthfirst search order. 
Converting to and from other data structures:

Convert a binary quadratic model to NetworkX graph format. 

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.
AdjArrayBQM: Uses C++ vectors as arrays
AdjDictBQM: Uses Python dictionaries
AdjMapBQM: Uses C++ maps
AdjVectorBQM: Uses C++ vectors
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,
The performance of various operations depends on your selected BQM implementation; the following table compares the complexity for a BQM of v variables.
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.