minorminer documentation¶
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.