Decomposers#
Classes#
 class ComponentDecomposer(rolling=True, silent_rewind=True, key=None, reverse=None, **runopts)[source]#
Selects a subproblem of variables that make up a connected component.
 Parameters:
rolling (bool, optional, default=True) – If True, successive calls for the same problem (with possibly different samples) produce subproblems on different components, selected by rolling down the list of all components.
key (callable, optional, default=None) – Extracts a comparison key from each component of the problem. The comparison keys determine which component will be used to build the subproblem.
reverse (bool, optional, default=None) – Only applies when key is specified. If False, the components’ comparison keys will be sorted in increasing order. If True or unspecified, they will be sorted in decreasing order.
silent_rewind (bool, optional, default=True) – If False, raises
EndOfStream
when resetting/rewinding the subproblem generator once all components have been used.
See Examples.
 class EnergyImpactDecomposer(size, min_gain=None, rolling=True, rolling_history=1.0, silent_rewind=True, traversal='energy', **runopts)[source]#
Selects a subproblem of variables maximally contributing to the problem energy.
The selection currently implemented does not ensure that the variables are connected in the problem graph.
 Parameters:
size (int) – Nominal number of variables in the subproblem. Actual subproblem can be smaller, depending on other parameters (e.g. min_gain).
min_gain (int, optional, default=inf) – Minimum reduction required to BQM energy, given the current sample. A variable is included in the subproblem only if inverting its sample value reduces energy by at least this amount.
rolling (bool, optional, default=True) – If True, successive calls for the same problem (with possibly different samples) produce subproblems on different variables, selected by rolling down the list of all variables sorted by decreasing impact.
rolling_history (float, optional, default=1.0) – Fraction of the problem size, as a float in range 0.0 to 1.0, that should participate in the rolling selection. Once reached, subproblem unrolling is reset.
silent_rewind (bool, optional, default=True) – If False, raises
EndOfStream
when resetting/rewinding the subproblem generator upon the reset condition for unrolling.traversal (str, optional, default='energy') –
Traversal algorithm used to pick a subproblem of size variables. Options are:
 energy:
Use the next size variables in the list of variables ordered by descending energy impact.
 bfs:
Breadthfirst traversal seeded by the next variable in the energy impact list.
 pfs:
Priorityfirst traversal seeded by variables from the energy impact list, proceeding with the variable on the search boundary that has the highest energy impact.
See Examples.
 class RandomConstraintDecomposer(size, constraints, **runopts)[source]#
Selects variables randomly as constrained by groupings.
By grouping related variables, the problem’s structure can guide the random selection of variables so subproblems are related to the problem’s constraints.
 Parameters:
See Examples.
 class RandomSubproblemDecomposer(size, **runopts)[source]#
Selects a subproblem of size random variables.
The selection currently implemented does not ensure that the variables are connected in the problem graph.
 Parameters:
size (int) – Number of variables in the subproblem.
See Examples.
 class RoofDualityDecomposer(sampling_mode=True, **runopts)[source]#
Selects a subproblem with variables that cannot be fixed by roof duality.
Roof duality finds a lower bound for the minimum of a quadratic polynomial. It can also find minimizing assignments for some of the polynomial’s variables; these fixed variables take the same values in all optimal solutions [BHT] [BH]. A quadratic pseudoBoolean function can be represented as a network to find the lower bound through networkflow computations. This decomposer can also use maximum flow in the implication network to fix variables. Consequently, you can find an assignment for the remaining variables that attains the optimal value.
 Parameters:
sampling_mode (bool, optional, default=True) – In sampling mode, only roofduality is used. When sampling_mode is false, strongly connected components are used to fix more variables, but in some optimal solutions these variables may take different values.
 class TilingChimeraDecomposer(size=(4, 4, 4), loop=True, **runopts)[source]#
Returns sequential Chimera lattices that tile the initial problem.
A Chimera lattice is an mbyn grid of Chimera tiles, where each tile is a bipartite graph with shores of size t. The problem is decomposed into a sequence of subproblems with variables belonging to the Chimera lattices that tile the problem Chimera lattice. For example, a 2x2 Chimera lattice could be tiled 64 times (8x8) on a fullyyielded DWave 2000Q system (16x16).
 Parameters:
size (int, optional, default=(4,4,4)) – Size of the Chimera lattice as (m, n, t), where m is the number of rows, n the columns, and t the size of shore in the Chimera lattice.
loop (Bool, optional, default=True) – Cycle continually through the tiles.
See Examples.
 class SublatticeDecomposer(seed=None, **runopts)[source]#
Selects a latticestructured subproblem.
This decomposer requires the input state to contain fields
bqm
andorigin_embeddings
; only the keys (the variables/nodes) fromorigin_embeddings
are used. The decomposer can also use the optional state fieldsproblem_dims
,exclude_dims
,geometric_offset
andorigin_embedding_index
.By default
geometric_offset
is assigned uniformly at random on the range given byproblem_dims
. By defaultorigin_embedding_index
is assigned uniformly at random on the range[0,len(state.origin_embeddings))
. The random number generator can be initialized with the class variableseed
.If
problem_dims
is a state field, geometrically offset variables are wrapped around boundaries according to assumed periodic boundary condition. This is a required field when thegeometric_offset
is not specified. Note that, the origin embedding must specify a lattice smaller than the target lattice. Parameters:
seed (int, default=None) – Pseudorandom number generator seed.
 Returns:
subproblem
andembedding
state fields
See also
Jack Raymond et al, Hybrid quantum annealing for largerthanQPU latticestructured problems
Methods#

Creates optimal embeddings for a lattice. 
Examples#
ComponentDecomposer#
This example iterates twice on a 4variable binary quadratic model, decomposing the problem into 2 connected components which are selected by component size in decreasing order.
import dimod
from hybrid.decomposers import ComponentDecomposer
from hybrid.core import State
from hybrid.utils import random_sample
bqm = dimod.BinaryQuadraticModel({'a': 1, 'b': 1, 'c': 1, 'd': 2}, {'ab': 1, 'bc': 1}, 0, dimod.SPIN)
state0 = State.from_sample(random_sample(bqm), bqm)
decomposer = ComponentDecomposer(key=len)
state1 = decomposer.next(state0).result()
state2 = decomposer.next(state1).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({b: 1.0, a: 1.0, c: 1.0}, {('b', 'a'): 1.0, ('b', 'c'): 1.0}, 0.0, 'SPIN')
>>> print(state2.subproblem)
BinaryQuadraticModel({d: 2.0}, {}, 0.0, 'SPIN')
EnergyImpactDecomposer#
This example iterates twice on a 10variable binary quadratic model with a random initial sample set. size configuration limits the subproblem in the first iteration to the first 4 variables shown in the output of flip_energy_gains.
import dimod
from hybrid.decomposers import EnergyImpactDecomposer
from hybrid.core import State
from hybrid.utils import min_sample, flip_energy_gains
bqm = dimod.BinaryQuadraticModel({t: 0 for t in range(10)},
{(t, (t+1) % 10): 1 for t in range(10)},
0, 'BINARY')
decomposer = EnergyImpactDecomposer(size=4, rolling=True, rolling_history=1.0)
state0 = State.from_sample(min_sample(bqm), bqm)
>>> flip_energy_gains(bqm, state0.samples.first.sample)
[(0, 9), (0, 8), (0, 7), (0, 6), (0, 5), (0, 4), (0, 3), (0, 2), (0, 1), (0, 0)]
>>> state1 = decomposer.run(state0).result()
>>> list(state1.subproblem.variables)
[8, 7, 9, 6]
>>> state2 = decomposer.run(state1).result()
>>> list(state2.subproblem.variables)
[2, 3, 4, 5]
RandomSubproblemDecomposer#
This example decomposes a 6variable binary quadratic model with a random initial sample set to create a 3variable subproblem.
import dimod
from hybrid.decomposers import RandomSubproblemDecomposer
from hybrid.core import State
from hybrid.utils import random_sample
bqm = dimod.BinaryQuadraticModel(
{t: 0 for t in range(6)}, {(t, (t+1) % 6): 1 for t in range(6)}, 0, 'BINARY')
decomposer = RandomSubproblemDecomposer(bqm, size=3)
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({2: 1.0, 3: 0.0, 4: 0.0}, {(2, 3): 1.0, (3, 4): 1.0}, 0.0, Vartype.BINARY)
TilingChimeraDecomposer#
This example decomposes a 2048variable Chimera structured binary quadratic model read from a file into 2x2x4lattice subproblems.
import dimod
from hybrid.decomposers import TilingChimeraDecomposer
from hybrid.core import State
from hybrid.utils import random_sample
with open('problems/randomchimera/2048.09.qubo', 'r') as fp:
bqm = dimod.BinaryQuadraticModel.from_coo(fp)
decomposer = TilingChimeraDecomposer(size=(2,2,4))
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({0: 0.0, 4: 0.0, 5: 0.0, 6: 0.0, 7: 3.0, 1: 0.0, 2: 0.0, 3: 4.0, 1024: 7.0, 1028: 0.0,
>>> # Snipped above response for brevity
>>> state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({8: 3.0, 12: 0.0, 13: 2.0, 14: 11.0, 15: 3.0, 9: 4.0, 10: 0.0, 11: 0.0, 1032: 0.0,
>>> # Snipped above response for brevity
RandomConstraintDecomposer#
This example decomposes a 4variable binary quadratic model that represents three serial NOT gates into 2variable subproblems. The expected decomposition should use variables that represent one of the NOT gates rather than two arbitrary variables.
import dimod
from hybrid.decomposers RandomConstraintDecomposer
from hybrid.core import State
from hybrid.utils import random_sample
bqm = dimod.BinaryQuadraticModel({'w': 2.0, 'x': 4.0, 'y': 4.0, 'z': 2.0},
{('w', 'x'): 4.0, ('x', 'y'): 4.0, ('y', 'z'): 4.0},
3.0, 'BINARY')
decomposer = RandomConstraintDecomposer(2, [{'w', 'x'}, {'x', 'y'}, {'y', 'z'}])
state0 = State.from_sample(random_sample(bqm), bqm)
state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({'z': 2.0, 'y': 0.0}, {('z', 'y'): 4.0}, 0.0, Vartype.BINARY)
SublatticeDecomposer#
This example creates a 5x5 square ferromagnetic lattice problem,
and builds the 3x3 subproblem located at the center of the square.
The initial state is set to all spin up.
Only the variable (2,2) is not adjacent to the boundary, other
variables pick up a linear bias of 1 or 2 due to the boundary condition.
Keys of the origin embedding
dict determine the subproblem created, in this
case there is no minorembedding provided (values are empty).
import dimod
from hybrid.decomposers import SublatticeDecomposer
from hybrid.core import State
problem_dims = (5, 5)
subproblem_dims = (3, 3)
geometric_offset = (1, 1)
edgelist = [((i, j), (i+1, j))
for i in range(problem_dims[0]1)
for j in range(problem_dims[1])]
edgelist += [((i, j), (i, j+1))
for i in range(problem_dims[0])
for j in range(problem_dims[1]1)]
bqm = dimod.BinaryQuadraticModel({}, {edge: 1 for edge in edgelist},
0, dimod.SPIN)
origin_embeddings = [{(i, j): None
for i in range(subproblem_dims[0])
for j in range(subproblem_dims[1])}]
decomposer = SublatticeDecomposer()
sample = {var: 1 for var in bqm.variables}
state0 = State.from_sample(sample, bqm,
origin_embeddings=origin_embeddings,
problem_dims=problem_dims,
geometric_offset=geometric_offset)
state1 = decomposer.run(state0).result()
>>> print(state1.subproblem)
BinaryQuadraticModel({(1, 2): 1.0, (2, 2): 0.0, (1, 1): 2.0, (1, 3): 2.0, (2, 1): 1.0, (3, 1): 2.0, (3, 2): 1.0, (2, 3): 1.0, (3, 3): 2.0}, {((1, 2), (2, 2)): 1.0, ((1, 2), (1, 1)): 1.0, ((1, 2), (1, 3)): 1.0, ((2, 2), (2, 1)): 1.0, ((2, 2), (2, 3)): 1.0, ((2, 2), (3, 2)): 1.0, ((1, 1), (2, 1)): 1.0, ((1, 3), (2, 3)): 1.0, ((2, 1), (3, 1)): 1.0, ((3, 1), (3, 2)): 1.0, ((3, 2), (3, 3)): 1.0, ((2, 3), (3, 3)): 1.0}, 0.0, 'SPIN')