Repository: dwavesystems/dimod

Issue:
Embedding QUBO leads to out-of-range linear terms.
If I determine the correct scaling factor to scale a QUBO such that the Ising form fits in the QPU range, I should be able to scale the QUBO by this amount, embed it, and solve the Ising.  However, the embedding causes some linear QUBO terms to be out of range in the resulting Ising model.  As discussed with @arcondello.

https://github.com/dwavesystems/dimod/blob/8ebfffa42319aa4850cfc5a1c99a8711eac44722/dimod/embedding/transforms.py#L125

Discussion:

Patch:
diff --git a/dimod/embedding/transforms.py b/dimod/embedding/transforms.py
index 4acba9fe..42a65912 100644
--- a/dimod/embedding/transforms.py
+++ b/dimod/embedding/transforms.py
@@ -35,7 +35,8 @@ __all__ = ['embed_bqm',
            ]
 
 
-def embed_bqm(source_bqm, embedding, target_adjacency, chain_strength=1.0):
+def embed_bqm(source_bqm, embedding, target_adjacency, chain_strength=1.0,
+              smear_vartype=None):
     """Embed a binary quadratic model onto a target graph.
 
     Args:
@@ -54,6 +55,11 @@ def embed_bqm(source_bqm, embedding, target_adjacency, chain_strength=1.0):
             Magnitude of the quadratic bias (in SPIN-space) applied between variables to create chains. Note
             that the energy penalty of chain breaks is 2 * `chain_strength`.
 
+        smear_vartype (:class:`.Vartype`, optional, default=None):
+            When a single variable is embedded, it's linear bias is 'smeared' evenly over the
+            chain. This parameter determines whether the variable is smeared in SPIN or BINARY
+            space. By default the embedding is done according to the given source_bqm.
+
     Returns:
         :obj:`.BinaryQuadraticModel`: Target binary quadratic model.
 
@@ -102,6 +108,13 @@ def embed_bqm(source_bqm, embedding, target_adjacency, chain_strength=1.0):
         >>> # Snipped above response for brevity
 
     """
+    if smear_vartype is Vartype.SPIN and source_bqm.vartype is Vartype.BINARY:
+        return embed_bqm(source_bqm.spin, embedding, target_adjacency,
+                         chain_strength=chain_strength, smear_vartype=None).binary
+    elif smear_vartype is Vartype.BINARY and source_bqm.vartype is Vartype.SPIN:
+        return embed_bqm(source_bqm.binary, embedding, target_adjacency,
+                         chain_strength=chain_strength, smear_vartype=None).spin
+
     # create a new empty binary quadratic model with the same class as source_bqm
     target_bqm = source_bqm.empty(source_bqm.vartype)
 


Test patch:
diff --git a/tests/test_embedding_transforms.py b/tests/test_embedding_transforms.py
index 3bdeb45a..c0342608 100644
--- a/tests/test_embedding_transforms.py
+++ b/tests/test_embedding_transforms.py
@@ -423,3 +423,25 @@ class TestEmbedBQM(unittest.TestCase):
 
         for v in itertools.chain(*embedding.values()):
             self.assertIn(v, target_bqm)
+
+    @unittest.skipUnless(_networkx, "No networkx installed")
+    def test_energy_range_embedding(self):
+        # start with an Ising
+        bqm = dimod.BinaryQuadraticModel.from_ising({}, {(0, 1): 1, (1, 2): 1, (0, 2): 1})
+
+        # convert to BINARY
+        bqm.change_vartype(dimod.BINARY, inplace=True)
+
+        # embedding
+        embedding = {0: ['a', 'b'], 1: ['c'], 2: ['d']}
+        graph = nx.cycle_graph(['a', 'b', 'c', 'd'])
+        graph.add_edge('a', 'c')
+
+        # embed
+        embedded = dimod.embed_bqm(bqm, embedding, graph, chain_strength=1, smear_vartype=dimod.SPIN)
+
+        preferred = dimod.BinaryQuadraticModel({'a': 0.0, 'b': 0.0, 'c': 0.0, 'd': 0.0},
+                                               {('a', 'c'): 0.5, ('b', 'c'): 0.5, ('c', 'd'): 1.0,
+                                                ('a', 'd'): 1.0, ('a', 'b'): -1.0}, 1.0, dimod.SPIN)
+
+        self.assertEqual(embedded.spin, preferred)