# 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 bqm 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 bqm 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.

- 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 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,

its graph and adjacency representations are

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

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.