{"id":"5c6d02ef-d011-432a-beaa-96dba2fa2162","arxiv_id":"2504.21112","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"high","formal_verification":"none","parameter_count":3,"one_line_summary":"A coordinate-based minor-embedding method for complete bipartite graphs on Pegasus is claimed to be far faster than Minorminer and to avoid long chains, but the zero-long-chain claim is incompatible with the 15-coupler degree limit for 120x120 graphs.","lead":"This paper proposes a deterministic template algorithm for mapping complete bipartite graphs, the structure of restricted Boltzmann machines, onto D-Wave Pegasus quantum annealers. The authors claim millisecond embedding times and zero long qubit chains, but the central result conflicts with the hardware degree limit.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"K_{120,120} cannot be embedded in a degree-15 Pegasus graph with all chains at most 6: every chain needs at least 10 physical qubits, so Table I's zero chains longer than 6 is mathematically impossible.","rationale":"The single most load-bearing concern is not that coupler validity is unverified, although that is also a real weakness; it is that the reported zero long chains is impossible by a pure degree-count argument. Since the paper's own Pegasus degree is 15, a K_{120,120} minor embedding forces every chain to contain at least 10 physical qubits. This directly invalidates the abstract's claim that the method eliminates long qubit chains and Table I's Avg. Chains > 6 = 0. I therefore agree with the reader's REJECT verdict, but I would ground it in the degree-bound refutation rather than in the coupler-existence assumption, so agreement with the reader's stated weakest_assumption is only partial. Additional issues, including the K172,172 versus K172,120 maximum-size inconsistency, the omitted periodicity parameters needed to reproduce Algorithm 1, and the lack of comparison with Zbinden et al.'s deterministic RBM embedding, reinforce rejection but are secondary. The conclusion is robust: the central empirical claim cannot hold for any valid minor embedding into Pegasus hardware.","tokens_in":7908,"tokens_out":11009,"duration_ms":118276,"concrete_test":"Implement Algorithm 1 for n=120 with the periodicity parameters v and h needed to reproduce the paper's layout, enumerate the connected component assigned to each logical visible and hidden node, and count chain lengths; also verify every generated coupler appears in the published Pegasus P16 edge list. The degree-capacity count predicts all 240 chains have length at least 10, so obtaining a valid embedding with any chain of length at most 6 would require a non-Pegasus coupler or a vertex degree above 15, either of which disproves Table I.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline empirical result is Table I (Section V): for 120x120 complete bipartite graphs, the proposed embedding has Avg. Chains > 6 = 0 on Pegasus. This is impossible given the degree bound the paper itself states in Section III-A (degree 15 per qubit). In any minor embedding of K_{120,120} into a graph of maximum degree Delta=15, fix a chain C of s physical qubits representing one visible node. The 120 logical edges incident to that visible node require at least 120 distinct incident hardware edges from C, one to each of the 120 disjoint hidden chains. Because C is connected, it has at least s-1 internal edges, consuming 2(s-1) of the total Delta*s incident edge slots. The number of external incident edges is therefore at most Delta*s - 2(s-1) = (Delta-2)s + 2 = 13s + 2. Requiring 13s + 2 >= 120 gives s >= 10. By symmetry every hidden chain also has length at least 10. Thus a valid embedding of K_{120,120} cannot have zero chains longer than six; either the table is wrong or the coupler graph is not Pegasus. This refutes the paper's central claim without relying on coupler-list validation or omitted periodicity parameters.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8197,"tokens_out":6523,"duration_ms":73696,"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":[{"comment":"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.","section":"Section V, Table I; Section III-A"},{"comment":"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.","section":"Section III-B and Algorithm 1"},{"comment":"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.","section":"Section III-B, Eqs. (5)--(6)"}],"minor_comments":[{"comment":"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.","section":"Section III-A, Eq. (2)"},{"comment":"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.","section":"Section V-A, Table I"},{"comment":"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.","section":"Section V"},{"comment":"Reference [14] appears to duplicate reference [4] with inconsistent volume and page information, and the bibliography should be checked for similar errors before resubmission.","section":"References"},{"comment":"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.","section":"Figures 6--10"}],"recommendation":"reject","confidential_remarks":"The degree-counting argument against Table I is decisive and does not depend on the hardware edge-list question. The paper as submitted cannot support its central empirical claim, and I do not see a minor revision that would fix the issue within the current scope. If the authors resubmit, they should validate the generated coupler pairs against the actual Pegasus edge list and report chain lengths that satisfy the necessary counting bound."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Plainly: the headline result cannot be right. Any minor embedding of K_{120,120} into a degree-15 graph requires chains of length at least 10. Fix one visible chain C of s qubits; it needs 120 distinct incident edges to the 120 hidden chains. Internal edges inside C consume 2(s−1) of the total 15s edge slots, leaving at most 13s+2 external slots. Requiring 13s+2 ≥ 120 forces s ≥ 10. So no valid embedding can have zero chains longer than six, and Table I's 0 for 120x120 is impossible. Either the measurement is wrong or the 'embedding' is not actually a minor embedding of the complete bipartite graph.\n\nWhat is genuinely new here: the coordinate-based formulas (Eqs. 3–6) and a deterministic O(mn/d) construction for complete bipartite graphs on a Pegasus-like grid. For smaller sizes, like 60x60, chains of length ≤6 are not ruled out by the degree bound, so the approach may be workable in that regime. The timing contrast—milliseconds versus hundreds of seconds—is striking and in principle reproducible. The authors also cite the relevant prior work, including Zbinden et al., even though they never actually compare against that deterministic RBM embedding.\n\nThe soft spots are not minor. First, the paper never verifies that the coupler pairs produced by Eq. 3 and Algorithm 1 correspond to real Pegasus couplers. If even one pair is absent, the mapping is invalid. Second, Algorithm 1's key parameters—periodicity_v, periodicity_h, n_periodicity—are never specified, so the experiments cannot be reproduced. Third, the theoretical maximum is K172,172 in Section III-A but K172,120 in Section III-B, an unexplained internal contradiction. Finally, the title says 'universal' but the method is specific to complete bipartite graphs; that is fine if stated, but the framing oversells.\n\nWho is this for? Practitioners who want deterministic embeddings of RBMs on D-Wave hardware. But as it stands, the unsupported central claim and missing validation make it unusable as a reference. I would not send this to peer review; a referee would immediately hit the degree bound and the missing periodicity values. The paper needs a major rewrite with hardware verification, corrected claims, and a real comparison to prior deterministic methods. Until then, it is not a credible contribution.","headline":"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.","tokens_in":8721,"tokens_out":3598,"would_cite":false,"duration_ms":38477,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["minor embedding","complete bipartite graph","Pegasus topology","restricted Boltzmann machine","quantum annealing","qubit chains","embedding time","adiabatic quantum computing"],"falsifier":"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.","tokens_in":7668,"feed_emoji":"⚛️","tokens_out":8433,"duration_ms":76752,"temperature":0.7,"pith_summary":"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.","feed_headline":"Bipartite graphs embed onto Pegasus in 0.014 s without long chains","feed_subtitle":"A periodic cell mapping eliminates qubit chains longer than six, the main source of chain-break errors in annealing.","key_machinery":"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.","core_discovery":"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}$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the Pegasus topology, its cell structure, degree, and maximum embeddable clique and bipartite sizes that parameterize the construction.","marker":"[15]"},{"why":"The closest prior method for embedding restricted Boltzmann machines onto Pegasus, setting the benchmark application and comparison context.","marker":"[8]"},{"why":"Template-based minor embedding work that the paper's periodic tiling approach extends.","marker":"[5]"},{"why":"Heuristic optimization of adiabatic embeddings, providing the chain-length reduction baseline the paper compares against.","marker":"[7]"},{"why":"Introduces chain-based minor embedding and the parameter-setting problem for chains.","marker":"[3]"},{"why":"Minor-universal graph design, the theoretical background for representing complete logical structures as chains.","marker":"[4]"}],"fun_headline_variants":["Fast universal embedding for bipartite graphs on Pegasus","99.98% faster embedding for large bipartite graphs","Periodic tiling embeds K_{120,120} in 0.014s","No qubit chain over six with periodic Pegasus embedding","Closed-form minor embedding for large bipartite graphs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Fast universal embedding for bipartite graphs on Pegasus","99.98% faster embedding for large bipartite graphs","Periodic tiling embeds K_{120,120} in 0.014s","No qubit chain over six with periodic Pegasus embedding","Closed-form minor embedding for large bipartite graphs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000697,"raw_usage":{"total_tokens":3129,"prompt_tokens":906,"completion_tokens":2223,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":2138}},"tokens_in":522,"tokens_out":2223,"duration_ms":15289,"temperature":1.0,"reasoning_tokens":2138,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:13:24.513165+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Embedding restricted boltzmann machines onto quantum annealers using pegasus topologies,","cited_arxiv_id":null,"evidence_quote":"The closest prior method for embedding restricted Boltzmann machines onto Pegasus, setting the benchmark application and comparison context."},{"cited_title":"Template- based minor embedding for adiabatic quantum optimization,","cited_arxiv_id":null,"evidence_quote":"Template-based minor embedding work that the paper's periodic tiling approach extends."},{"cited_title":"Optimizing adiabatic quantum embedding for large-scale problems,","cited_arxiv_id":null,"evidence_quote":"Heuristic optimization of adiabatic embeddings, providing the chain-length reduction baseline the paper compares against."},{"cited_title":"Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design","cited_arxiv_id":"1001.3116","evidence_quote":"Minor-universal graph design, the theoretical background for representing complete logical structures as chains."}],"review_version":1}