Pith. sign in

REVIEW 3 major objections 5 minor 15 references

Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph

T0 review · 3 major / 5 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper presents a universal minor-embedding framework that maps complete bipartite graphs onto Pegasus quantum annealers using periodic cell patterns, eliminating chains longer than six qubits and embedding a 120×120 graph in about…

desk verdict The paper's central empirical claim—zero chains longer than six for a 120x120 RBM on Pegasus—is impossible by a degree-bound argument; the deterministic construction is interesting but unvalidated, and the table is not credible. read the letter →

arxiv 2504.21112 v1 pith:XX5R2XQS submitted 2025-04-29 quant-ph

Salvatore Sinno , Thomas Gro{ss} , Nicholas Chancellor , Bhavika Bhalgamiya , Arati Sahoo This is my paper · ORCID
classification quant-ph
keywords minorembeddingcompletebipartitegraphPegasustopologyrestrictedBoltzmannmachinequantumannealingqubitchainstimeadiabaticcomputing
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper tries to establish that complete bipartite graphs such as Restricted Boltzmann Machines can be embedded onto Pegasus quantum annealers by hand-built periodic cell patterns rather than by heuristic search. It claims the construction needs no qubit chain longer than six physical qubits and produces embeddings in about 0.01 seconds, while the standard heuristic takes minutes and leaves some chains above the breakage threshold. If true, the result removes a practical bottleneck for quantum generative models and optimization: large RBM instances become embeddable quickly, deterministically, and with fewer chain-break errors.

What carries the argument

The machinery is a periodic coordinate system for Pegasus in which each qubit is indexed by orientation $u$, perpendicular tile offset $w$, qubit offset $k$, and parallel tile offset $z$, with the integer labelling $(u,w,k,z) \mapsto z + (M-1)(k + \alpha(w + Mu))$. The embedding tiles complete bipartite cells $K_{m,n}$ (using $m=4$, $n=8$ on Pegasus) across the grid, connecting each horizontal visible qubit to vertical hidden qubits in its cell and to the adjacent cell, and making chain couplings only between neighbouring qubit IDs. This converts minor embedding from a search problem into an arithmetic construction that scales with the number of cells.

What would settle it

Enumerate the Pegasus wiring list or query a real device's edge set, then check every visible-hidden pair appended to J connections by Algorithm 1 for a size such as 60×60; if any pair is missing, the construction is invalid as a minor embedding. Running the generated embedding through hardware-side embedding validation would give the same answer.

Watch

Extended reading notes

Core claim

The central claim is that the Pegasus hardware graph contains a repeating cell structure that can be tiled to realize any complete bipartite graph $K_{V,H}$ that fits, with visible units assigned to horizontal qubits and hidden units to vertical qubits by explicit arithmetic formulas. Algorithm 1 constructs the logical-physical mapping and the coupling matrix $J$ in closed form, and the paper reports that for 60×60 through 120×120 graphs the average embedding time is 0.012 to 0.014 seconds with zero chains longer than six, whereas the default heuristic takes 214 to 960 seconds and produces two to fifteen such chains. The theoretical maximum complete bipartite graph this construction embeds on Pegasus is $K_{172,120}$.

Load-bearing premise

The load-bearing premise is that every pair of qubits the labelling formula and Algorithm 1 connect is a physical connection that actually exists in Pegasus hardware; the paper never verifies this against the hardware's real wiring, so if even one pair is absent the mapping is not a valid minor embedding.

Editorial extensions

If this is right

  • RBM instances up to at least 120×120 can be embedded in milliseconds, making repeated embedding during training or sampling practical.
  • Because no chain exceeds six physical qubits, the embeddings avoid the chain-breakage regime the paper identifies as the main source of decoherence errors.
  • The embedding is deterministic and repeatable: the same coupling matrix and logical-physical map are generated every time, which heuristic search does not guarantee.
  • The maximum complete bipartite graph this construction can embed on Pegasus is $K_{172,120}$, so instances up to that size are covered before the hardware topology must change.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the periodic label formula is verified against the full Pegasus wiring list, the same construction should extend almost unchanged to later annealer topologies that keep the cell-and-offset structure; this is my inference, not a claim in the paper.
  • Because the embedding is closed-form, it can be precomputed once and reused, so in a real workflow the wall-clock advantage could be larger than the reported single-embedding speedup.
  • An analytical proof of validity may be possible directly from the degree-15 connectivity rules, which would make the empirical timing results secondary evidence.
  • A direct check of every generated visible-hidden pair against the hardware wiring list would settle whether the construction is truly universal; the paper does not report such a check.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper proposes a deterministic, periodicity-based construction for minor-embedding complete bipartite graphs (RBMs) onto D-Wave Pegasus hardware. It introduces a qubit coordinate labelling (Eq. 3), a set of embedding rules (Section III-B), an algorithm (Algorithm 1), and benchmark results (Table I) claiming embedding times of about 0.012--0.014 s and zero chains longer than six for sizes up to 120x120, compared with Minorminer. The central claim is that the construction yields a universal, valid minor embedding with short qubit chains.

Significance. If the central claim were correct, the speed and short-chain behavior would be practically relevant for quantum restricted Boltzmann machines and other complete-bipartite problems on quantum annealers. The paper has strengths: the construction is deterministic, the pseudocode is explicit, and the comparison target (Minorminer) is standard. However, the headline quantitative claim is impossible under the paper's own degree-15 hardware assumption, and the paper never verifies that the generated coupler pairs exist in the actual Pegasus topology. Because the main load-bearing result fails, the significance of the contribution is not established.

major comments (3)
  1. [Section V, Table I; Section III-A] The reported "Avg. Chains > 6 = 0" for K_{120,120} is impossible in any hardware graph of maximum degree 15, which is the degree the paper itself states for Pegasus. For a connected chain S of s physical qubits representing one logical vertex, the s vertices have at most 15s incident edge slots. Since S is connected, at least s-1 internal edges consume 2(s-1) slots, leaving at most (15-2)s + 2 = 13s + 2 external slots. A valid minor embedding of K_{120,120} requires at least 120 distinct external couplers from each visible chain to the 120 disjoint hidden chains, so 13s + 2 >= 120, giving s >= 10. The same bound applies to hidden chains. Thus Table I's claim of zero chains longer than six is inconsistent with any valid minor embedding into a degree-15 graph, and the paper's central empirical result cannot be correct as stated.
  2. [Section III-B and Algorithm 1] The paper never verifies that every visible-hidden pair (n, p) appended to J connections in Algorithm 1 corresponds to an existing coupler in the Pegasus hardware graph. Section IV gives an example asserting, for instance, that visible node 0 connects to physical qubits 2970, 2985, 3000, 3015, 3030, 3045, 3060, and 3075, but no proof, no check against the actual Pegasus edge list, and no hardware or simulator validation is provided. If any of these pairs is not a hardware edge, the object generated is an abstract graph rather than a minor embedding, and the resulting J matrix cannot be programmed onto the QPU. This validation is load-bearing for every empirical claim in the paper.
  3. [Section III-B, Eqs. (5)--(6)] The construction is not reproducible as written because the input parameters periodicity_v, periodicity_h, and n_periodicity are never given numeric definitions for Pegasus. The text states only that m = 4 and n = 8 are selected and that alpha <= m + n + 1, but the values of periodicity_v and periodicity_h used to produce Table I are not reported. Without these values, no reader can reconstruct the embedding, verify the chain-length counts, or check whether the generated qubit IDs correspond to valid Pegasus qubits.
minor comments (5)
  1. [Section III-A, Eq. (2)] The symbol alpha is defined as the degree of a vertex, but the preceding text says Pegasus qubits have degree 15 and nominal length 12, and Section IV appears to use alpha as the nominal length. These uses conflict; as written, D = 12 M(M-1) gives 2880 qubits for M=16, which is not the standard Pegasus P16 qubit count, so the formula and parameter definitions should be reconciled.
  2. [Section V-A, Table I] The metric definition says "chains with length >= 6" while Table I labels the column "Avg. Chains > 6"; the threshold should be stated consistently so the reader knows whether length 6 is included.
  3. [Section V] All reported results are classical construction times and chain counts; no annealing experiment, hardware run, or simulation is presented, so the claims about decoherence, chain breakage, and anneaal quality are not directly supported by the data.
  4. [References] Reference [14] appears to duplicate reference [4] with inconsistent volume and page information, and the bibliography should be checked for similar errors before resubmission.
  5. [Figures 6--10] Several figures (notably Figs. 6--10) are described only qualitatively, and Figure 10 has no defined axes or legend; adding quantitative captions would help readers interpret the visual claims.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: deterministic construction benchmarked externally; 'optimal' label and hardware validation are evidentiary gaps, not circular reductions.

full rationale

No circularity was found. The embedding construction (Eqs. 2-7 and Algorithm 1) is deterministic and uses no parameters fitted to the benchmark data; the comparison against Minorminer is an external baseline. The 'theoretical maximum' in Eq. 1 is cited from Boothby et al. [15], an independent D-Wave source rather than the present authors, and it is not used to fit or define the algorithm's outputs. The empirical claims about embedding time and chain counts are reported outputs of the construction, not fitted inputs renamed as predictions. No self-citation chain is load-bearing: the reference list contains no works by the present authors. Two evidentiary gaps exist but are not circular: Section III-A asserts rather than derives that the optimal embedding 'consists of a parallel path of horizontal qubits and a parallel path of vertical qubits,' and the physical validity of the coupler identifiers against the real Pegasus edge list is not verified. These are correctness and rigor concerns, not reductions of a claimed prediction to the paper's own inputs.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The construction depends on several unstated or unchecked choices: the periodicity parameters in Algorithm 1 are never reported, the Pegasus degree or nominal length is used inconsistently (12 versus 15), the mapping to hardware couplers is asserted rather than verified, the theoretical maximum is imported from Boothby et al., and the chain-stability threshold is assumed without evidence. No new physical entities are introduced.

free parameters (3)
  • periodicity_v, periodicity_h, n_periodicity = not reported
    Algorithm 1 takes these three parameters as input; the experimental section never states their values, so the reported embeddings and timings cannot be reproduced.
  • unit cell dimensions m and n for Pegasus = m=4, n=8
    Section IV selects these values without derivation; they determine the building block K_{m,n} used by the algorithm.
  • alpha (degree or nominal length) = ambiguous: 12 or 15
    The paper says Pegasus qubits have degree 15 and nominal length 12, then uses l=12 and requires alpha <= m+n+1. The value of alpha in the construction is inconsistent and unspecified.
assumptions (5)
  • domain assumption The Pegasus hardware graph is exactly described by the coordinate system of Eq. (3) and the connection rules in Section III-B.
    The algorithm's validity depends on this mapping; no verification against actual hardware coupler lists is provided.
  • ad hoc to paper Every visible-hidden qubit pair generated by Algorithm 1 corresponds to an existing coupler on the QPU.
    The construction asserts this without proof or empirical check; this is the load-bearing premise of the embedding.
  • domain assumption The maximum complete bipartite size given by Eq. (1), K_{12M-20,12M-20}, from Boothby et al. is correct and applicable to P16.
    The theoretical maximum is imported from reference [15] and used to claim 172x172, which then conflicts with the algorithm's stated maximum K172,120.
  • domain assumption Chains longer than six qubits are subject to breaking and give unreliable results.
    The threshold is stated in the introduction without citation and is used as the primary embedding quality metric.
  • ad hoc to paper The condition alpha <= m + n + 1 is sufficient for the proposed embedding construction to produce a valid minor embedding.
    The paper states this condition without proof, and it is tied to the unverified mapping between Eq. (3) and real Pegasus couplers.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph." pith.science (2026). https://pith.science/paper/XX5R2XQS

@misc{pith2026250421112,
  author       = {Pith},
  title        = {Pith review of: Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XX5R2XQS}},
  note         = {Machine review of arXiv:2504.21112}
}
read the original abstract

Minor embedding is essential for mapping largescale combinatorial problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently accommodates complete bipartite graphs onto the hardware topology of quantum annealers. By leveraging the inherent topographical periodicity of the physical quantum adiabatic annealer processor, our method systematically reduces qubit chain lengths, resulting in enhanced stability, computational efficiency, and scalability of quantum annealing. We benchmark our embedding framework against Minorminer, the default heuristic embedding algorithm, for the Pegasus topology, demonstrating that our approach significantly improves embedding quality. Our empirical results show a 99.98% reduction in embedding time for a 120 x 120 complete bipartite graphs. Additionally, our method eliminates long qubit chains, which primarily cause decoherence and computational errors in quantum annealing. These findings advance the scalability of quantum embeddings, particularly for quantum generative models, anomaly detection, and large-scale optimization tasks. Our results establish a foundation for integrating efficient quantum-classical hybrid solutions, paving the way for practical applications in quantum-enhanced machine learning and optimization.

Figures

Figures reproduced from arXiv: 2504.21112 by the authors.

Figure 1
Figure 1. Minor-embedding of G(left) in a square lattice U. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Connections Based on this, to embed a complete bipartite graph KV,H, equivalent to an RBM with V visible nodes and H hidden nodes, we start from a completed bipartite subgraph that can be embedded using some Km,n bipartite graph that can be com￾pleted embedded in G(M) using Ka,b. If V ≤ min(m, n)M, then the number of vertical Km,n cells we need is given by: Hv =  V min(m, n)  (4) In this case, each visible node k … view at source ↗
Figure 5
Figure 5. 8×12 RBM Embedded on Pegasus in embedding time and the elimination of long qubit chains. Moreover, by preserving the bipartite structure of RBMs and ensuring a systematic logical-to-physical mapping, our approach enhances the scalability of quantum machine learn￾ing models on quantum annealers. This advancement is par- [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figures from the paper (2 more)
Figure 9
Figure 9. Figure 9: Deail of Embedding 120×120 RBM on Pegasus [PITH_FULL_IMAGE:figures/full_fig_p006_9.png]
Figure 10
Figure 10. Figure 10: Comparison of Embedding rating hybrid optimization techniques to refine qubit alloca￾tion further, and integrating these embeddings into real-world quantum-enhanced machine learning workflows. Additionally, [PITH_FULL_IMAGE:figures/full_fig_p006_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages

  1. [1]

    Scalable architecture for adiabatic quantum computing of np-hard problems,

    W. M. Kaminsky and S. Lloyd, “Scalable architecture for adiabatic quantum computing of np-hard problems,” Quantum Computing and Quantum Bits in Mesoscopic Systems , pp. 229–236, 2004

    work page 2004

  2. [2]

    Quantum annealing with manufactured spins,

    M. W. Johnson, T. Lanting, S. Han, and M. H. S. Amin, “Quantum annealing with manufactured spins,” Nature, vol. 473, pp. 194–198, 2009

    work page 2009

  3. [3]

    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, https://arxiv.org/abs/0804.4884

    arXiv 2008

  4. [4]

    Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design

    ——, “Minor-embedding in adiabatic quantum computation: Ii. minor- universal graph design,” Quantum Information Processing , vol. 10, pp. 343–353, 2011, https://arxiv.org/abs/1001.3116

    work page Pith review arXiv 2011

  5. [5]

    Template- based minor embedding for adiabatic quantum optimization,

    T. Serra, T. Huang, A. Raghunathan, and D. Bergman, “Template- based minor embedding for adiabatic quantum optimization,” INFORMS Journal on Computing , vol. 33, no. 3, pp. 1048–1063, 2021, https: //pubsonline.informs.org/doi/10.1287/ijoc.2021.1065

    work page arXiv 2021

  6. [6]

    Efficiently embedding qubo problems on adiabatic quantum computers,

    P. Date, “Efficiently embedding qubo problems on adiabatic quantum computers,” D-Wave Systems Documentation , 2021, https://www.dwavesys.com/resources/application/ efficiently-embedding-qubo-problems-on-adiabatic-quantum-computers/

    work page 2021

  7. [7]

    Optimizing adiabatic quantum embedding for large-scale problems,

    C. P. Goodrich and B. D. Sullivan, “Optimizing adiabatic quantum embedding for large-scale problems,” Journal of Quantum Information Science, vol. 8, no. 1, pp. 24–34, 2018

    work page 2018

  8. [8]

    Embedding restricted boltzmann machines onto quantum annealers using pegasus topologies,

    S. Zbinden, S. Suresh, and S. Bernath, “Embedding restricted boltzmann machines onto quantum annealers using pegasus topologies,” Quantum Machine Intelligence, vol. 3, p. 12, 2021

    work page 2021

Show all 15 references
  1. [9]

    Anomaly detection speed-up by quantum restricted boltzmann ma- chine,

    M. Benedetti, J. Realpe-G ´omez, R. Biswas, and A. Perdomo-Ortiz, “Anomaly detection speed-up by quantum restricted boltzmann ma- chine,” Communications Physics , vol. 6, no. 1, pp. 1–9, 2023, https: //www.nature.com/articles/s42005-023-01390-y

    2023

  2. [10]

    Application of quantum annealing to training of deep neural networks,

    S. Adachi and M. P. Henderson, “Application of quantum annealing to training of deep neural networks,” arXiv preprint arXiv:1510.06356 , 2015

    2015 arXiv

  3. [11]

    Estimation of effective temperatures in quantum annealers for sampling applications: A case study with restricted boltzmann machines,

    M. Benedetti, J. Realpe-Gomez, R. Biswas, and A. Perdomo-Ortiz, “Estimation of effective temperatures in quantum annealers for sampling applications: A case study with restricted boltzmann machines,” Physical Review A, vol. 94, no. 2, p. 022308, 2016

    2016

  4. [12]

    Training restricted boltzmann machines with a d-wave quantum annealer,

    V . Dixit, P. Verma, K. C. Dixit, and S. Kais, “Training restricted boltzmann machines with a d-wave quantum annealer,” Frontiers in Physics, vol. 9, p. 589626, 2021, https://www.frontiersin.org/articles/10. 3389/fphy.2021.589626/full

    2021

  5. [13]

    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, pp. 709–729, 2014

    2014

  6. [14]

    Minor-embedding in adiabatic quantum computation: Ii. minor-universal graph design,

    V . Choi, “Minor-embedding in adiabatic quantum computation: Ii. minor-universal graph design,” Quantum Information Processing, vol. 7, no. 5, pp. 193–209, 2010

    2010

  7. [15]

    Next-generation topology of d-wave quantum processors,

    K. Boothby, P. Bunyk, J. Raymond, and A. Roy, “Next-generation topology of d-wave quantum processors,” 2020. [Online]. Available: https://arxiv.org/abs/2003.00133 APPENDIX A. Algorithms Algorithm 1 Embedding a Complete Bipartite Graph 1: Input: n visible, n hidden, periodicity...

    2020 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.