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})    
>>> response.data_vectors['energy']      
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(delta_beta=None, seed=None, beta=None, **runopts)[source]

Sample from the input sample set according to a distribution defined with sample energies (with replacement) and temperature/beta difference between current and previous population:

p ~ exp(-sample.energy / delta_temperature) ~ exp(-delta_beta * sample.energy)

Parameters

  • delta_beta (float) – Inverse of sampling temperature difference between current and previous population. Can be defined on sampler construction, on run method invocation, or in the input state’s delta_beta variable.

  • beta (float) – Deprecated. Use ‘delta_beta’ instead.

  • 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 and delta_beta state variables according to a schedule given on construction or in state at first run call.

Parameters

beta_schedule (iterable(float)) – The beta schedule. State’s beta/delta_beta are iterated according to the beta schedule.

Raises

EndOfStream –

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='linear', beta_range=None, **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='linear') –

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

    • linear

    • geometric

  • beta_range (tuple[float], optional) – A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. The schedule is derived by interpolating the range with interpolation method. Default range is set based on the total bias associated with each node (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=100, num_iter=100, num_sweeps=100, beta_range=None)[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.

  • beta_range (tuple[float], optional) – A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. Passed to CalculateAnnealingBetaSchedule for linear schedule generation.

Returns

Workflow (Runnable instance).

HybridizedPopulationAnnealing(num_reads=100, num_iter=100, num_sweeps=100, beta_range=None)[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.

  • beta_range (tuple[float], optional) – A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. Passed to CalculateAnnealingBetaSchedule for linear schedule generation.

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.