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
- bqm (
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
- 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
anddelta_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
- 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 (seeneal.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).