dwavesystems / dwave-system

An API for easily incorporating the D-Wave system as a sampler, either directly or through Leap's cloud-based hybrid samplers
https://docs.ocean.dwavesys.com/
Apache License 2.0
90 stars 64 forks source link

Allow greedy substitute sampler in `MockDWaveSampler` to try harder #474

Closed randomir closed 1 year ago

randomir commented 1 year ago

Current Problem Some doctests (that use MockDWaveSampler implicitly) are failing (sporadically) because they were written with TabuSampler level of result quality in mind, yet we switched to greedy sampler in #443.

One example of a such failure is visible here, as part of #436.

Proposed Solution Introduce "oversampling rate" parameter used by the greedy sampler in MockDWaveSampler. Oversampling would default to none, but could be tweaked by doctests init code. Mock sampler would take num_reads * oversampling_rate greedy samples, but would truncate to and return only the best num_reads samples.

Albeit this is only a probabilistic fix, setting oversampling rate to >10 is shown to regularly resolve all failures of current tests.

Alternatives Considered

  1. Simplify problems used in (mock) tests and doctests to strictly convex, thus guaranteed to be solved by the greedy substitute sampler. This might hurt the pedagogical aspect of examples in docs.
  2. Revert to TabuSampler. Goes against the rationale to switch to greedy in the first place.

/cc @jackraymond @JoelPasvolsky

jackraymond commented 1 year ago

An alternative possibility, that I like is for MockDWaveSampler() to swap in the ground state for the first sample when num_variables<=X, where X could be as large as 16. Determining the ground state by exhaustive enumeration is fast enough in this regime, and it would allow us to avoid probabilistic guarantees on our test up to a scale X. Any "test" bigger than X~10 that is relying on probabilistic guarantees is probably one that we should replace.

randomir commented 1 year ago

@jackraymond, I initially didn't like the discontinuities this approach has -- only one ground state is inserted, only up to a certain problem size. But on second thought, the ground state inserted can conceivably be seen as generated by greedy descent starting from a "lucky" initial state. And it's great that's it's deterministic for the class of problems we should use in our (doc)tests anyway. So, let's go with your proposal instead! I'll open a PR.

jackraymond commented 1 year ago

If you really wanted, you could make things a bit smoother as a function of system size (1 of several options):

Solve H(s) by greedy descent from either (a) random s (for randomized) or (b) s= all 1 (deterministic). To get s0. Define a new problem over the first X variables only, fields are conditioned on the s0 values for indexes higher than X: h_i(first X) = hi + sum{j'>=X} (J{ij'} +J{j'i}) s_i s0_j, Jij = Jij, for i,j <X Minimize this problem exactly and substute the first X values in s0 by this solution.

However, I think its simpler to document and maintain a hard cut off. Turn it on by default and allow users to turn it off.