Samplers¶

The dwave-greedy package currently includes just one sampler, SteepestDescentSampler, which is an alias for SteepestDescentSolver.

A sampler accepts a binary quadratic model (BQM) and returns variable assignments. Samplers generally try to find minimizing values but can also sample from distributions defined by the BQM.

SteepestDescentSolver¶

Class¶

class SteepestDescentSolver[source]¶

Steepest descent solver/sampler for binary quadratic models.

Steepest descent is the discrete analogue of gradient descent, but the best move is computed using a local minimization rather rather than computing a gradient. At each step, we determine the dimension along which to descend based on the highest energy drop caused by a variable flip.

Solves convex problems to optimality.

Number of downhill runs (samples produced) is determined by num_reads, number of initial_states, or a combination of the two, depending on the initial_states_generator.

For a given input model’s graph \(G = (V, E)\), \(V\) being a set of graph vertices and \(E\) a set of edges, runtime complexity of the underlying C++ implementation is \(O(|E|)\) for initialization phase and \(O(|V|)\) per downhill step.

In the large_sparse_opt mode, runtime complexity on sparse graphs is \(O(|V|*log|V|)\) for initialization and \(O(max\_degree * log|V|)\) per downhill step.

Aliased as SteepestDescentSampler.

Examples

Solve a simple Ising problem:

>>> import greedy
...
>>> sampler = greedy.SteepestDescentSampler()
>>> samples = sampler.sample_ising({0: 2, 1: 2}, {(0, 1): -1})
...
>>> print(samples)      
   0  1 energy num_oc. num_st.
0 -1 -1   -5.0       1       2
['SPIN', 1 rows, 1 samples, 2 variables]

Post-processes samples generated by another sampler (simulated annealing in this example):

import neal
import dimod
import greedy
import networkx

bqm = dimod.generators.ran_r(5, networkx.complete_graph('abc'))

samples = neal.SimulatedAnnealingSampler().sample(bqm)

postprocessed = greedy.SteepestDescentSampler().sample(bqm, initial_states=samples)

For additional examples, see sample().

Attributes¶

`SteepestDescentSolver.properties`	Values for parameters accepted by the sampling methods.
`SteepestDescentSolver.parameters`	Keyword arguments accepted by the sampling methods.

Methods¶

`SteepestDescentSolver.sample`(bqm[, ...])	Sample from a binary quadratic model.
`SteepestDescentSolver.sample_ising`(h, J, ...)	Sample from an Ising model using the implemented sample method.
`SteepestDescentSolver.sample_qubo`(Q, ...)	Sample from a QUBO using the implemented sample method.

SteepestDescentSampler¶

Class¶

SteepestDescentSampler¶: alias of greedy.sampler.SteepestDescentSolver