.. _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.