.. _embedding_sdk: =============== Minor-Embedding =============== To solve an arbitrarily posed binary quadratic problem directly on a D-Wave system requires mapping, called *minor embedding*, to the :ref:topology_sdk of the system's quantum processing unit (QPU). This preprocessing can be done by a composed sampler consisting of the :class:~dwave.system.samplers.DWaveSampler() and a composite that performs minor-embedding. (This step is handled automatically by :class:~dwave.system.samplers.LeapHybridSampler() and :doc:dwave-hybrid  reference samplers.) For example, a simple two-variable :term:bqm, .. math:: E(\bf{s}) = - s_0 s_1 \qquad\qquad s_i\in\{-1,+1\} might be embedded to two connected qubits, such as 633 and 3603 on an Advantage system: .. figure:: ../_images/embedding_2var2qubits.png :align: left :name: Embedding2var2qubits :scale: 40 % :alt: Two-variable problem embedded into two qubits. Two-variable problem, shown on the left as a graph, is embedded in two connected qubits on an Advantage, shown on the right against the Pegasus topology. Variable :math:s_0, highlighted in dark magenta, is represented by qubit number 633 and variable :math:s_1 is represented by qubit 3603. (This and similar images in this section are generated by Ocean's :doc:problem inspector  tool. In the Advantage :term:Pegasus topology, most qubits are connected to fifteen other qubits, so other valid minor-embeddings might be 633 for :math:s_0 and 634 for :math:s_1 or 4628 for :math:s_0 and 1749 for :math:s_1. Chains ------ Larger problems often require chains because the :doc:QPU topology  is not fully connected. For example, a :math:K_5 graph is not *native* to the :term:Pegasus topology, meaning that the following five-variable :term:bqm with a clique (fully-connected) :math:K_5 graph cannot be represented by five qubits on an Advantage QPU. >>> import dimod >>> bqm = dimod.generators.doped(1, 5) >>> bqm.add_linear_from({v: 1 for v in bqm.variables}) Instead, at least one variable is represented by a *chain* of physical qubits, as in this minor-embedding: .. figure:: ../_images/embedding_5var6qubits.png :align: left :name: Embedding5var6qubits :scale: 60 % :alt: Five-variable fully-connected problem embedded into six qubits. Five-variable :math:K_5 fully-connected problem, shown on the left as a graph, is embedded in six qubits on an Advantage, shown on the right against the Pegasus topology. Variable 0, highlighted in dark magenta, is represented by two qubits, 1975 and 4840. The minor-embedding above was derived from the hueristic used by :class:~dwave.system.composites.EmbeddingComposite() on the working graph of an Advantage selected by :class:~dwave.system.samplers.DWaveSampler(): >>> from dwave.system import DWaveSampler, EmbeddingComposite, FixedEmbeddingComposite >>> sampler = EmbeddingComposite(DWaveSampler()) Other qubits might have been chosen; for example, >>> sampler = FixedEmbeddingComposite(DWaveSampler(), ... embedding={0: [4408, 2437], 1: [4333], 2: [4348], 3: [2497], 4: [2512]}) # doctest: +SKIP intentionally sets the embedding shown below to represent this same :math:K_5 graph: .. figure:: ../_images/embedding_5var6qubits_2.png :align: left :name: Embedding3var6qubits_2 :scale: 60 % :alt: Three-variable fully-connected problem embedded into six qubits. Five-variable :math:K_5 fully-connected problem, shown on the left as a graph, is embedded in six qubits on an Advantage, shown on the right against the Pegasus topology. Variable 0, highlighted in dark magenta, is represented by two qubits, 4408 and 2437. .. _concepts__chain_strength: Chain Strength -------------- For a chain of qubits to represent a variable, all its constituent qubits must return the same value for a sample. This is accomplished by setting a strong coupling to the edges connecting these qubits. That is, for the qubits in a chain to be likely to return identical values, the coupling strength for their connecting edges must be strong compared to the coupling with other qubits that influence non-identical outcomes. The :math:K_5 BQM has ten ground states (best solutions). These are shown below---solved by brute-force stepping through all possible configurations of values for the variables---with ground-state energy -3.0: >>> print(dimod.ExactSolver().sample(bqm).lowest()) 0 1 2 3 4 energy num_oc. 0 +1 +1 -1 -1 -1 -3.0 1 1 -1 +1 +1 -1 -1 -3.0 1 2 +1 -1 +1 -1 -1 -3.0 1 3 -1 -1 +1 +1 -1 -3.0 1 4 -1 +1 -1 +1 -1 -3.0 1 5 +1 -1 -1 +1 -1 -3.0 1 6 -1 -1 -1 +1 +1 -3.0 1 7 -1 -1 +1 -1 +1 -3.0 1 8 -1 +1 -1 -1 +1 -3.0 1 9 +1 -1 -1 -1 +1 -3.0 1 ['SPIN', 10 rows, 10 samples, 5 variables] These solutions are states in which two variables are assigned one value and the remaining three variables the complementary value; for example two are :math:-1 and three :math:+1 as shown below. .. figure:: ../_images/embedding_5var6qubits_groundsolution.png :align: left :name: Embedding3var6qubitsGroundSolution :scale: 50 % :alt: Three-variable fully-connected problem embedded into six qubits. Ground state of the five-variable :math:K_5 fully-connected problem. A typical submission of the problem to a quantum computer, using the same minor-embedding as the previous subsection and the default chain strength, returned all the ground states, with these solutions constituting over 90% of the returned samples. >>> sampleset = sampler.sample(bqm, num_reads=1000) # doctest: +SKIP >>> print(sampleset.lowest()) # doctest: +SKIP 0 1 2 3 4 energy num_oc. chain_. 0 -1 +1 +1 -1 -1 -3.0 69 0.0 1 +1 -1 -1 +1 -1 -3.0 115 0.0 2 +1 -1 -1 -1 +1 -3.0 95 0.0 3 +1 -1 +1 -1 -1 -3.0 84 0.0 4 -1 -1 -1 +1 +1 -3.0 116 0.0 5 -1 -1 +1 +1 -1 -3.0 99 0.0 6 -1 -1 +1 -1 +1 -3.0 91 0.0 7 +1 +1 -1 -1 -1 -3.0 71 0.0 8 -1 +1 -1 +1 -1 -3.0 98 0.0 9 -1 +1 -1 -1 +1 -3.0 95 0.0 10 +1 -1 -1 +1 -1 -3.0 1 0.2 ['SPIN', 11 rows, 934 samples, 5 variables] The default chain strength is set by the :func:~dwave.embedding.chain_strength.uniform_torque_compensation function: >>> print(round(sampleset.info['embedding_context']['chain_strength'], 3)) # doctest: +SKIP 2.828 Resubmitting with a much lower chain strength produced less satisfactory results (only ~10% of returned samples are ground states). >>> sampleset = sampler.sample(bqm, num_reads=1000, chain_strength=1) # doctest: +SKIP >>> print(sampleset.lowest()) # doctest: +SKIP 0 1 2 3 4 energy num_oc. chain_. 0 -1 +1 +1 -1 -1 -3.0 12 0.0 1 +1 -1 -1 +1 -1 -3.0 13 0.0 2 +1 -1 -1 -1 +1 -3.0 13 0.0 3 +1 -1 +1 -1 -1 -3.0 16 0.0 4 -1 -1 -1 +1 +1 -3.0 6 0.0 5 -1 -1 +1 +1 -1 -3.0 10 0.0 6 -1 -1 +1 -1 +1 -3.0 17 0.0 7 +1 +1 -1 -1 -1 -3.0 17 0.0 8 -1 +1 -1 +1 -1 -3.0 10 0.0 9 -1 +1 -1 -1 +1 -3.0 7 0.0 ['SPIN', 10 rows, 121 samples, 5 variables] Many of the remaining ~90% of returned samples have "broken chains", meaning qubits of a chain did not have identical values due to insufficiently strong coupling compared to quadratic coefficients of interactions (of the variable the chain represented) with other variables. .. figure:: ../_images/embedding_5var6qubits_broken.png :align: left :name: Embedding5var6qubitsBroken :scale: 60 % :alt: Three-variable fully-connected problem embedded into six qubits with a broken chain. Five-variable :math:K_5 fully-connected problem is embedded in six qubits on an Advantage using a low chain strength. Variable 0, highlighted in dark magenta, is represented by two qubits, numbers 2437 and 4408. The displayed solution has a broken chain: qubit 4408 returned a value of :math:-1 (represented by a white dot) while qubit 2347 returned a value of :math:+1 (a blue dot). The logical representation of the problem, on the left, shows a half-white, half-blue dot to represent a value based on a broken chain. For information on handling embedding and chains, see the following documentation: * :ref:and, :ref:multi_gate, and :ref:inspector_graph_partitioning examples Show through some simple examples how to embed and set chain strength. * :std:doc:minorminer  tool Is the hueristic used by common Ocean embedding :term:composite\ s. * :std:doc:problem inspector  tool Visualizes embeddings. * :std:doc:dwave-system  Composites section Provides embedding composites * :std:doc:dwave-system  Embedding section Describes chain-related functionality.