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

image

Fig. 47 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
>>> import dwavebinarycsp
>>> import dwavebinarycsp.factories.constraint.gates as gates
...
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(gates.and_gate(['in11', 'in12', 'out1'], name='AND1'))
>>> bqm_and1 = dwavebinarycsp.stitch(csp)
...
>>> 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 48 shows a local embedding: the BQM for each AND gate is manually embedded using Ocean’s FixedEmbeddingComposite into a Chimera unit cell with the outputs connected to inputs.
  • Figure 49 shows a global embedding: the combined BQM for the connected AND gates is embedded using Ocean’s EmbeddingComposite.
image

Fig. 48 Example of local embedding for three connected AND gates.

image

Fig. 49 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 50 shows the BQM embedded in an Advantage QPU.

image

Fig. 50 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 51 has the default chain strength, which for this problem was calculated as about 7.
  • Figure 52 has a chain strength manually set to 1 (identical to the maximum bias for the problem). [1]
  • Figure 53 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)
image

Fig. 51 Energy histogram for the social-network problem with a chain strength of ~7.

image

Fig. 52 Energy histogram for the social-network problem with a chain strength of 1.

image

Fig. 53 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

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 to[2] \(2MNL=2 \times 16 \times 16 \times 4=2048\) qubits).

[2]The yield of a working graph is typically less than 100%.

Table 27 shows some example embeddings of complete graphs on a D-Wave 2000Q QPU.

Table 27 Complete Embeddings 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 28 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):

Table 28 Complete Embeddings Versus Chain Length for 95% Yields.
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 54 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.

image

Fig. 54 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 55 is an embedding found for the sparse graph.
  • Figure 56 is a clique embedding in which the BQM graph is a minor.
image

Fig. 55 Embedding found for the sparse graph of the problem.

image

Fig. 56 Clique embedding that includes the sparse graph of the problem.

Clearly the clique embedding requires more and longer chains.

Further Information

  • Leap’s Exploring Pegasus 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

image

Fig. 57 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
>>> import dwavebinarycsp
>>> import dwavebinarycsp.factories.constraint.gates as gates
...
>>> C1 = dnx.chimera_graph(1)
...
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(gates.and_gate(['in11', 'in12', 'out1'], name='AND1'))
>>> bqm_and1 = dwavebinarycsp.stitch(csp)
...
>>> embedding_and = minorminer.find_embedding(list(bqm_and1.quadratic.keys()), C1)
>>> embedding_and
{'in1': [5], 'in2': [3], 'out': [7, 1]}
>>> csp = dwavebinarycsp.ConstraintSatisfactionProblem(dwavebinarycsp.BINARY)
>>> csp.add_constraint(gates.or_gate(['in21', 'in22', 'out2'], name='OR2'))
>>> bqm_or2 = dwavebinarycsp.stitch(csp)
...
>>> embedding_or = minorminer.find_embedding(list(bqm_or2.quadratic.keys()), C1)
>>> embedding_or
{'in21': [2], 'in22': [6], 'out2': [0, 7]}
image

Fig. 58 Circuit of three Boolean gates pre-embedded in a D-Wave 2000Q QPU.

Further Information

  • [Ada2015] describes embedding an RBM on the D-Wave system by mapping the visible nodes to chains of vertical qubits and hidden nodes to chains of horizontal qubits.

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.

Further Information

  • [Dwave6] is a white paper describing measured performance improvements from using virtual graphs.