QPU Solvers: Minor-Embedding¶
The D-Wave QPU minimizes the energy of an Ising spin configuration whose pairwise interactions lie on the edges of a QPU working graph, either a Chimera graph for the D-Wave 2000Q or a Pegasus graph for the Advantage. To solve an Ising spin problem with arbitrary pairwise interaction structure, the corresponding graph must be minor embedded into a QPU’s graph.
There are algorithms that can embed a problem of \(N\) variables in at most \(N^2\) qubits.
Ocean software’s minorminer provides embedding tools.
This chapter presents the following embedding topics:
Global Versus Local¶
Global embedding models each constraint as a BQM, adds all constraint models, and maps the aggregate onto the QPU graph. Advantages of this method are that it typically requires fewer qubits and shorter chains.
Locally structured embedding models each constraint locally within a subgraph, places the local subgraphs within the QPU graph, and then connects variables belonging to multiple local subgraphs. Advantages of this method, when the scopes of constraints are small, are typically that it is more scalable to large problems, requires less precision for parameters, and enforces qubit chains with lower coupling strengths.
Example¶
Fig. 51 Circuit of three connected AND gates.¶
This small example compares global and local embedding for a problem constructed with three connected AND gates.
You can embed a BQM representing an AND gate in a single Chimera unit cell, and this example uses a D-Wave 2000Q system for simplicity. The code below finds an embedding for a BQM constructed for an AND gate in a single Chimera unit cell.
>>> import minorminer
>>> import dwave_networkx as dnx
>>> from dimod.generators import and_gate
...
>>> bqm_and1 = and_gate('in1', 'in2', 'out')
...
>>> C1 = dnx.chimera_graph(1)
>>> embedding_and = minorminer.find_embedding(list(bqm_and1.quadratic.keys()), C1)
>>> embedding_and
{'in1': [5], 'in2': [3], 'out': [7, 1]}
The Multiple-Gate Circuit example in the Ocean documentation demonstrates how a BQM can be constructed in different ways for constraints representing a circuit of Boolean gates.
The two graphics below compare local and global embeddings of a BQM representing the three-AND circuit onto a D-Wave 2000Q QPU.
Figure 52 shows a local embedding: the BQM for each AND gate is manually embedded using Ocean’s
FixedEmbeddingCompositeinto a Chimera unit cell with the outputs connected to inputs.Figure 53 shows a global embedding: the combined BQM for the connected AND gates is embedded using Ocean’s
EmbeddingComposite.
Fig. 52 Example of local embedding for three connected AND gates.¶
Fig. 53 Example of global embedding for three connected AND gates.¶
In this small example, global embedding is likely more performant but for a larger number of such gates, local emebedding with its repeated structure likely would keep chains shorter and uniform across the entire problem (assuming simple and sparse connectivity between parts).
Further Information¶
[Bia2016] compares global and local methods of embedding in the context of CSPs and discusses a rip-up and replace method.
[Boo2016] discusses clique minor generation.
[Cai2014] gives a practical heuristic for finding graph minors.
[Jue2016] discusses using FPGA-like routing to embed.
[Ret2017] describes embedding quantum-dot cellular automata networks.
Chain Management¶
Similar to Lagrangian relaxation, you map a given problem’s variable \(s_i\) onto chain \(\{q_i^{(1)}, \cdots, q_i^{(k)}\}\) while encoding equality constraint \(q_i^{(j)} = q_i^{(j')}\) as an Ising penalty \(-M q_i^{(j)} q_i^{(j')}\) of weight \(M>0\).
The following considerations and recommendations apply to chains.
Prefer short chains to long chains.
Prefer uniform chain lengths to uneven chains.
Balance chain strength and problem range. Estimate chain strength and set just slightly above the minimum threshold needed, using strategies for auto-adjusting these chains. When mapping a problem’s variable to qubits chains, the penalties for equality constraints should be (1) large enough so low-energy configurations do not violate these constraints and (2) the smallest weight that enforces the constraints while enabling precise problem statement (on \(\vc{h}\) and \(\vc{J}\)) and efficient exploration of the search space. An effective procedure incrementally updates weights until the equality constraints are satisfied.
See also the Imprecision of Biases section.
Example¶
This example embeds a BQM representing a 30-node signed-social network problem and then looks at the effects of different chain-strength settings.
>>> import networkx as nx
>>> import random
>>> import numpy as np
>>> import dwave_networkx as dnx
>>> import dimod
>>> from dwave.system import DWaveSampler, LazyFixedEmbeddingComposite
>>> import dwave.inspector
>>> # Create a problem
>>> G = nx.generators.complete_graph(30)
>>> G.add_edges_from([(u, v, {'sign': 2*random.randint(0, 1) - 1}) for u, v in G.edges])
>>> h, J = dnx.algorithms.social.structural_imbalance_ising(G)
>>> bqm = dimod.BQM.from_ising(h, J)
>>> # Sample on a D-Wave system
>>> num_samples = 1000
>>> sampler = LazyFixedEmbeddingComposite(DWaveSampler())
>>> sampleset = sampler.sample(bqm, num_reads=num_samples)
You can now analyze the solution looking for the affects of your chain-strength setting in various ways.
As a first iteration, it’s convenient to use the Ocean default chain strength.
The LazyFixedEmbeddingComposite class sets
a default chain strength using the
uniform_torque_compensation() function
to calculate a reasonable value. For this problem, with the embedding found
heuristically, it calculated a chain strength of about 7.
>>> print(sampleset.info["embedding_context"]["chain_strength"])
7.614623037288188
You can check the length of the longest chain.
>>> chains = sampleset.info["embedding_context"]["embedding"].values()
>>> print(max(len(chain) for chain in chains))
6
You can verify that the default chain strength for this problem is strong enough so few chains are broken.
>>> print("Percentage of samples with >10% breaks is {} and >0 is {}.".format(
... np.count_nonzero(sampleset.record.chain_break_fraction > 0.10)/num_samples*100,
... np.count_nonzero(sampleset.record.chain_break_fraction > 0.0)/num_samples*100))
Percentage of samples with >10% breaks is 0.0 and >0 is 17.5.
You can also look at the embedding and histograms of solution energies using Ocean’s problem inspector tool.
>>> dwave.inspector.show(sampleset)
Figure 54 shows the BQM embedded in an Advantage QPU.
Fig. 54 BQM representing a social-network problem of 30 nodes embedded in an Advantage QPU.¶
The following graphs show histograms of the returned solutions’ energies for different chains strengths:
Figure 55 has the default chain strength, which for this problem was calculated as about 7.
Figure 56 has a chain strength manually set to 1 (identical to the maximum bias for the problem). 1
Figure 57 has a chain strength manually set to 14 (double the default value for this problem).
- 1
You can set a chain strength relative to your problem’s largest bias by using, for example, the
scaled()function.>>> from dwave.embedding.chain_strength import scaled >>> sampleset = sampler.sample(bqm, num_reads=num_samples, chain_strength=scaled)
Fig. 55 Energy histogram for the social-network problem with a chain strength of ~7.¶
Fig. 56 Energy histogram for the social-network problem with a chain strength of 1.¶
Fig. 57 Energy histogram for the social-network problem with a chain strength of 14.¶
You can see that setting the chain strength too low compared to the problem’s biases results in high chain breakage and consequently few good solutions; setting it too high distorts the problem.
Further Information¶
The Multiple-Gate Circuit example in the Ocean documentation is a good introductory example of the effects of setting chain strengths.
The Using the Problem Inspector example demonstrates using Ocean’s problem inspector tool for examining embeddings and setting chain strengths.
[Rie2014] studies embedding and parameter setting, and their effects on problem solving in the context of optimization problems.
[Ven2015b] discusses effects of embedding the Sherrington-Kirkpatrick problem.
Embedding Complete Graphs¶
Embeddings for cliques (fully-connected graphs) can be very useful: a minor-embedding for a \(K_n\) clique can be used for all minors of that graph. This means that if your application needs to submit to the QPU a series of problems of up to \(n\) variables, having an embedding for the \(K_n\) graph lets you simply reuse it for all those submissions, saving the embedding-computation time in your application’s runtime execution.
Using a clique embedding can have a high cost for sparse graphs because chain lengths increase significantly for high numbers of variables.
Example: Largest Chimera Cliques¶
The largest complete graph \(K_V\) that is a minor of a \(M\times N\times L\) Chimera graph has \(V=1+L\min(M,N)\) vertices. For example, 65 vertices is the theoretical maximum on a D-Wave 2000Q QPU, which supports a C16 Chimera graph (a \(16 {\rm x} 16\) matrix of 8-qubit unit cells for up to2 \(2MNL=2 \times 16 \times 16 \times 4=2048\) qubits).
- 2
The yield of a working graph is typically less than 100%.
Table 26 shows some example embeddings of complete graphs on a D-Wave 2000Q QPU.
Complete Graph |
Minor of Chimera Working Graph |
|---|---|
\(K_5\) |
\(1\times 1\times 4\) (single cell) |
\(K_9\) |
\(2\times 2\times 4\) (four cells) |
\(K_{65}\) |
\(16\times 16\times 4\) (all cells) |
Example: Chain Lengths for Cliques on Pegasus & Chimera¶
Table 27 shows some example embeddings of complete graphs versus chain lengths for both QPU topologies with 95% yields. For a given maximum chain length, you can embed cliques of about the following sizes in Pegasus P16 and Chimera C16 topologies with working graphs simulating 95% yield (by random removal of 5% of nodes and 0.5% of edges to represent inactivated qubits and couplers):
Chain Length |
Chimera |
Pegasus |
|---|---|---|
1 |
\(K_2\) |
\(K_4\) |
2 |
\(K_4\) |
\(K_{10}\) |
4 |
\(K_{12}\) |
\(K_{30}\) |
10 |
\(K_{28}\) |
\(K_{71}\) |
For a Pegasus graph with 100% yield the largest complete graph that is embeddable is \(K_{150}\) with chain length of 14. QPUs typically do not achieve 100% yield.
Example: Clique-Embedding a Sparse BQM¶
Figure 58 shows an example BQM constructed from
a sparse NetworkX graph,
chvatal_graph(). This example embeds the BQM
onto an Advantage QPU in two ways: (1) using the standard
minorminer heuristic of
the EmbeddingComposite class and (2) using
a clique embedding found by the DWaveCliqueSampler
class.
Fig. 58 BQM based on a sparse graph.¶
>>> from dwave.system import DWaveSampler, EmbeddingComposite, DWaveCliqueSampler
>>> import networkx as nx
>>> import dimod
>>> import random
>>> import dwave.inspector
>>> # Create a small, sparse BQM from a NetworkX graph
>>> G = nx.generators.small.chvatal_graph()
>>> for edge in G.edges:
... G.edges[edge]['quadratic'] = random.choice([1,-1])
>>> bqm = dimod.from_networkx_graph(G,
... vartype='BINARY',
... edge_attribute_name='quadratic')
>>> sampleset = EmbeddingComposite(DWaveSampler()).sample(bqm, num_reads=1000)
>>> sampleset_clique = DWaveCliqueSampler().sample(bqm, num_reads=1000)
The following graphs show both embeddings:
Figure 59 is an embedding found for the sparse graph.
Figure 60 is a clique embedding in which the BQM graph is a minor.
Fig. 59 Embedding found for the sparse graph of the problem.¶
Fig. 60 Clique embedding that includes the sparse graph of the problem.¶
Clearly the clique embedding requires more and longer chains.
Further Information¶
[Pel2021] proposes a method of parallel quantum annealing that makes use of available qubits by embedding several small problems in the same annealing cycle.
[Zbi2020] proposes two algorithms, Spring-Based MinorMiner (SPMM) and Clique-Based MinorMiner (CLMM), for minor-embedding QUBO problems into Chimera and Pegasus graphs.
Exploring the Pegasus Topology Jupyter Notebook.
Reusing Embeddings¶
For problems that vary only the biases and weights on a fixed graph, you can set a good embedding once before submitting the problem to the QPU. There is no need to recompute the embedding (a time-consuming operation) for every submission.
Pre-embedding Local Constraint Structures¶
The structure of some problems contains repeated elements; for example, the multiple AND gates, half adders, and full adders in the Factoring example. Such problems may benefit from being embedded with repeating block structures for the common elements, with connectivity then added as needed.
Example¶
Fig. 61 Circuit of three Boolean gates.¶
This small example pre-embeds three Boolean gates.
You can embed a BQM representing an AND or OR gate in a single Chimera unit cell, and this example uses a D-Wave 2000Q system for simplicity. The code below finds an embedding for a BQM constructed for AND and OR gates in a single Chimera unit cell. You can then shift the gates to other unit cells by adding \(8n\) to the embedding values, where \(n\) is the selected unit cell.
>>> import minorminer
>>> import dwave_networkx as dnx
>>> from dimod.generators import and_gate, or_gate
...
>>> C1 = dnx.chimera_graph(1)
...
>>> bqm_and1 = and_gate('in11', 'in12', 'out1')
>>> embedding_and = minorminer.find_embedding(list(bqm_and1.quadratic.keys()), C1)
>>> embedding_and
{'in11': [5], 'in12': [3], 'out1': [7, 1]}
...
>>> bqm_or2 = or_gate('in21', 'in22', 'out2')
>>> embedding_or = minorminer.find_embedding(list(bqm_or2.quadratic.keys()), C1)
>>> embedding_or
{'in21': [2], 'in22': [6], 'out2': [0, 7]}
Fig. 62 Circuit of three Boolean gates pre-embedded in a D-Wave 2000Q QPU.¶
Virtual Graphs¶
The D-Wave virtual graph feature simplifies the process of minor-embedding
by enabling you to more easily create, optimize, use, and reuse an embedding
for a given working graph. When you submit an embedding and specify a chain strength
using Ocean’s VirtualGraphComposite class, it
automatically calibrates the qubits in a chain to compensate for the effects of
unintended biases—see
integrated control errors (ICE) 1—
caused by QPU imperfections.