arxiv: 2604.25433 · v2 · submitted 2026-04-28 · 🪐 quant-ph

Recognition: unknown

Ember: An Extensible Benchmark Suite for Quantum Annealing Embedding Algorithms

Zachary Macaskill-Smith , Unmol Sharma , Melissa Warner , K\'alm\'an Varga , David A. B. Hyde

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:18 UTC · model grok-4.3

classification 🪐 quant-ph

keywords minor embeddingquantum annealingbenchmark suiteD-Wave hardwareChimera topologygraph embedding algorithmsreproducible evaluationsolution quality

0 comments

The pith

No single embedding algorithm for quantum annealing performs best across all graph families

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Prior work on minor embedding algorithms for quantum annealing has produced unreliable comparisons because studies used incompatible graph sets, metrics, and experimental conditions. Ember supplies a standardized open framework with reproducible execution, a library of 24,016 graphs spanning structured, random, and physics-motivated types, and analysis tools that cover multiple D-Wave hardware topologies. Evaluation of five algorithms on the Chimera topology shows that relative performance changes systematically with graph structure, so the best algorithm is family-dependent. This matters because embedding quality directly limits the solution quality and reliability obtained from the annealer. The suite also permits testing of error models and newer approaches such as reinforcement learning within the same controlled setting.

Core claim

The paper introduces Ember as an extensible benchmark suite for minor embedding algorithms and uses it to evaluate five algorithms over its full library on the Chimera topology. It establishes that no algorithm dominates universally: performance rankings vary systematically according to the structure of the embedded graph, and the optimal choice depends on the problem family.

What carries the argument

Ember's standardized algorithm interface together with its library of 24,016 diverse graphs and unified analysis pipeline that supports Chimera, Pegasus, and Zephyr topologies.

If this is right

Algorithm choice for embedding must be matched to the specific graph family rather than selected once for all problems.
Future comparisons of embedding methods require diverse graph libraries to avoid conclusions that hold only for narrow problem classes.
Hardware topology and qubit error rates must be included in benchmarks because they alter relative algorithm performance.
Reinforcement-learning embedding methods can be fairly compared against classical algorithms inside the same reproducible framework.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Users could build simple graph-feature detectors that route each new problem to the currently best-performing embedding algorithm for its family.
The systematic variation suggests that graph-theoretic invariants may predict which algorithm will succeed, opening a path to parameter-free selection rules.
The same benchmark structure could be reused for other sparse-hardware compilation tasks once analogous graph libraries are assembled.

Load-bearing premise

The 24,016 graphs and chosen metrics capture the embedding challenges and solution-quality factors that arise in practical quantum annealing applications.

What would settle it

Finding one algorithm that ranks first on every graph family in the library, or showing that a different but still practical set of metrics reverses the observed ranking pattern.

Figures

Figures reproduced from arXiv: 2604.25433 by David A. B. Hyde, K\'alm\'an Varga, Melissa Warner, Unmol Sharma, Zachary Macaskill-Smith.

**Figure 1.** Figure 1: Success rate vs. node count (20-node bins, all graph categories view at source ↗

**Figure 2.** Figure 2: Mean ACL vs. p |E| (quantile-binned, 20 bins of equal graph count). Shaded bands show pointwise 95% confidence intervals for the bin mean. All algorithms exhibit approximately linear growth; MINORMINER achieves the smallest slope. CLIQUE’s elevated ACL at low edge counts reflects its Kn assumption rather than edge structure. FAST produces no successful embeddings above n = 128, ATOM above n = 205, and PSSA… view at source ↗

**Figure 3.** Figure 3: Baseline-conditioned retention stratified by source edge count: fraction of embeddings successful at view at source ↗

read the original abstract

Minor embedding is a required compilation step for quantum annealing, mapping logical problem graphs onto sparse hardware topologies. Despite its central role in determining solution quality, no standardized benchmark exists for comparing embedding algorithms: prior studies use incompatible graph libraries, inconsistent metrics, and non-reproducible experimental setups, making cross-algorithm comparisons unreliable. We present Ember (Embedding Minor Benchmark for Evaluative Reproducibility), an open-source benchmarking framework addressing this gap. Ember provides a standardized algorithm interface with seeded, reproducible execution infrastructure; a diverse graph library of 24,016 instances spanning structured, random, and physics-motivated problem types not previously used in embedding benchmarks; and a unified analysis pipeline supporting all three current D-Wave hardware topologies (Chimera, Pegasus, Zephyr). We evaluate five algorithms across the full library on Chimera and find that no algorithm dominates universally: rankings vary systematically with graph structure, and the best algorithm depends on the family being embedded. We also examine the effects of hardware topology (including Pegasus and Zephyr), qubit error rates, and evaluate a reinforcement-learning approach (CHARME) within a narrower test set. Ember is available at https://github.com/zachmacsmith/ember and is installable via pip install ember-qc.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Ember supplies a standardized open benchmark for embedding algorithms with results showing performance rankings shift by graph family.

read the letter

The one thing to know is that this paper releases Ember, a standardized, open benchmark for quantum annealing embedding algorithms complete with a large graph library and initial comparison results. They address the problem of incompatible prior studies by providing a common interface, reproducible setup, and a library of over 24,000 graphs that includes types not used in earlier benchmarks. Their evaluation of five algorithms on the Chimera topology shows that rankings change with graph family, so no single method is best for everything. They extend this to other topologies, error rates, and even test a reinforcement learning approach in a smaller set. Making it pip-installable and hosting on GitHub is a plus for usability. The potential weak point is whether the graph library captures the embedding difficulties from real-world problems. The instances are described as spanning structured, random, and physics-motivated categories, but the paper does not appear to validate them against QUBO graphs derived from published applications such as TSP or ML tasks. If the synthetic distributions differ, the non-universality finding could be less general than it seems. This work is for anyone developing or selecting embedding algorithms for D-Wave hardware. It is worth sending to peer review because it supplies new infrastructure and data that others can build on, even if some aspects of the evaluation need tightening.

Referee Report

1 major / 1 minor

Summary. The manuscript introduces Ember, an open-source benchmark suite for minor embedding algorithms in quantum annealing. It supplies a standardized algorithm interface with seeded reproducibility, a library of 24,016 graph instances spanning structured, random, and physics-motivated types, and a unified analysis pipeline for D-Wave Chimera, Pegasus, and Zephyr topologies. Evaluation of five algorithms on Chimera shows no universal dominator, with rankings varying systematically by graph family. Additional results examine topology effects, qubit error rates, and a reinforcement-learning approach (CHARME) on a narrower subset.

Significance. If the central empirical result holds, the work supplies valuable infrastructure for reproducible comparisons of embedding algorithms, a longstanding gap in quantum annealing research. The open-source code, pip-installable package, and emphasis on seeded execution are concrete strengths that enable community use. The finding that algorithm performance depends on graph family has direct implications for practitioners selecting embeddings for structured versus random problems. Significance is tempered by the need to confirm the library captures practical embedding difficulties.

major comments (1)

The claim that no embedding algorithm dominates universally (abstract) rests on the 24,016-instance library capturing the distribution of minor-embedding difficulties encountered in practice. The library is described as spanning structured, random, and physics-motivated types not previously benchmarked, yet no external validation or comparison is provided against QUBO graphs derived from published application instances (e.g., TSP, scheduling, or ML models). If the synthetic generators produce systematically different chain-length or success-rate statistics than real applications, the observed family-dependent rankings could be an artifact of benchmark construction rather than a robust property of the algorithms.

minor comments (1)

Abstract: the statement that Ember supports all three D-Wave topologies is clear, but only Chimera results are detailed; a concise summary table or key quantitative differences for Pegasus and Zephyr would aid readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the constructive review and the recommendation for major revision. The primary concern regarding external validation of the benchmark library against real application-derived QUBOs is addressed point-by-point below. We have made targeted revisions to strengthen the discussion of the library's representativeness while preserving the core contribution of a standardized, reproducible framework.

read point-by-point responses

Referee: The claim that no embedding algorithm dominates universally (abstract) rests on the 24,016-instance library capturing the distribution of minor-embedding difficulties encountered in practice. The library is described as spanning structured, random, and physics-motivated types not previously benchmarked, yet no external validation or comparison is provided against QUBO graphs derived from published application instances (e.g., TSP, scheduling, or ML models). If the synthetic generators produce systematically different chain-length or success-rate statistics than real applications, the observed family-dependent rankings could be an artifact of benchmark construction rather than a robust property of the algorithms.

Authors: We acknowledge the value of direct validation against QUBO instances extracted from published applications such as TSP, scheduling, or machine-learning models. Our library was constructed to span graph families that correspond to the structural characteristics of such problems (e.g., grid-like and lattice graphs for many combinatorial optimization tasks, and physics-motivated graphs drawn from Ising models). The central empirical result—that algorithm rankings vary systematically by family—remains robust within this controlled, reproducible setting and provides practitioners with guidance on selecting embeddings according to problem structure. To address the referee's concern, we have added a new paragraph in the revised Discussion section that explicitly maps common application QUBOs onto the families in Ember, citing representative literature, and notes the benchmark's extensibility for users to incorporate their own application-derived instances. This revision clarifies the scope without overstating generalizability. revision: partial

Circularity Check

0 steps flagged

No significant circularity in Ember benchmark evaluation

full rationale

The paper introduces new infrastructure (Ember framework, standardized interface, 24,016-instance graph library spanning structured/random/physics-motivated types, unified analysis pipeline) and reports direct empirical results from running five embedding algorithms on Chimera (plus narrower tests on Pegasus/Zephyr and CHARME). The central claim—no algorithm dominates universally, with rankings varying by graph family—is an observation from these runs rather than a derivation, fitted parameter, or self-referential definition. No equations reduce outputs to inputs by construction, no load-bearing self-citations justify uniqueness theorems, and the work is self-contained against external benchmarks (the tested algorithms). This matches the expected honest non-finding for a benchmark suite paper.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The central contribution is an empirical benchmarking framework and new graph library rather than a mathematical derivation. No free parameters, axioms, or invented entities are required for the core claims, which rest on running existing algorithms on the provided test instances.

pith-pipeline@v0.9.0 · 5536 in / 1158 out tokens · 94444 ms · 2026-05-08T03:18:12.220437+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Reference graph

Works this paper leans on

41 extracted references · 9 canonical work pages · 1 internal anchor

[1]

Embedding of complete graphs in broken Chimera graphs,

E. Lobe and A. Lutz, “Embedding of complete graphs in broken Chimera graphs,”Quantum Information Processing, vol. 20, no. 8, p. 291, 2021

2021
[2]

What is the computational value of finite-range tunneling?

V . S. Denchev et al., “What is the computational value of finite-range tunneling?”Physical Review X, vol. 6, no. 3, p. 031015, 2016

2016
[3]

Stochastic blockmodels: First steps,

P. W. Holland, K. B. Laskey, and S. Leinhardt, “Stochastic blockmodels: First steps,”Social Networks, vol. 5, no. 2, pp. 109–137, 1983

1983
[4]

The D-Wave Advantage system: An overview,

D-Wave Systems Inc., “The D-Wave Advantage system: An overview,” Technical Report 14-1049A-A, 2020. [Online]. Avail- able: https://www.dwavequantum.com/media/s3qbjp3s/14-1049a-a the d-wave advantage system an overview.pdf

2020
[5]

Quantum annealing in the transverse Ising model,

T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,”Physical Review E, vol. 58, no. 5, pp. 5355–5363, 1998

1998
[6]

Minor-embedding in adiabatic quantum computation: I. The parameter setting problem,

V . Choi, “Minor-embedding in adiabatic quantum computation: I. The parameter setting problem,”Quantum Information Processing, vol. 7, pp. 193–209, 2008

2008
[7]

Gomez-Tejedor, E

A. G ´omez-Tejedor and E. Osaba, “Addressing the minor-embedding problem in quantum annealing and evaluating state-of-the-art algorithm performance,” arXiv:2504.13376, 2025

work page arXiv 2025
[8]

G., and Roy, A

J. Cai, W. Macready, and A. Roy, “A practical heuristic for finding graph minors,” arXiv:1406.2741, 2014

work page arXiv 2014
[9]

Efficiently embedding QUBO problems on adiabatic quantum computers,

P. Date, D. Arthur, and L. Pusey-Nazzaro, “Efficiently embedding QUBO problems on adiabatic quantum computers,”Quantum Informa- tion Processing, vol. 18, no. 4, p. 117, 2019

2019
[10]

ATOM: An efficient topology adaptive algorithm for minor embedding in quantum computing,

H. Ngo et al., “ATOM: An efficient topology adaptive algorithm for minor embedding in quantum computing,” arXiv:2307.01843, 2023

work page arXiv 2023
[11]

CHARME: A chain-based reinforcement learning ap- proach for the minor embedding problem,

H. Ngo et al., “CHARME: A chain-based reinforcement learning ap- proach for the minor embedding problem,” arXiv:2406.07124, 2024

work page arXiv 2024
[12]

Embedding algorithms for quantum annealers with Chimera and Pegasus connection topologies,

S. Zbinden, A. B ¨artschi, H. Djidjev, and S. Eidenbenz, “Embedding algorithms for quantum annealers with Chimera and Pegasus connection topologies,” inProc. ISC High Performance, pp. 187–206, 2020

2020
[13]

Boothby, P

T. Boothby, P. Bunyk, J. Raymond, and A. Roy, “Next-generation topology of D-Wave quantum processors,” arXiv:2003.00133, 2020

work page arXiv 2003
[14]

Pegasus graph (Ocean documentation),

D-Wave Systems Inc., “Pegasus graph (Ocean documentation),” https: //docs.ocean.dwavesys.com/
[15]

Zephyr graph (Ocean documentation),

D-Wave Systems Inc., “Zephyr graph (Ocean documentation),” https: //docs.ocean.dwavesys.com/
[16]

minorminer: A tool for finding graph minors,

D-Wave Systems Inc., “minorminer: A tool for finding graph minors,” https://github.com/dwavesystems/minorminer
[17]

Fast clique minor generation in Chimera qubit connectivity graphs,

T. Boothby, A. D. King, and A. Roy, “Fast clique minor generation in Chimera qubit connectivity graphs,”Quantum Information Processing, vol. 15, no. 1, pp. 495–508, 2016

2016
[18]

Minor embedding for quantum annealing with reinforcement learning,

R. Nembrini et al., “Minor embedding for quantum annealing with reinforcement learning,”Quantum Machine Intelligence, 2025. doi:10.1007/s42484-026-00341-4

work page doi:10.1007/s42484-026-00341-4 2025
[19]

Computational supremacy in quantum simulation,

A. D. King et al., “Computational supremacy in quantum simulation,” arXiv:2403.00910, 2024

work page arXiv 2024
[20]

Comparing three generations of D-Wave quantum anneal- ers for minor embedded combinatorial optimization problems,

E. Pelofske, “Comparing three generations of D-Wave quantum anneal- ers for minor embedded combinatorial optimization problems,”Quantum Science and Technology, vol. 10, no. 2, p. 025025, 2025

2025
[21]

Benchmarking quantum annealing with maximum cardinality matching problems,

D. Vert et al., “Benchmarking quantum annealing with maximum cardinality matching problems,”Frontiers in Computer Science, vol. 6, 2024

2024
[22]

Proximal Policy Optimization Algorithms

J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” arXiv:1707.06347, 2017

work page internal anchor Pith review arXiv 2017
[23]

The Aligned Rank Transform for nonparametric factorial analyses using only ANOV A procedures,

J. O. Wobbrock, L. Findlater, D. Gergle, and J. J. Higgins, “The Aligned Rank Transform for nonparametric factorial analyses using only ANOV A procedures,” inProc. ACM SIGCHI Conf. Human Factors in Computing Systems, pp. 143–146, 2011

2011
[24]

Quantum optimization of fully connected spin glasses,

D. Venturelli, S. Mandr `a, S. Knysh, B. O’Gorman, R. Biswas, and V . Smelyanskiy, “Quantum optimization of fully connected spin glasses,” Physical Review X, vol. 5, no. 3, p. 031040, 2015

2015
[25]

Collective dynamics of ‘small-world’ networks,

D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’ networks,”Nature, vol. 393, no. 6684, pp. 440–442, 1998

1998
[26]

On random graphs I,

P. Erd ˝os and A. R ´enyi, “On random graphs I,”Publicationes Mathemat- icae Debrecen, vol. 6, pp. 290–297, 1959

1959
[27]

Emergence of scaling in random net- works,

A.-L. Barab ´asi and R. Albert, “Emergence of scaling in random net- works,”Science, vol. 286, no. 5439, pp. 509–512, 1999

1999
[28]

Benchmark graphs for testing community detection algorithms,

A. Lancichinetti, S. Fortunato, and F. Radicchi, “Benchmark graphs for testing community detection algorithms,”Physical Review E, vol. 78, no. 4, p. 046110, 2008

2008
[29]

Layout-aware embedding for quantum annealing processors,

J. P. Pinilla and S. J. E. Wilton, “Layout-aware embedding for quantum annealing processors,” inProc. ISC High Performance, pp. 121–139, 2019

2019
[30]

D-Wave Ocean software (Ocean SDK),

D-Wave Systems Inc., “D-Wave Ocean software (Ocean SDK),” https: //github.com/dwavesystems/dwave-ocean-sdk
[31]

Deep learning-enabled method for accelerated graph embedding,

D. A. B. Hyde, “Deep learning-enabled method for accelerated graph embedding,” U.S. Patent Application No. 19/354,319, Oct. 9, 2025

2025
[32]

Using caching techniques to improve graph embedding performance,

J. W. Brahm, D. A. B. Hyde, and P. McMahon, “Using caching techniques to improve graph embedding performance,” U.S. Patent 10,929,294, Feb. 23, 2021

2021
[33]

Adiabatic quantum programming: minor embedding with hard faults,

C. Klymko, B. D. Sullivan, and T. S. Humble, “Adiabatic quantum programming: minor embedding with hard faults,”Quantum Information Processing, vol. 13, no. 3, pp. 709–729, 2014

2014
[34]

Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes,

Y . Sugie et al., “Minor-embedding heuristics for large-scale annealing processors with sparse hardware graphs of up to 102,400 nodes,”Soft Computing, vol. 25, pp. 1731–1749, 2021

2021
[35]

Graph minors from simulated annealing for annealing machines with sparse connectivity,

Y . Sugie et al., “Graph minors from simulated annealing for annealing machines with sparse connectivity,” inProc. Theory and Practice of Natural Computing (TPNC), pp. 111–123, 2018

2018
[36]

Integer programming techniques for minor-embedding in quantum annealers,

D. E. Bernal, K. E. C. Booth, R. Dridi, H. Alghassi, S. Tayur, and D. Venturelli, “Integer programming techniques for minor-embedding in quantum annealers,” inProc. CPAIOR, pp. 112–129, 2020

2020
[37]

Scaling of graph embedding for quantum annealers,

E. Pelofske, A. B ¨artschi, G. Hahn, H. N. Djidjev, and S. Eidenbenz, “Scaling of graph embedding for quantum annealers,” inProc. IEEE Int. Conf. Quantum Computing and Engineering (QCE), Montreal, QC, Canada, 2024

2024
[38]

Graph minor embeddings for D-Wave computer architecture,

Z. Yang and M. J. Dinneen, “Graph minor embeddings for D-Wave computer architecture,” Technical Report, University of Auckland, 2019

2019
[39]

Op- timised quantum embedding: a universal minor-embedding framework for large complete bipartite graphs,

S. Sinno, T. Groß, N. Chancellor, B. Bhalgamiya, and A. Sahoo, “Op- timised quantum embedding: a universal minor-embedding framework for large complete bipartite graphs,” inProc. IEEE Quantum Artificial Intelligence (QAI), 2025

2025
[40]

Decomposition algorithms for solving NP-hard problems on a quantum annealer,

E. Pelofske, G. Hahn, and H. Djidjev, “Decomposition algorithms for solving NP-hard problems on a quantum annealer,” Los Alamos National Laboratory, Los Alamos, NM, Tech. Rep. LA-UR-19-30809, 2021

2021
[41]

Quantum computing and the stable set problem,

A. Krpan, J. Povh, and D. Pucher, “Quantum computing and the stable set problem,”Optimization Methods and Software, vol. 40, no. 4, pp. 837–870, 2025, doi: 10.1080/10556788.2025.2490639

work page doi:10.1080/10556788.2025.2490639 2025