Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms

The paper introduces Ember, an open-source, reproducible benchmark suite that standardizes the evaluation of quantum annealing embedding algorithms across diverse graph instances and hardware topologies, revealing that no single algorithm universally dominates and that performance is highly dependent on specific graph structures.

The Gist

Imagine you have a complex puzzle you want to solve using a special, high-tech machine called a Quantum Annealer (specifically, one made by D-Wave). This machine is like a giant, intricate city of roads (qubits) where information travels. However, the city has a problem: the roads don't connect everywhere. Some neighborhoods are isolated, and you can't drive directly from point A to point B if there's no road.

Your puzzle, however, assumes you can go anywhere. To make your puzzle work on this machine, you have to perform a translation step called "Minor Embedding." This is like taking your puzzle pieces and stretching them out into long chains of connected cars to bridge the gaps in the city's road network.

The Problem:
For years, scientists have been inventing different "translation strategies" (algorithms) to figure out how to stretch these puzzle pieces most efficiently. But there was a major issue: everyone was testing their strategies on different puzzles, using different rules, and measuring success in different ways. It was like comparing a chef's soup recipe to a baker's cake recipe using different ovens and different taste testers. You couldn't tell who was actually the best cook.

The Solution: "Ember"
The authors of this paper built Ember (Embedding Minor Benchmark for Evaluative Reproducibility). Think of Ember as a universal, standardized cooking competition.

• The Kitchen: It provides a single, fair kitchen (software framework) where every strategy must cook under the exact same conditions.
• The Ingredients: Instead of just using random ingredients, they created a massive pantry with 24,016 different types of puzzles. These include standard random puzzles, but also special ones inspired by physics (like crystals and magnets) and structured patterns that real-world problems actually look like.
• The Judges: They tested five different "chefs" (algorithms) to see who could solve these puzzles best.

What They Found:
When they ran the competition, they discovered that there is no single "best" chef. The winner depends entirely on what kind of puzzle you give them:

• MinorMiner: This is the "reliable veteran." It works well on almost everything, especially the physics-inspired puzzles and simple shapes. It's the safest bet if you don't know what kind of puzzle you have.
• OCT-fast: This is the "speed specialist." When it works, it's incredibly fast and produces very short chains (efficient solutions), but it only works well on specific, highly structured puzzles (like perfect grids or symmetric shapes).
• Clique: This is the "brute force" approach. It's the fastest to run, but it often creates very long, clumsy chains. It's only good if you have a puzzle that is a perfect, dense web (a complete graph).
• ATOM & PSSA: These had mixed results. ATOM was fast but often failed to find a solution or made messy chains. PSSA was good at solving "perfectly dense" puzzles but struggled with others.

The Hardware Matters More Than the Chef:
The paper also tested these strategies on three different generations of the D-Wave machine (Chimera, Pegasus, and Zephyr).

• The "City" Upgrade: They found that upgrading the machine's hardware (the road network) makes a bigger difference than changing the translation strategy. The newest machine (Zephyr) could solve 3 times more puzzles than the oldest one (Chimera) just because its roads were better connected.
• Broken Roads (Faults): Real machines have broken roads (faulty qubits). When they simulated broken roads, the "reliable veteran" (MinorMiner) kept working almost as well as before. However, the other strategies (like PSSA and Clique) crashed hard, losing their ability to solve puzzles almost immediately.

The Bottom Line:
The paper concludes that if you are trying to solve a problem on a quantum computer:

1. Don't just pick the fastest algorithm. The best one depends on the shape of your problem.
2. If you don't know your problem's shape, use MinorMiner. It's the most robust and works on the widest variety of puzzles.
3. Hardware upgrades are powerful. A better machine can solve problems that no algorithm on an older machine could ever touch.
4. Reliability is key. Some algorithms look good on paper but fail the moment the hardware has a few glitches.

Ember is now open for anyone to use, ensuring that future "chefs" can be tested fairly against this massive library of puzzles, so we can finally know who is truly the best at translating our problems for quantum machines.

Technical Summary

1. Problem Statement

Quantum annealing (QA) on D-Wave processors requires minor embedding, a compilation step that maps logical problem graphs onto sparse hardware topologies (Chimera, Pegasus, Zephyr). The quality of this embedding—specifically chain length and success rate—directly dictates annealing performance and solution fidelity.

Despite the critical nature of embedding, the field lacks a standardized benchmark. Existing comparisons suffer from:

• Incompatibility: Algorithms are tested on different graph libraries, hardware topologies, and experimental setups.
• Non-reproducibility: Many studies lack random seeds or detailed configuration logs.
• Limited Scope: Prior benchmarks rely heavily on random graph families (e.g., Erdős-Rényi, Barabási-Albert) and often ignore structured or physics-motivated graphs common in real-world applications.
• Missing Comparisons: Newer algorithms (e.g., ATOM, CHARME) have not been compared against established baselines (e.g., MinorMiner, OCT) under identical conditions.

2. Methodology: The Ember Framework

The authors introduce Ember (Embedding Minor Benchmark for Evaluative Reproducibility), an open-source, extensible benchmarking framework designed to address these gaps.

A. Architecture & Infrastructure

• Standardized Interface: Defines a strict Python contract for embedding algorithms (input/output formats, timeout handling, versioning) to ensure fair comparison.
• Reproducibility: Every run is seeded, with resolved configurations saved as YAML files. It supports checkpointing and resuming interrupted runs.
• Fault Simulation: Allows for the simulation of qubit faults by randomly removing nodes/edges from the target hardware graph to test robustness.
• Two-Part Design: ember-qc (runner) and ember-qc-analysis (standalone analysis), allowing analysis on machines without D-Wave software stacks.

B. The Graph Library

Ember introduces a diverse library of 24,016 distinct problem graphs across 35 categories and 5 structural families, significantly expanding beyond prior work:

1. Random: Includes Watts–Strogatz, Erdős–Rényi, Barabási–Albert, and stochastic block models.
2. Structured: Algebraic graphs (Petersen, circulant, Turán, complete bipartite, hypercubes).
3. Physics/Lattice: 2D and 3D lattices (triangular, honeycomb, kagome, frustrated square, Shastry–Sutherland) relevant to quantum simulation.
4. Topological: Extremal graphs (paths, cycles, stars, trees) testing treewidth and diameter limits.
5. Benchmarking/Application: Planted-solution graphs, weak-strong clusters, spin-glass instances, and hardware-native subgraphs.

C. Algorithms Evaluated

The study evaluates five primary algorithms (and variants) implemented via the Ember contract:

1. MinorMiner: The standard D-Wave heuristic (greedy search).
2. Clique Embedding: Exact polynomial-time embedding for complete graphs.
3. OCT-based (fast-OCT): Uses Odd-Cycle Transversal decompositions.
4. ATOM: Adaptive topology approach.
5. PSSA: Probabilistic Swap-Shift Annealing (reimplemented for D-Wave topologies).
6. CHARME: A Reinforcement Learning (RL) approach (evaluated on a specific subset).

3. Key Contributions

1. Reproducible Infrastructure: A unified, open-source platform enabling direct, fair comparison of embedding algorithms with full traceability.
2. Diverse Graph Library: The first benchmark to systematically include physics-motivated lattices and structured graphs, revealing that algorithm performance is highly dependent on graph topology.
3. Cross-Topology Analysis: Evaluations across all three D-Wave generations (Chimera, Pegasus, Zephyr), quantifying hardware capacity gains.
4. Fault Tolerance Characterization: Systematic testing of algorithm robustness against simulated qubit faults.

4. Key Results

A. No Universal Dominator (Rank Reversals)

• Aggregate vs. Specific: While MinorMiner ranks first overall (Success Rate: 61.3%, Mean Chain Length: 4.23), no single algorithm dominates across all graph types.
• Structural Dependence: Rankings reverse systematically based on graph structure:
  • MinorMiner dominates on Physics/Lattice and Topological graphs.
  • OCT-fast outperforms MinorMiner on algebraically regular graphs (Bipartite, Turán, Hypercube) and Spin-Glass instances, producing chains 7–15% shorter with ~1/8th the runtime.
  • PSSA leads on Complete Graphs.
  • Clique is optimal only for dense complete graphs within hardware limits but fails rapidly on other structures.
• Conclusion: Aggregate rankings mask critical performance variations; algorithm selection must be matched to the specific problem structure.

B. Hardware Topology Effects

• Capacity Gains: Zephyr extends Pegasus's edge capacity by 12% and offers ~3.4× more capacity than Chimera.
• Chain Length: Zephyr produces chains 2.7–3.0× shorter than Chimera on large graphs due to higher connectivity (degree-15 vs. degree-6).
• Scalability: MinorMiner maintains meaningful success rates (>40%) on Zephyr for graphs up to 200+ nodes, whereas Chimera success rates drop to <12% for the same size.

C. Fault Tolerance

• Graceful Degradation: MinorMiner degrades gracefully under qubit faults (losing ~28% success rate at 25% fault rate).
• Sharp Cliffs: PSSA and Clique exhibit catastrophic failure ("cliffs") between 1% and 5% fault rates, losing roughly twice the success rate of MinorMiner.
• Mechanism: MinorMiner's incremental path-finding routes around isolated faults, whereas Clique's fixed templates and PSSA's global properties fail discontinuously when connectivity is broken.

D. Reinforcement Learning (CHARME)

• Evaluated on graphs matching its training distribution ($N=120$).
• Performance: At $N=120$, CHARME outperforms ATOM significantly (51% vs. 29% success rate) but remains inferior to MinorMiner (75–100%).
• Trade-off: CHARME achieves feasibility gains by accepting significantly longer chains (+34% mean chain length) and higher runtime (~20× ATOM, ~5× MinorMiner).

5. Significance and Practical Implications

• Algorithm Selection: The paper provides concrete guidance: use OCT-fast for runtime-sensitive workloads on structured graphs, MinorMiner as the robust default for general/physics problems, and PSSA/Clique only for specific dense graph classes.
• Hardware Leverage: For large problems, upgrading hardware (e.g., from Chimera to Zephyr) yields greater performance gains (3.8× success rate improvement) than algorithmic tuning.
• Robustness: MinorMiner is the most robust choice for real-world deployment where qubit faults are inevitable.
• Future Research: Ember establishes a foundation for future work, including generalizing OCT/ATOM/CHARME to Pegasus/Zephyr, integrating graph structural metadata for dynamic algorithm selection, and performing end-to-end evaluations on actual QPUs.

Availability: The framework is open-source and installable via pip install ember-qc.