dwavesystems / dwave-hybrid Goto Github PK

View Code? Open in Web Editor NEW

79.0 79.0 50.0 21.2 MB

Hybrid Asynchronous Decomposition Sampler prototype framework.

Home Page: https://docs.ocean.dwavesys.com/projects/hybrid/en/stable/

License: Apache License 2.0

Python 100.00%

quantum-computing

dwave-hybrid's People

Contributors

Stargazers

Watchers

Forkers

randomir stjordanis joelpasvolsky arcondello aamirlat sgangoly qpansoftware deltaresprojects nikolayvoronchikhin sajidsaleem mayoor23 birlrobotics kslaughter js-burns cnxtech m3ller seanmcrae jackreeceejini kevcruzx chenqin loverui0 ssghost todun hsadeghidw mmillerxyz neolithera hhtong maneeshs 00mjk xar1sgeovlacp2019059 ayazskhan zeta1999 global-localhost global19 global19-atlassian-net fermiq steliord jackraymond rog77 andreyyurin retrohun seatim philarnoldvinci cwickniss lordspringfroggy777 davidmerwin mxburns2022 kevinchern

dwave-hybrid's Issues

Add energy threshold termination criterion to Loop

Something like:

Loop(key=operator.attrgetter('subsamples.first.energy'),
     terminate=partial(operator.gt, 1000))

Loop(key='subsamples.first.energy', terminate=lambda v: v < 1000)

would terminate looping as soon as value of key function would drop below 1000.

`runnable & branches` composition fails

Prepending of Runnable to Branches fails

>>> Identity() & Branches(Runnable())
...
TypeError: not all branches have the same input dimensionality

but appending works:

>>> Branches(Runnable()) & Identity()
Branches(Runnable(), Identity())

Simplify late binding of runopts on instantiated Runnables

For example:

sa = hybrid.SimulatedAnnealingProblemSampler(sweeps=100)
...
sa.bind(sweeps=1000)
sa.partial(sweeps=1000)   # alternatively

would be a syntactic sugar for:

sa.next = functools.partial(sa.next, sweeps=1000)

QPU auto-embedding sampler fails for clique embedded subsamplers

Currently, QPUSubproblemAutoEmbeddingSampler will auto-embed with EmbeddingComposite any structured sampler it receives for qpu_sampler, thus turning it into an unstructured sampler - which is needed if we want to handle any subproblem out-of-the-box.

The problem is if user is aware of the embedding problems, and wants to pass in a structured sampler which can handle all subproblems we'll throw at it. For example, is it uses FixedEmbeddingComposite with a clique embedding.

Add PA example/workflow

Implement Population Annealing (PA) as an example workflow, and a reference importable workflow.

Add timeout to QPU samplers

Simulate until SAPI supports conditional submit.

num_reads error for TabuProblemSampler

bqm = dimod.BinaryQuadraticModel({'x': 0.0, 'y': 0.0, 'z': 8.0, 'a': 2.0, 'b': 0.0, 'c': 6.0},
          {('y', 'x'): 2.0, ('z', 'x'): -4.0, ('z', 'y'): -4.0,
          ('b', 'a'): 2.0, ('c', 'a'): -4.0, ('c', 'b'): -4.0, ('a', 'z'): -4.0},
          -1.0, 'BINARY')
sampler = samplers.TabuProblemSampler(bqm, tenure=2, timeout=5)
state = State.from_sample({'x': 0, 'y': 0, 'z': 1, 'a': 1, 'b': 1, 'c': 0}, bqm)
new_state = sampler.next(state)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-e5fcdae3a847> in <module>()
----> 1 new_state = sampler.next(state)

test\dwave-hybrid\hybrid\samplers.py in next(self, state)
    197         sampleset = self.sampler.sample(
    198             state.problem, init_solution=state.samples, tenure=self.tenure,
--> 199             timeout=self.timeout, num_reads=self.num_reads)
    200         return state.updated(samples=sampleset)
    201

c:\python27\lib\site-packages\tabu\sampler.pyc in sample(self, bqm, init_solution, tenure, scale_factor, timeout, num_reads)
    114
    115         if not isinstance(num_reads, int):
--> 116             raise TypeError("'num_reads' should be a positive integer")
    117         if num_reads < 1:
    118             raise ValueError("'num_reads' should be a positive integer")

TypeError: 'num_reads' should be a positive integer

Bug: reset stop event in Loop after stop

Stop flag/event/semaphore have to be reset in stoppable elements, otherwise next run will bail-out immediately.

Runnable.timers[<key>] fails before the first run

Make Runnable.timers and Runnable.counters a defaultdict (or alike).

Incompatible with dimod==0.8.8

For latest dimod, tests are failing with e.g.:

======================================================================
ERROR: test_default (tests.test_composers.TestSplatComposer)
First subsample is combined with the first sample.
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/radomir/work/dwave-hybrid/tests/test_composers.py", line 65, in test_default
    nextstate = SplatComposer().next(state)
  File "/home/radomir/work/dwave-hybrid/hybrid/composers.py", line 44, in next
    sample = next(state.samples.change_vartype(state.subsamples.vartype).samples())
TypeError: 'SamplesArray' object is not an iterator

The reason is a change in behaviour of SampleSet::samples() (from iterator to iterable).

Define a more flexible convergence criteria

Current implementation sets as a convergence criterion that the resulting energy is unchanged through convergence number of iterations. In practice that will be infrequently triggered because of fluctuations in the energy landscape. It would be helpful to define a more flexible criterion such as a percentage of energy decrease in a window of iterations. So setting, for example, convergence_x=10, convergence_y=5 would terminate if the energy has decreased >= 5% from its value 10 iterations ago. ("x", "y" could be more intuitive names.) Thank you!

Appreciate problem graph in Energy Impact Decomposer (or similar)

Right now EID deconstructs problems based solely on variables' energy impacts.

EID (or a new decomposer) should be able to traverse the problem graph, and select a connected subproblem.

We should support at least BFS and PFS traversal modes in EID (or in a new decomposer).

Ideally, traversing would be decoupled from variable weighting. (Weights could seed the traversal.)

Also, min/max chain length (or graph diameter) seem like useful parameters to control the crawl.

`Parallel` doesn't work with collection of `States` on input

Surfaced after #155 in "qbsolv-like-alt" example:

Unwind(...) | Parallel(Map(...), Map(...))

To properly fix this, we'll have to make traits more expressive, as well as traits validation more precise.

RandomConstraintDecomposer fails for certain constraint graphs

See: https://circleci.com/gh/dwavesystems/dwave-hybrid/2404

When a set of user-supplied constraints are translated into a graph, that graph might have gaps in a sequence of integer node names.

Later, random.choice(range(len(graph)) assumes nodes are sequentially numbered and fails when RNG hits that hole. Here, node zero was not present in the graph because constraints look like [set(), {...}, ...].

Missing subsamples trait on ReverseAnnealingAutoEmbeddingSampler

We need subsamples for the initial_state of the anneal.

Add time-based termination criterion to Loop(s)

For example:

Loop(<body>, convergence=3, timeout=30)

would iterate until output doesn't change over three consecutive iterations, or until 30 seconds of wall clock elapsed.

Alternatively, we could also inspect cumulative runtime of ?

Needed for #101.

Expose useful workflows as importable runnables

To facilitate workflow reuse, "structure sweep", and structure/parameter perturbation, make some standard workflows available under (perhaps) hybrid.reference or hybrid.workflow.

We can start with the existing examples (and then keep adding simpler workflows as they are discovered):

simple parallelized qbsolv-like
parallelized qbsolv
dialectic search
QPU + tabu postprocessing
parallel tempering
kerberos

Introduce per-block, per-run context id

Child's context id would be nested under parent's context id, similarly to logging namespaces.

Logging/tracing/profiling subsystem could then use fully qualified context ids to uniquely address events.

incompatible error for QPUSubproblemAutoEmbeddingSampler

The runnable branch with QPUSubproblemAutoEmbeddingSampler may raise error with message: ValueError: Problem graph incompatible with solver. Here's the sample code:

# just a random bqm
bqm = dimod.BinaryQuadraticModel({'x': 0.0, 'y': 0.0, 'z': 8.0, 'a': 2.0, 'b': 0.0, 'c': 6.0},
          {('y', 'x'): 2.0, ('z', 'x'): -4.0, ('z', 'y'): -4.0,
          ('b', 'a'): 2.0, ('c', 'a'): -4.0, ('c', 'b'): -4.0, ('a', 'z'): -4.0},
          -1.0, 'BINARY') 

qpusampler = DWaveSampler()

runnable = EnergyImpactDecomposer(max_size=1) | QPUSubproblemAutoEmbeddingSampler(num_reads=1000, qpu_sampler = qpusampler) | SplatComposer()                                                                                  
main = SimpleIterator(runnable, max_iter=10, convergence=3)

init_state = State.from_sample(min_sample(bqm), bqm)
solution = main.run(init_state).result()

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-4-34da8c1091f1> in <module>()
     10 
     11 init_state = State.from_sample(min_sample(bqm), bqm)
---> 12 solution = main.run(init_state).result()

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
    430                 raise CancelledError()
    431             elif self._state == FINISHED:
--> 432                 return self.__get_result()
    433             else:
    434                 raise TimeoutError()

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
    382     def __get_result(self):
    383         if self._exception:
--> 384             raise self._exception
    385         else:
    386             return self._result

~/anaconda3/lib/python3.6/concurrent/futures/thread.py in run(self)
     54 
     55         try:
---> 56             result = self.fn(*self.args, **self.kwargs)
     57         except BaseException as exc:
     58             self.future.set_exception(exc)

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
    341 
    342         with self.count('dispatch.next'):
--> 343             new_state = self.next(state)
    344 
    345         self.validate_output_state_traits(new_state)

~/anaconda3/lib/python3.6/site-packages/hybrid/flow.py in next(self, state)
    447 
    448         for iterno in range(self.max_iter):
--> 449             state = self.runnable.run(state).result()
    450             state_quality = self.key(state)
    451 

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
    423                 raise CancelledError()
    424             elif self._state == FINISHED:
--> 425                 return self.__get_result()
    426 
    427             self._condition.wait(timeout)

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
    382     def __get_result(self):
    383         if self._exception:
--> 384             raise self._exception
    385         else:
    386             return self._result

~/anaconda3/lib/python3.6/concurrent/futures/thread.py in run(self)
     54 
     55         try:
---> 56             result = self.fn(*self.args, **self.kwargs)
     57         except BaseException as exc:
     58             self.future.set_exception(exc)

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
    341 
    342         with self.count('dispatch.next'):
--> 343             new_state = self.next(state)
    344 
    345         self.validate_output_state_traits(new_state)

~/anaconda3/lib/python3.6/site-packages/hybrid/flow.py in next(self, state)
    134         for component in self.components:
    135             state = component.run(state, defer=False)
--> 136         return state.result()
    137 
    138     def error(self, exc):

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
    423                 raise CancelledError()
    424             elif self._state == FINISHED:
--> 425                 return self.__get_result()
    426 
    427             self._condition.wait(timeout)

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
    382     def __get_result(self):
    383         if self._exception:
--> 384             raise self._exception
    385         else:
    386             return self._result

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in submit(self, fn, *args, **kwargs)
     41         # customizable underlying executor (e.g. thread/process/celery/network)
     42         try:
---> 43             return Present(result=fn(*args, **kwargs))
     44         except Exception as exc:
     45             return Present(exception=exc)

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
    331             except Exception as exc:
    332                 with self.count('dispatch.resolve.error'):
--> 333                     return self.error(exc)
    334 
    335         if not getattr(self, '_initialized', False):

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in error(self, exc)
    312         must be explicitly silenced.
    313         """
--> 314         raise exc
    315 
    316     def dispatch(self, future):

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
    328         with self.count('dispatch.resolve'):
    329             try:
--> 330                 state = future.result()
    331             except Exception as exc:
    332                 with self.count('dispatch.resolve.error'):

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in result(self, timeout)
    423                 raise CancelledError()
    424             elif self._state == FINISHED:
--> 425                 return self.__get_result()
    426 
    427             self._condition.wait(timeout)

~/anaconda3/lib/python3.6/concurrent/futures/_base.py in __get_result(self)
    382     def __get_result(self):
    383         if self._exception:
--> 384             raise self._exception
    385         else:
    386             return self._result

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in submit(self, fn, *args, **kwargs)
     41         # customizable underlying executor (e.g. thread/process/celery/network)
     42         try:
---> 43             return Present(result=fn(*args, **kwargs))
     44         except Exception as exc:
     45             return Present(exception=exc)

~/anaconda3/lib/python3.6/site-packages/hybrid/core.py in dispatch(self, future)
    341 
    342         with self.count('dispatch.next'):
--> 343             new_state = self.next(state)
    344 
    345         self.validate_output_state_traits(new_state)

~/anaconda3/lib/python3.6/site-packages/hybrid/samplers.py in next(self, state)
    100 
    101     def next(self, state):
--> 102         response = self.sampler.sample(state.subproblem, num_reads=self.num_reads)
    103         return state.updated(subsamples=response)
    104 

~/anaconda3/lib/python3.6/site-packages/dimod/core/sampler.py in sample(self, bqm, **parameters)
    191         elif bqm.vartype is Vartype.BINARY:
    192             h, J, offset = bqm.to_ising()
--> 193             response = self.sample_ising(h, J, **parameters)
    194             response.change_vartype(Vartype.BINARY, energy_offset=offset)
    195             return response

~/anaconda3/lib/python3.6/site-packages/dwave/system/samplers/dwave_sampler.py in sample_ising(self, h, J, **kwargs)
    283         num_variables = len(active_variables)
    284 
--> 285         future = self.solver.sample_ising(h, J, **kwargs)
    286 
    287         return dimod.Response.from_future(future, _result_to_response_hook(active_variables, dimod.SPIN))

~/anaconda3/lib/python3.6/site-packages/dwave/cloud/solver.py in sample_ising(self, linear, quadratic, **params)
    196         # Our linear and quadratic objective terms are already separated in an
    197         # ising model so we can just directly call `_sample`.
--> 198         return self._sample('ising', linear, quadratic, params)
    199 
    200     def sample_qubo(self, qubo, **params):

~/anaconda3/lib/python3.6/site-packages/dwave/cloud/solver.py in _sample(self, type_, linear, quadratic, params)
    251         # Check the problem
    252         if not self.check_problem(linear, quadratic):
--> 253             raise ValueError("Problem graph incompatible with solver.")
    254 
    255         # Mix the new parameters with the default parameters

ValueError: Problem graph incompatible with solver.

Create `stoppable` mixin or decorator ...

... to simplify the development of Runnables which use a semaphore (threading.Event) to receive and handle the stop command.

There's a pattern that can be abstracted (see Loop and Identity).

Accept additional state variables in `State.from_*` factories

For example:

State.from_problem(bqm, beta=2.3)

Consistently propagate runopts on all Runnables

Right now, samplers ignore runopts provided to run().

Parallel SimulatedAnnealing samplers in threading mode block each other

s1 = hybrid.SimulatedAnnealingProblemSampler(num_reads=1000, sweeps=10000)
s2 = hybrid.SimulatedAnnealingProblemSampler(num_reads=1000, sweeps=10000)
p = hybrid.Parallel(s1, s2)

bqm = dimod.BinaryQuadraticModel({'a': 1}, {}, 0, 'BINARY')
state = hybrid.State.from_problem(bqm)

def time_runnable(runnable, init):
    runnable.run(init).result()
    return sum(runnable.timers['dispatch.next'])

t_s1 = time_runnable(s1, state)
t_s2 = time_runnable(s2, state)
t_p = time_runnable(p, state)

# (on my laptop)
# t_s1 ~ t_s2 ~ 0.2s
# t_p ~ t_s1 + t_s2 ~ 0.4s
# expected: t_p = max(t_s1, t_s2) ~ 0.2s

State.from_problem/from_bqm factory function

Simplify construction if we don't really care about the initial sample (or are happy with min/max/rnd):

state = State.from_problem(bqm, sample=<sample_like | factory_function | None>)

Propagate QPU sampling parameters in KerberosSampler

Sometimes is useful to propagate things like chain_length.

Alternative is to partially apply those arguments on the passed-in sampler's sample().

Conflate {non-,interruptable} samplers

Make Tabu{Problem,Subproblem}Sampler accept infinite timeout and make it stoppable.

Similarly for simulated annealing.

Should we allow a single Runnable instance to run multiple times concurrently?

Since Runnable.run() is (via dispatch()) offloading next() to an executor, it's possible to run a single instance's next multiple times in parallel.

This is not a problem if next() does not mutate the self, but it could potentially lead to a state lost, or even a deadlock if it does.

Should be categorically ban such a behaviour, or leave the responsibility to the block/workflow developer?

Deferred Runnable's runtime options

Runnable.__init__ to accept more options than it knows how to handle, defer all those to runtime, assuming run will use them.

In other words, support definition of run time options during construction time.

Add Const block

Imagine you wanting to reset initial states for a sampler:

random_tabu = hybrid.Const(samples=None) | hybrid.TabuProblemSampler()

Handle embedding failures

QPUSubproblemAutoEmbeddingSampler might fail on the embedding step even if embedding exists (due to heuristic nature of the algorithm used). We might provide some safety net for users by re-trying to embed some small number of times (e.g. retries=3 as a kwarg to the sampler init).

SA/Tabu samplers should use current samples for the initial solution

The current set of samples from the input state should be used to initialize starting solutions for the underlying SA and Tabu solvers.

Missing code for merge_substates in "Using the Framework" RTD

Reading along the examples provided in "Using the Framework", it is not apparent where merge_substates is defined.

Do we need to include def merge_substates() in the document from the following file?
https://github.com/dwavesystems/dwave-hybrid/blob/2614c00c07a6bc867292f66e19b73f9e453c8d37/examples/qbsolv-like-alt.py

Optimize State copy

Use a shallow copy, wrapped in proxy that will do deepcopy of an individual attribute only on demand (when modified, not when accessed).

Add a block for truncating samples

Unwinding context

Unwind block can propagate it requires unwinding behaviour from its children via runopts.

Add a block for merging States by merging samples

Support infinite interruptible Loop(s)

Loop/LoopUntilNoImprovement, LoopN, LoopWhileNoImprovement should:

support infinite looping
be interruptible (stoppable)

Racing Tabu samplers in threading mode doesn't work

t1 = hybrid.TabuProblemSampler(timeout=1000)
t2 = hybrid.TabuProblemSampler(timeout=2000)
w = hybrid.Race(t1, t2)

bqm = dimod.BinaryQuadraticModel({'a': 1}, {}, 0, 'BINARY')
state = hybrid.State.from_problem(bqm)
w.run(state).result()

# sum(w.timers['dispatch.next']) ~ 3 sec!
# -> it should be ~ 2 sec

Link to examples for samplers, composers, decomposers classes

Once this repo is public with a RTD site, add links to RTD/sampler, RTD/composers, and RTD/decomposers examples for command-line help users (because examples were moved out of class docstrings to RST file)

Workflow templates

For more involved workflows from #138, it might make sense to create them (and/or) as templates that would accept some workflow bits (runnables or parameters), and would construct a workflow according to a template.

Motivating pseudo-code example (see examples/qbsolv-like-alt.py):

ParallelizedSubsampler = WorkflowTemplate<subsampler, initial_state=None> hybrid.Map(
    subsampler
) | hybrid.Reduce(
    hybrid.Lambda(merge_substates),
    initial_state=initial_state
) | hybrid.SplatComposer()

Later we could use it:

qpu = ParallelizedSubsampler(hybrid.QPUSubproblemAutoEmbeddingSampler())
random = ParallelizedSubsampler(hybrid.RandomSubproblemSampler(), initial_state=some)

Generalize traits to support type checking

Trait could be:

'x': x in state
('x', Type): x in state and isinstance(x, Type)
predicate :: state -> Bool: predicate(state) true

Add a PT workflow example

Implement Parallel Tempering (PT) as an example workflow. Make compatible with the ICM block from #134.

Add diversity preserving samples reducer

Currently, one way of reducing the number of samples (in sampleset) is with the SliceSamples block (which acts only on one dimension, typically energy).

We would like to have a block that reduces the number of samples, but by eliminating "similar ones", and keeping relatively distinct ones in.

Remove interruptible samplers

Implement as infinite loop over Tabu/SA/etc.

Differentiate Identity from InterruptableIdentity

Identity should never block (even when inside Race), versus InterruptableIdentity which is meant to block in Race to prevent trivially winning and stopping remaining (useful) branches.

Generalize perf counters/timers

Timers are stored in a list, one per call, and counters are scalars updated on each call.

Provide a general underlying object ~ PerfCounter/StatCounter/VariableStats/Trace/similar that could be used to implement both behaviours + do on-update stats (count/min/max/mean/median).

Block developers could then use such PerfCounter to trace/log/aggregate values of interest, per iteration (e.g. (sub)problem size, max chain length, best sample energy - maybe even per branch, etc.)

I have installed dwave hybrid from source.

Any idea why am I getting this?

Thank you,

Add an ICM block

Implement an isoenergetic cluster move (ICM) block, perhaps according to this paper.

dwavesystems / dwave-hybrid Goto Github PK

dwave-hybrid's People

Contributors

Stargazers

Watchers

Forkers

dwave-hybrid's Issues

Recommend Projects

Recommend Topics

Recommend Org