Introduction

The dimod API provides a binary quadratic model (BQM) class that contains Ising and quadratic unconstrained binary optimization (QUBO) models used by samplers such as the D-Wave system. It provides utilities for constructing new samplers and composed samplers. It also provides useful functionality for working with these models and samplers. Its reference examples include several samplers and composed samplers.

Ising and QUBO Formulations

The Ising model is an objective function of \(N\) variables \(\bf 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.

Example

Solving problems with large numbers of variables might necessitate the use of decomposition methods such as branch-and-bound to reduce the number of variables. The following example reduces an Ising model for a small problem (the K4 complete graph) for illustrative purposes, and converts the reduced-variables model to QUBO formulation.

>>> 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}
>>> bqm_k4 = dimod.BinaryQuadraticModel(linear, quadratic, 0.5, dimod.SPIN)
>>> bqm_k4.vartype
<Vartype.SPIN: frozenset([1, -1])>
>>> len(bqm_k4.linear)
4
>>> bqm_k4.contract_variables(2, 3)
>>> len(bqm_k4.linear)
3
>>> bqm_no3_qubo = bqm_k4.binary
>>> bqm_no3_qubo.vartype
<Vartype.BINARY: frozenset([0, 1])>

Samplers and Composites

Samplers are processes that sample from low energy states of a problem’s objective function. A binary quadratic model (BQM) sampler samples from low energy states in models such as those defined by an Ising equation or a QUBO problem and returns an iterable of samples, in order of increasing energy. A dimod sampler provides ‘sample_qubo’ and ‘sample_ising’ methods as well as the generic BQM sampler method.

Composed samplers apply pre- and/or post-processing to binary quadratic programs without changing the underlying sampler implementation by layering composite patterns on the sampler. For example, a composed sampler might add spin transformations when sampling from the D-Wave system.

Structured samplers are restricted to sampling only binary quadratic models defined on a specific graph.

You can create your own samplers with dimod’s Sampler abstract base class (ABC) providing complementary methods (e.g., ‘sample_qubo’ if only ‘sample_ising’ is implemented), consistent responses, etc.

Example

This example creates a dimod sampler by implementing a single method (in this example the sample_ising() method).

class LinearIsingSampler(dimod.Sampler):

    def sample_ising(self, h, J):
        sample = linear_ising(h, J)  # Defined elsewhere
        energy = dimod.ising_energy(sample, h, J)
        return dimod.Response.from_samples([sample], {'energy': [energy]})

    @property
    def properties(self):
        return dict()

    @property
    def parameters(self):
        return dict()

The Sampler ABC provides the other sample methods “for free” as mixins.

Minor-Embedding

Embedding attempts to create a target model from a target graph. The process of embedding takes a source model, derives the source graph, maps the source graph to the target graph, then derives the target model. Sometimes referred to in other tools as the embedded graph/model.

Solving an arbitrarily posed binary quadratic problem on a D-Wave system requires minor-embedding to a target graph that represents the system’s quantum processing unit.

Terminology

chain
A collection of nodes or variables in the target graph/model that we want to act as a single node/variable.
chain strength
Magnitude of the negative quadratic bias applied between variables to form a chain.
composed sampler
Samplers that apply pre- and/or post-processing to binary quadratic programs without changing the underlying sampler implementation by layering composite patterns on the sampler. For example, a composed sampler might add spin transformations when sampling from the D-Wave system.
graph
A collection of nodes and edges. A graph can be derived from a model: a node for each variable and an edge for each pair of variables with a non-zero quadratic bias.
model
A collection of variables with associated linear and quadratic biases. Sometimes referred to in other tools as a problem.
sampler
A process that samples from low energy states of a problem’s objective function. A binary quadratic model (BQM) sampler samples from low energy states in models such as those defined by an :term`Ising` equation or a Quadratic Unconstrained Binary Optimization (QUBO) problem and returns an iterable of samples, in order of increasing energy. A dimod sampler provides ‘sample_qubo’ and ‘sample_ising’ methods as well as the generic BQM sampler method.
source
In the context of embedding, the model or induced graph that we wish to embed. Sometimes referred to in other tools as the logical graph/model.
structured sampler
Samplers that are restricted to sampling only binary quadratic models defined on a specific graph.
target
Embedding attempts to create a target model from a target graph. The process of embedding takes a source model, derives the source graph, maps the source graph to the target graph, then derives the target model. Sometimes referred to in other tools as the embedded graph/model.