Introduction

dimod provides a binary quadratic model (BQM) class that contains Ising and quadratic unconstrained binary optimization (QUBO) models used, as described in Solving Problems on a D-Wave System, by samplers such as the D-Wave system.

It provides useful functionality for working with these models and samplers; for example BQM Generators to build BQMs and Utilities for calculating the energy of a sample or serializing dimod objects.

It includes reference Samplers and Composites for processing binary quadratic programs and refining sampling, and useful for testing your code during development.

It also provides an API for Samplers and Composites for constructing new samplers and composed samplers tailored for your problem.

Additionally, it provides some Higher-Order Composites and functionality such as reducing higher-order polynomials to BQMs.

Example

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

[1]Ocean software’s D-Wave Hybrid provides tools for decomposing large problems.
>>> 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.

Examples

This first example uses a composed sampler on the Boolean NOT Gate example detailed in the Getting Started documentation. The ExactSolver test sampler calculates the energy of all possible samples; the FixedVariableComposite composite sets the value and removes specified variables from the BQM before sending it to the sampler. Fixing variable x, the input to the NOT gate, to 1 results in valid solution \(z=0\) having lower energy (-1) than solution \(x=z=1\), which is an invalid state for a NOT gate.

>>> from dimod import FixedVariableComposite, ExactSolver
>>> Q = {('x', 'x'): -1, ('x', 'z'): 2, ('z', 'x'): 0, ('z', 'z'): -1}
>>> composed_sampler = FixedVariableComposite(ExactSolver())
>>> sampleset = composed_sampler.sample_qubo(Q, fixed_variables={'x': 1})
>>> print(sampleset)
   x  z energy num_oc.
0  1  0   -1.0       1
1  1  1    0.0       1
['BINARY', 2 rows, 2 samples, 2 variables]

The next 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.

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