minorminer#

Reference documentation for minorminer:

About minorminer#

minorminer is a heuristic tool for minor embedding: given a minor and target graph, it tries to find a mapping that embeds the minor into the target.

The primary utility function, find_embedding(), is an implementation of the heuristic algorithm described in [1]. It accepts various optional parameters used to tune the algorithm’s execution or constrain the given problem.

This implementation performs on par with tuned, non-configurable implementations while providing users with hooks to easily use the code as a basic building block in research.

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

Another function, find_clique_embedding(), can be used to find clique embeddings for Chimera, Pegasus, and Zephyr graphs in polynomial time. It is an implementation of the algorithm described in [2]. There are additional utilities for finding biclique embeddings as well.

[2] https://arxiv.org/abs/1507.04774

Examples#

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]]

# We can insist that variable 0 of the triangle will always be assigned to [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]

# If we didn't want to force variable 0 to stay as [2], but we thought that
# was a good start we could provide it as an initialization hint instead.
embedding = find_embedding(triangle, square, initial_chains={0: [2]})
print(embedding)
# [[2], [0, 3], [1]]
# [[0], [3], [1, 2]]
# Output where variable 0 has switched to something else is possible again.

import networkx as nx

# An example on some less trivial graphs
# We will try to embed a fully connected graph with 6 nodes, into a
# random regular graph with degree 3.
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 for this, sometimes it might even fail
# and return an empty list

A more fleshed out example can be found under examples/fourcolor.py

cd examples
pip install -r requirements.txt
python fourcolor.py

Introduction#

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

minorminer has both a Python and C++ API, and includes implementations of multiple embedding algorithms to best fit different problems.

Minor-Embedding and QPU Topology#

For an introduction to minor-embedding, see the Minor Embedding section.

For an introduction to the topologies of D-Wave hardware graphs, see the Topologies section and the Exploring Pegasus Jupyter Notebook that explains the Advantage architecture in further detail.

Minor-embedding can be done manually, though typically for very small problems only. For a walkthrough of the manual minor-embedding process, see the SAT: Formulate, Embed, and Submit section.

Minor-Embedding in Ocean#

Minor-embedding can also be automated through Ocean. minorminer is used by several Ocean embedding composites for this purpose. For details on automated (and manual) minor-embedding through Ocean, see how the EmbeddingComposite and FixedEmbeddingComposite classes are used in this Boolean AND Gate example.

Once an embedding has been found, D-Wave’s Problem Inspector tool can be used to evaluate its quality. See the Using the Problem Inspector section for more information.

Usage Information#