Reference Workflows

The code includes implementations of some reference workflows you can incorporate as provided into your application and also use to jumpstart development of custom workflows.

Kerberos

Kerberos hybrid sampler runs 3 sampling branches in parallel. In each iteration, best results from tabu search and simulated annealing are combined with best results from QPU sampling a subproblem.

Kerberos(max_iter=100, max_time=None, convergence=3, energy_threshold=None, sa_reads=1, sa_sweeps=10000, tabu_timeout=500, qpu_reads=100, qpu_sampler=None, qpu_params=None, max_subproblem_size=50)[source]

An opinionated hybrid asynchronous decomposition sampler for problems of arbitrary structure and size. Runs Tabu search, Simulated annealing and QPU subproblem sampling (for high energy impact problem variables) in parallel and returns the best samples.

Kerberos workflow is used by KerberosSampler.

Termination Criteria Args:

max_iter (int):
Number of iterations in the hybrid algorithm.
max_time (float/None, optional, default=None):
Wall clock runtime termination criterion. Unlimited by default.
convergence (int):
Number of iterations with no improvement that terminates sampling.
energy_threshold (float, optional):
Terminate when this energy threshold is surpassed. Check is performed at the end of each iteration.

Simulated Annealing Parameters:

sa_reads (int):
Number of reads in the simulated annealing branch.
sa_sweeps (int):
Number of sweeps in the simulated annealing branch.

Tabu Search Parameters:

tabu_timeout (int):
Timeout for non-interruptable operation of tabu search (time in milliseconds).

QPU Sampling Parameters:

qpu_reads (int):
Number of reads in the QPU branch.
qpu_sampler (dimod.Sampler, optional, default=DWaveSampler()):
Quantum sampler such as a D-Wave system.
qpu_params (dict):
Dictionary of keyword arguments with values that will be used on every call of the QPU sampler.
max_subproblem_size (int):
Maximum size of the subproblem selected in the QPU branch.
Returns:Workflow (Runnable instance).
class KerberosSampler[source]

An opinionated dimod-compatible hybrid asynchronous decomposition sampler for problems of arbitrary structure and size.

Examples

This example solves a two-variable Ising model.

>>> import dimod
>>> import hybrid
>>> response = hybrid.KerberosSampler().sample_ising(
...                     {'a': -0.5, 'b': 1.0}, {('a', 'b'): -1})    # doctest: +SKIP
>>> response.data_vectors['energy']      # doctest: +SKIP
array([-1.5])
sample(bqm, init_sample=None, num_reads=1, **kwargs)[source]

Run Tabu search, Simulated annealing and QPU subproblem sampling (for high energy impact problem variables) in parallel and return the best samples.

Sampling Args:

bqm (BinaryQuadraticModel):
Binary quadratic model to be sampled from.
init_sample (SampleSet, callable, None):
Initial sample set (or sample generator) used for each “read”. Use a random sample for each read by default.
num_reads (int):
Number of reads. Each sample is the result of a single run of the hybrid algorithm.

Termination Criteria Args:

max_iter (int):
Number of iterations in the hybrid algorithm.
max_time (float/None, optional, default=None):
Wall clock runtime termination criterion. Unlimited by default.
convergence (int):
Number of iterations with no improvement that terminates sampling.
energy_threshold (float, optional):
Terminate when this energy threshold is surpassed. Check is performed at the end of each iteration.

Simulated Annealing Parameters:

sa_reads (int):
Number of reads in the simulated annealing branch.
sa_sweeps (int):
Number of sweeps in the simulated annealing branch.

Tabu Search Parameters:

tabu_timeout (int):
Timeout for non-interruptable operation of tabu search (time in milliseconds).

QPU Sampling Parameters:

qpu_reads (int):
Number of reads in the QPU branch.
qpu_sampler (dimod.Sampler, optional, default=DWaveSampler()):
Quantum sampler such as a D-Wave system.
qpu_params (dict):
Dictionary of keyword arguments with values that will be used on every call of the QPU sampler.
max_subproblem_size (int):
Maximum size of the subproblem selected in the QPU branch.
Returns:A dimod SampleSet object.
Return type:SampleSet

Parallel Tempering

Parallel tempering support and a reference workflow implementation.

class FixedTemperatureSampler(beta=None, num_sweeps=10000, num_reads=None, aggregate=False, seed=None, **runopts)[source]

Parallel tempering propagate/update step.

The temperature (beta) can be specified upon object construction, and/or given externally (dynamically) in the input state.

On each call, run fixed temperature (~`1/beta`) simulated annealing for num_sweeps (seeded by input sample(s)), effectively producing a new state by sampling from a Boltzmann distribution at the given temperature.

Parameters:
  • beta (float, optional) – Inverse of constant sampling temperature. If not supplied on construction, it must be present in the input state.
  • num_sweeps (int, optional, default=10k) – Number of fixed temperature sampling sweeps.
  • num_reads (int, optional, default=len(state.samples)) – Number of samples produced. If undefined, inferred from the size of the input sample set.
  • aggregate (bool, optional, default=False) – Aggregate samples (duplicity stored in num_occurrences).
  • seed (int, optional, default=None) – Pseudo-random number generator seed.
next(state, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
class SwapReplicaPairRandom(betas=None, seed=None, **runopts)[source]

Parallel tempering swap replicas step.

On each call, choose a random input state (replica), and probabilistically accept a swap with the adjacent state (replica). If swap is accepted, only samples contained in the selected states are exchanged.

Betas can be supplied in constructor, or otherwise they have to present in the input states.

Parameters:
  • betas (list(float), optional) – List of betas (inverse temperature), one for each input state. If not supplied, betas have to be present in the input states.
  • seed (int, default=None) – Pseudo-random number generator seed.
swap_pair(betas, states, i, j)[source]

One pair of states’ (i, j) samples probabilistic swap.

next(states, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
class SwapReplicasDownsweep(betas=None, **runopts)[source]

Parallel tempering swap replicas step.

On each call, sweep down and probabilistically swap all adjacent pairs of replicas (input states).

Betas can be supplied in constructor, or otherwise they have to present in the input states.

Parameters:betas (list(float), optional) – List of betas (inverse temperature), one for each input state. If not supplied, betas have to be present in the input states.
next(states, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
ParallelTempering(num_sweeps=10000, num_replicas=10, max_iter=None, max_time=None, convergence=3)[source]

Parallel tempering workflow generator.

Parameters:
  • num_sweeps (int, optional) – Number of sweeps in the fixed temperature sampling.
  • num_replicas (int, optional) – Number of replicas (parallel states / workflow branches).
  • max_iter (int/None, optional) – Maximum number of iterations of the update/swaps loop.
  • max_time (int/None, optional) – Maximum wall clock runtime (in seconds) allowed in the update/swaps loop.
  • convergence (int/None, optional) – Number of times best energy of the coldest replica has to repeat before we terminate.
Returns:

Workflow (Runnable instance).

HybridizedParallelTempering(num_sweeps=10000, num_replicas=10, max_iter=None, max_time=None, convergence=3)[source]

Parallel tempering workflow generator.

Parameters:
  • num_sweeps (int, optional) – Number of sweeps in the fixed temperature sampling.
  • num_replicas (int, optional) – Number of replicas (parallel states / workflow branches).
  • max_iter (int/None, optional) – Maximum number of iterations of the update/swaps loop.
  • max_time (int/None, optional) – Maximum wall clock runtime (in seconds) allowed in the update/swaps loop.
  • convergence (int/None, optional) – Number of times best energy of the coldest replica has to repeat before we terminate.
Returns:

Workflow (Runnable instance).

Population Annealing

Population annealing support and a reference workflow implementation.

class EnergyWeightedResampler(beta=None, seed=None, **runopts)[source]

Sample from the input sample set according to a distribution defined with sample energies (with replacement):

p ~ exp(-sample.energy / temperature) ~ exp(-beta * sample.energy)
Parameters:
  • beta (float) – Inverse of sampling temperature. Can be defined on sampler construction, on run method invocation, or in the input state’s beta variable.
  • seed (int, default=None) – Pseudo-random number generator seed.
Returns:

Input state with new samples. The lower the energy of an input sample, the higher will be its relative frequency in the output sample set.

next(state, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
class ProgressBetaAlongSchedule(beta_schedule=None, **runopts)[source]

Sets beta state variable to a schedule given on construction or in state at first run.

Parameters:beta_schedule (iterable(float)) – The beta schedule. State’s beta is iterated according to the beta schedule.
Raises:EndOfStream when beta schedule is depleted.
init(state, **runopts)[source]

Run prior to the first next/run, with the first state received.

Default to NOP.

next(state, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
class CalculateAnnealingBetaSchedule(length=2, interpolation='geometric', **runopts)[source]

Calculate a best-guess beta schedule estimate for annealing methods, based on magnitudes of biases of the input problem, and the requested method of interpolation.

Parameters:
  • length (int) – Length of the produced beta schedule.
  • interpolation (str, optional, default='geometric') –

    Interpolation used between the hot and the cold beta. Supported values are:

    • linear
    • geometric
See:
neal.default_beta_range().
next(state, **runopts)[source]

Execute one blocking iteration of an instantiated Runnable with a valid state as input.

Parameters:state (State) – Computation state passed between connected components.
Returns:The new state.
Return type:State

Examples

This code snippet runs one iteration of a sampler to produce a new state:

new_state = sampler.next(core.State.from_sample({'x': 0, 'y': 0}, bqm))
PopulationAnnealing(num_reads=20, num_iter=20, num_sweeps=1000)[source]

Population annealing workflow generator.

Parameters:
  • num_reads (int) – Size of the population of samples.
  • num_iter (int) – Number of temperatures over which we iterate fixed-temperature sampling / resampling.
  • num_sweeps (int) – Number of sweeps in the fixed temperature sampling step.
Returns:

Workflow (Runnable instance).

HybridizedPopulationAnnealing(num_reads=20, num_iter=20, num_sweeps=1000)[source]

Workflow generator for population annealing initialized with QPU samples.

Parameters:
  • num_reads (int) – Size of the population of samples.
  • num_iter (int) – Number of temperatures over which we iterate fixed-temperature sampling / resampling.
  • num_sweeps (int) – Number of sweeps in the fixed temperature sampling step.
Returns:

Workflow (Runnable instance).

qbsolv

QBSolv inspired simple workflows.

SimplifiedQbsolv(max_iter=10, max_time=None, convergence=3, energy_threshold=None, max_subproblem_size=30)[source]

Races a Tabu solver and a QPU-based sampler of flip-energy-impact induced subproblems.

For arguments description see: Kerberos.