Minor-Embedding a Problem

The D-Wave QPU minimizes the energy of an Ising spin configuration whose pairwise interactions lie on the edges of an \(M,N,L\) Chimera graph. To solve a given Ising spin problem with arbitrary pairwise interaction structure, you minor embed its graph into a Chimera graph by using qubits to represent missing edges.

Similar to Lagrangian relaxation, you map a given problem’s variable \(s_i\) onto a set of qubits \(\{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 Background chapter provides several introductory examples of embeddings.

There are algorithms that can embed a problem of \(N\) variables in at most \(N^2\) qubits.

General Considerations

The following considerations apply to minor embedding.

  • Global embedding models each constraint as an Ising model, adds all constraint models, and maps the aggregate onto the Chimera graph. Advantages of this method are that it typically requires fewer qubits and shorter chains of connected qubits for logical problem variables.
  • Locally structured embedding models each constraint locally within a subgraph, places the local subgraphs within the Chimera 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.
  • 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 the Overcoming Imprecisions of Qubit Biases and Coupling Strengths section.
  • Logically identical embeddings can have different higher energy spectrums, thus different performances.
  • Qubits used as couplers cannot be used as problem variables, reducing the effective size of the Ising problem that can be solved. Use embeddings that waste the fewest qubits.

Software Tools

Further Information

  • The Embedding section discusses the above more fully.
  • [Bia2016] compares global and local methods of embedding in the context of CSPs and discusses a rip-up and replace method.
  • [Cai2014] gives a practical heuristic for finding graph minors.
  • [Boo2016] discusses clique minor generation.
  • [Ret2017] describes embedding quantum-dot cellular automata networks.
  • [Jue2016] discusses using FPGA-like routing to embed.
  • [Ven2015b] discusses effects of embedding the Sherrington-Kirkpatrick problem.
  • [Rie2014] studies embedding and parameter setting, and their effects on problem solving in the context of optimization problems.

Chain Management

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.

Embedding Complete Graphs

The largest complete (all \(V\) vertices interconnected) graph \(K_V\) that is a minor of a \(M\times N\times L\) 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[1] \(2MNL=2 \times 16 \times 16 \times 4=2048\) qubits).

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

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

Table 21 Example 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)

The \(K_9\) embedded graph minor for a \(2\times2\times4\) graph is shown in Figure 41.

Diagram of the Chimera graph showing :math:`K_9` embedding.

Fig. 41 Embedding a \(K_9\) graph into \(2\times 2\times 4\); A and B indicate two different blocks of 4 variables. Equivalently labeled qubits are connected by edge penalties.

Specific connectivity requirements may have problem-specific embeddings that make more effective use of qubits than using Chimera as the complete graph for immediate embedding of all Ising problems defined on \(V\) variables.

Further Information

Finding Better Embeddings

Where the exact form of a problem is malleable, for example in some machine learning problems, simplify by assuming that each node in the original graph is mapped to a single node in Chimera. Fit the problem into Chimera by maximizing the total magnitude of \(J_{i,j}\) mapped to Chimera edges; that is,

\[\vc{M}^\star = \argmax_{\vc{M}} \sum_{i>j} \sum_{(q,q')\in E}|J_{i,j}| m_{i,q} m_{j,q'},\]

where \(\vc{M}\) is subject to the mapping constraints: \(\sum_q m_{i,q} = 1\), for all problem variables \(i\), and \(\sum_i m_{i,q}\le 1\), for all Chimera nodes \(q\).

For linear time embedding, apply a greedy heuristic to approximately maximize the objective.

Further Information

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.

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 provides tools and interactive examples that simplify 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 these tools, they automatically calibrate the qubits in a chain to compensate for the effects of biases that may be introduced as a result of strong couplings.

Further Information

  • D-Wave provides an open-source tool, dwave_virtual_graph on GitHub
  • [Dwave6] is a white paper describing measured performance improvements from using virtual graphs.