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])
parameters = None[source]#
properties = None[source]#
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))
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).

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

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.

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))
swap_pair(betas, states, i, j)[source]#

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

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

Population Annealing#

Population annealing support and a reference workflow implementation.

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

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

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

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.

latticeLNLS#

Greedy large neighborhood local search workflows for lattices.

LatticeLNLS(topology, exclude_dims=None, qpu_sampler=None, energy_threshold=None, max_iter=128, max_time=None, convergence=None, qpu_params=None, workflow_type='qpu-only', track_qpu_branch=False)[source]#

Implements lattice workflows as described in Hybrid quantum annealing for larger-than-QPU lattice-structured problems.

LatticeLNLS workflow is used by LatticeLNLSSampler. Note that to operate this workflow a minimal set of lattice specific state variables must be instantiated:

  1. bqm: A BinaryQuadraticModel, with variables indexed geometrically

  2. origin_embeddings: see make_origin_embeddings

  3. problem_dims: see SublatticeDecomposer

Parameters:

  • topology (str) –

    A lattice topology (e.g. ‘cubic’), consistent with bqm.

    Supported values:

    • ’pegasus’ (qpu_sampler must be pegasus-structured)

    • ’cubic’ (qpu_sampler must be pegasus of chimera-structured)

    • ’kings’ (qpu_sampler must be pegasus of zephyr-structured)

    • ’chimera’ (qpu_sampler must be chimera-structured)

  • qpu_sampler (dimod.Sampler, optional, default=DWaveSampler()) – Sampler such as a D-Wave system.

  • qpu_params (dict, optional, default = {'num_reads': 25, 'annealing_time': 100}) – Dictionary of keyword arguments with values that will be used on every call of the QPU sampler. A local copy of the parameter is made. If the dictionary does not include ‘num_reads’, it is defaulted as 25, if dictionary does not include ‘annealing_time’, it is defaulted as 100.

  • workflow_type (str, optional) –

    Options are:

    • ’qpu-only’

      Default workflow of this paper

    • ’qpu+post-process’

      Steepest greedy descent over the subspace is run sequentially on samples returned by the QPU.

    • ’qpu+parallel-process’

      Steepest greedy descent on the full space is run in parallel with the QPU; the best result is accepted on each iteration.

  • track_qpu_branch (bool, optional, default=False) – Flag indicating whether to track samples, subproblems, and subsamples (samples for the subproblem) in the hybrid.State of the workflow.

  • max_iter (int, optional, default=128) – Number of iterations in the hybrid algorithm.

  • max_time (float/None, optional) – Wall clock runtime termination criterion. Unlimited by default.

  • convergence (int, optional) – 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.

Returns:

Workflow (Runnable instance).

See also

make_origin_embeddings

SublatticeDecomposer

Jack Raymond et al, Hybrid quantum annealing for larger-than-QPU lattice-structured problems

class LatticeLNLSSampler[source]#

A dimod-compatible hybrid decomposition sampler for problems of lattice structure.

For workflow and lattice related arguments, see: LatticeLNLS.

Examples

This example solves a cubic-structured BQM using the default QPU. An 18x18x18 cubic-lattice ferromagnet is created, and sampled by the lattice workflow.

>>> import dimod
>>> import hybrid
>>> from dwave.system import DWaveSampler
>>> topology = 'cubic'
>>> qpu_sampler = DWaveSampler()                        
>>> sampler = hybrid.LatticeLNLSSampler()               
>>> cuboid = (18,18,18)
>>> edge_list = ([((i,j,k),((i+1)%cuboid[0],j,k)) for i in range(cuboid[0])
...              for j in  range(cuboid[1]) for k in range(cuboid[2])]
...             + [((i,j,k),(i,(j+1)%cuboid[1],k)) for i in range(cuboid[0])
...                for j in  range(cuboid[1]) for k in range(cuboid[2])]
...             + [((i,j,k),(i,j,(k+1)%cuboid[2])) for i in range(cuboid[0])
...                for j in range(cuboid[1]) for k in range(cuboid[2])])
>>> bqm = dimod.BinaryQuadraticModel.from_ising({}, {e: -1 for e in edge_list})
>>> EGS = -len(edge_list)
>>> qpu_params={'num_reads': 25,
...             'annealing_time': 100,
...             'auto_scale': False,
...             'chain_strength': 2}
>>> response = sampler.sample(topology='cubic', bqm=bqm,
...                           problem_dims=cuboid,
...                           energy_threshold=EGS,
...                           qpu_sampler=qpu_sampler,
...                           qpu_params=qpu_params)                           
>>> response.data_vectors['energy']                      
array([-17496])

See also

make_origin_embeddings

SublatticeDecomposer

Jack Raymond et al, Hybrid quantum annealing for larger-than-QPU lattice-structured problems

parameters = None[source]#
properties = None[source]#
sample(topology, bqm, problem_dims, exclude_dims=None, reject_small_problems=True, qpu_sampler=None, init_sample=None, num_reads=1, track_qpu_branch=False, **kwargs)[source]#

Solve large subspaces of a lattice structured problem sequentially integrating proposals greedily to arrive at a global or local minima of the bqm.

Parameters:

  • bqm (BinaryQuadraticModel) – Binary quadratic model to be sampled from. Keying of variables must be appropriate to the lattice class.

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

  • track_qpu_branch (bool, optional, default=False) – Flag indicating whether to track samples, subproblems, and subsamples (samples for the subproblem) in the returned sample set’s info field. One list of tracked data is stored per read (as in num_reads).

  • problem_dims (tuple of ints) – Lattice dimensions (e.g. cubic case (18,18,18)).

  • exclude_dims (list of ints, optional) –

    Subspaces are selected by geometric displacement. In the case of cellular-level displacements only dimensions indexing cell-displacements are considered. The defaults are topology dependent:

    • ’chimera’: [2,3] (u,k chimera coordinates are not displaced).

    • ’pegasus’: [0,3,4] (t,u,k nice pegasus coordinates are not displaced).

    • ’cubic’: [] all dimensions are displaced.

  • reject_small_problems (bool, optional, default=True) – If the subsolver is bigger than the target problem, raise an error by default (True), otherwise quietly shrink the embedding to be no larger than the target problem.

  • arguments (additional workflow) – per LatticeLNLS.

Returns:

A dimod SampleSet object.

Return type:

SampleSet

See also

make_origin_embeddings

SublatticeDecomposer

Jack Raymond et al, Hybrid quantum annealing for larger-than-QPU lattice-structured problems