quip-topo-alloc

Warning

Work in progress -- APIs, heuristics, benchmark numbers, and docs may change.

A Python library for finding minor embeddings of graphs into D-Wave quantum annealer hardware topologies (Chimera, Pegasus, Zephyr).

A minor embedding maps each vertex of a source graph H to a connected chain of hardware qubits such that chains are disjoint and every edge of H is covered by a qubit-coupler edge between the corresponding chains.

What this project provides

• A pure Python implementation of a CMR-style minor embedding heuristic.
• Utilities to compare embedding quality against minorminer.
• A visualisation script to inspect produced embeddings.
• Unit tests and benchmark tests for correctness and performance tracking.

Algorithm

The implementation follows the heuristic by Cai, Macready, and Roy (2014), arXiv:1406.2741.

Each attempt starts from a random single-qubit initialisation and iteratively improves the embedding using a Gauss-Seidel pass: for every H node in random order, it finds the G anchor that minimises the total weighted path cost to all neighbouring chains, then rebuilds the chain from that anchor. Edge weights are :math:\beta^{\\text{overlap}} (where :math:\\beta = graph diameter), penalising qubits already used by other chains. Attempts restart from a fresh random initialisation when stuck.

See DESIGN.md for a detailed description of implementation decisions.

Installation

uv sync

Basic usage

import networkx as nx
import dwave_networkx as dnx
from topoalloc import embed

G = dnx.chimera_graph(3)      # hardware topology
H = nx.complete_graph(5)      # graph to embed

embedding = embed(H, G, tries=20, random_seed=42)
# embedding: {h_node: {g_node, ...}, ...}  or None if failed

Validate an embedding

import networkx as nx

def is_valid_minor_embedding(H: nx.Graph, G: nx.Graph, emb: dict) -> bool:
	# 1. Chains are non-empty, in G, connected, and pairwise disjoint.
	seen = set()
	for chain in emb.values():
		if not chain:
			return False
		if any(node not in G for node in chain):
			return False
		if not nx.is_connected(G.subgraph(chain)):
			return False
		if seen & chain:
			return False
		seen |= chain

	# 2. Every H-edge has at least one cross-chain edge in G.
	for u, v in H.edges():
		if not any(G.has_edge(x, y) for x in emb[u] for y in emb[v]):
			return False
	return True

Utility scripts

Compare chain quality against minorminer

Run preset known cases across all three topologies:

uv run bin/compare_embeddings --known

Run a specific topology and source graph:

uv run bin/compare_embeddings --topology chimera --size 3 --graph k5 --graph k6
uv run bin/compare_embeddings --topology pegasus --size 2 --graph k6 --runs 20

Test against random graphs -- Erdos-Renyi G(n, p) or Barabasi-Albert B(n, m):

uv run bin/compare_embeddings --topology chimera --size 3 --random-count 5 --random-nodes 8
uv run bin/compare_embeddings --random-topology pegasus --random-count 10 --random-edge-prob 0.5
uv run bin/compare_embeddings --topology chimera --size 3 --random-ba-count 5 --random-ba-m 2

Both --random-count and --random-ba-count can be combined in one run.

Verbosity levels control output detail:

• --verbosity 0 -- summary table only
• --verbosity 1 -- per-case chain statistics (default)
• --verbosity 2 -- per-attempt log with chain lists and pass/fail status

uv run bin/compare_embeddings --known --verbosity 2
uv run bin/compare_embeddings --known --verbosity 0 --histogram

Visualise an embedding

uv run bin/visualise_embedding --topology chimera --size 2 --graph k4
uv run bin/visualise_embedding --graph 3x3 --output grid.png

Running tests

uv sync --group test
uv run --group test python -m pytest tests/test_embed.py

Run all tests (unit + benchmarks enabled through pytest-benchmark):

uv run --group test python -m pytest

Running benchmarks

uv run --group test python -m pytest tests/bench_embed.py --benchmark-only

See BENCHMARKS.md for recorded results.

Benchmark findings and minor quality

Current benchmark summary (see BENCHMARKS.md for full tables):

• Mean chain-size ratio (topoalloc / minorminer) is 1.006 on recorded known cases.
• All reported known-case ratios are at most 1.052, below the stated 1.2x ceiling.
• On some zephyr cases, topoalloc slightly outperformed minorminer in mean chain size.
• Runtime is substantially slower than minorminer, which is expected because topoalloc is pure Python and performs full repeated attempts.

Interpretation for embedding quality:

• Minor validity is checked by tests for connectivity, disjointness, and edge coverage.
• Chain quality is competitive with minorminer on the recorded small/known cases.
• Performance remains the main trade-off vs minorminer's native implementation.

Contribution hints

• Keep changes small and focused -- one logical change per commit.
• Add or update tests in tests/ for every behavior change.
• Prefer measurable improvements: run quality comparison before and after heuristic changes.
• Use uv dependency groups (dev, test) as defined in pyproject.toml.
• Update DESIGN.md for algorithmic changes and BENCHMARKS.md when benchmark outcomes change.

License notice

This project is distributed under the terms in the LICENSE file in the repository root.