Introduction

minorminer is a tool for finding graph minor embeddings, developed to embed Ising problems onto quantum annealers (QA). While it can be used to find minors in arbitrary graphs, it is particularly geared towards the state of the art in QA: problem graphs of a few to a few hundred variables, and hardware graphs of a few thousand qubits.

The primary function find_embedding() is a modernized implementation of the Cai, Macready and Roy [1] algorithm with several new features to give users finer control and address a wider class of problems.

Definitions

Let \(S\) and \(T\) be graphs, which we call source and target. If a set of target nodes is either size 1 or it’s a connected subgraph of \(T\), we call it a chain. A mapping \(f\) from source nodes to chains is an embedding of \(S\) into \(T\) when

• for every pair of nodes \(s_1 \neq s_2\) of \(S\), the chains \(f(s_1)\) and \(f(s_2)\) are disjoint, and
• for every source edge \((s_1, s_2)\), there is at least one target edge \((s_1, s_2)\) for which \(t_1 \in f(s_1)\) and \(t_2 \in f(s_2)\)

In the case that two chains are not disjoint, we say that they overlap. If a mapping has overlapping chains, and some of its source edges are represented by qubits shared by their associated chains but the others are all proper, then we call that mapping an overlapped embedding.

Higher-level Algorithm Description

This is a very rough description of the heuristic more properly described in [1], and most accurately described in the source.

Where it is difficult to find proper embeddings, it is much easier to find embeddings where the chains are allowed to overlap. The key operation is a placement heuristic. We initialize by setting \(f(s_0) = {t_0}\) for chosen source and target nodes, and then proceed placing nodes heedless of the overlaps that accumulate. We persist: tear out a chain, clean up its neighboring chains, and replace it. The placement heuristic attempts to avoid the qubits involved in overlaps, and once it finds an embedding, continues in the same fashion with the aim of minimizing the sizes of the chains.

Placement Heuristic

Let \(s\) be a source node with neighbors \(n_1, \cdots, n_d\). We first measure the distance from each neighbor’s chain, \(f(n_i)\) to all target nodes. Then, we select a target node \(t_0\) that minimizes the sum of distances to those chains. Then, we follow a minimum-length path from \(t_0\) to each neighbor’s chain, and the union of those paths is the new chain for \(s\). The distances are computed in \(T\) as a node-weighted graph, where the weight of a node is an exponential function of the number of chains which use it.

Hinting and Constraining

New features to this implementation are initial_chains, fixed_chains, and restrict_chains. Initial chains are used during the initialization procedure, and can be used to provide hints in the form of an overlapped, partial, or otherwise faulty embedding. Fixed chains are held constant during the execution of the algorithm. Finally, chains can be restricted to being contained within a user-defined subset of \(T\) – this constraint is somewhat soft, and the algorithm can be expected to violate it.

[1] https://arxiv.org/abs/1406.2741

Examples

This example minor embeds a triangular source K4 graph onto a square target graph.

from minorminer import find_embedding

# A triangle is a minor of a square.
triangle = [(0, 1), (1, 2), (2, 0)]
square = [(0, 1), (1, 2), (2, 3), (3, 0)]

# Find an assignment of sets of square variables to the triangle variables
embedding = find_embedding(triangle, square, random_seed=10)
print(len(embedding))  # 3, one set for each variable in the triangle
print(embedding)
# We don't know which variables will be assigned where, here are a
# couple possible outputs:
# [[0, 1], [2], [3]]
# [[3], [1, 0], [2]]

Embedding a \(K_3\) source graph into a square target graph by chaining two target nodes to represent one source node.

This minorminer execution of the example requires that source variable 0 always be assigned to target node 2.

embedding = find_embedding(triangle, square, fixed_chains={0: [2]})
print(embedding)
# [[2], [3, 0], [1]]
# [[2], [1], [0, 3]]
# And more, but all of them start with [2]

This minorminer execution of the example suggests that source variable 0 be assigned to target node 2 as a starting point for finding an embedding.

embedding = find_embedding(triangle, square, initial_chains={0: [2]})
print(embedding)
# [[2], [0, 3], [1]]
# [[0], [3], [1, 2]]
# Output where source variable 0 has switched to a different target node is possible.

This example minor embeds a fully connected K6 graph into a 30-node random regular graph of degree 3.

import networkx as nx

clique = nx.complete_graph(6).edges()
target_graph = nx.random_regular_graph(d=3, n=30).edges()

embedding = find_embedding(clique, target_graph)

print(embedding)
# There are many possible outputs, and sometimes it might fail
# and return an empty list
# One run returned the following embedding:
{0: [10, 9, 19, 8],
 1: [18, 7, 0, 12, 27],
 2: [1, 17, 22],
 3: [16, 28, 4, 21, 15, 23, 25],
 4: [11, 24, 13],
 5: [2, 14, 26, 5, 3]}

Embedding a \(K_6\) source graph (upper left) into a 30-node random target graph of degree 3 (upper right) by chaining several target nodes to represent one source node (bottom). The graphic of the embedding clusters chains representing nodes in the source graph: the cluster of red nodes is a chain of target nodes that represent source node 0, the orange nodes represent source node 1, and so on.