Optimised Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph
Salvatore Sinno 1 Thomas Groß , 1 Nicholas Chancellor 1 Bhavika Bhalgamiya , 2 and Arati Sahoo 2 · 2025
Read Optimised Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph by Salvatore Sinno 1 Thomas Groß , 1 Nicholas Chancellor 1 Bhavika Bhalgamiya , 2 and Arati Sahoo 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-21112.txt.
Introduction
Salvatore Sinno and colleagues presented in 2025 a faster way to map large problems onto quantum annealers. Such machines need a step called minor embedding, which links one problem variable to a chain of physical qubits. Long chains cause errors and slow the work down, so shorter chains are much better.
Their method uses the repeating layout of the Pegasus hardware to build embeddings for complete bipartite graphs in a set pattern. Against the standard Minorminer tool, it cut embedding time by almost all for a large test graph and removed long chains. The team says this should help quantum machine learning, anomaly detection, and large optimization tasks scale up.
Catalog record
| CREATOR | Salvatore Sinno 1 Thomas Groß , 1 Nicholas Chancellor 1 Bhavika Bhalgamiya , 2 and Arati Sahoo 2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-21112
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimised Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph Salvatore Sinno 1 Thomas Groß , 1 Nicholas Chancellor 1 Bhavika Bhalgamiya , 2 and Arati Sahoo 2 Abstract Minor embedding is essential for mapping large-scale 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×120 complete bipartite graph. 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. I Introduction Adiabatic quantum computing systems based on superconducting qubits impose strict physical constraints on hardware connectivity. Specifically, each qubit is restricted in terms of both its degree, limiting the number of direct couplers and the physical length of couplers, restricting connections to nearby qubits only. Although the physical arrangement of qubits can be adapted to some degree, practical quantum hardware graphs are fundamentally bounded-degree, edge-length-constrained geometric layouts. Embedding logical problems, such as the Ising Hamiltonian, onto these hardware architectures is thus constrained by these physical limitations. If the logical graph is not directly representable within the hardware’s connectivity constraints, a technique known as minor embedding must be applied. Minor embedding involves mapping logical qubits onto interconnected physical qubit chains, ensuring logical connectivity by creating subtrees that effectively behave as single logical qubits. The impact of minor embedding extends beyond just execution time—it also affects the quality of the solution. In many cases, to achieve the required connectivity between qubits, the embedding process forces the creation of long chains of physical qubits to represent a single logical qubit. These chains, which correspond to higher-order neighbourhoods in the quantum hardware graph, introduce structural vulnerabilities. When chains exceed a critical length threshold (typically more than six qubits long), they become increasingly prone to breakage due to thermal noise, fabrication imperfections, and quantum decoherence. This leads to unreliable computational results, as broken chains disrupt the logical qubit representation and degrade the overall performance of the quantum algorithm. Therefore, optimizing the minor embedding process is essential for ensuring efficient use of AQC resources, reducing computation overhead, and improving the accuracy and stability of the final solutions obtained from quantum annealing. Our Contribution: This paper introduces an optimized minor embedding framework designed for mapping large complete bipartite graphs (e.g., Restricted Boltzmann Machines (RBMs)) onto adiabatic quantum processors. Our main contributions are: 1. A universal minor-embedding framework tailored for efficiently embedding large complete bipartite graphs onto quantum annealers, notably leveraging the Pegasus topology. 2. A significant reduction in qubit chain lengths, thus enhancing embedding stability and computational performance compared to established embedding algorithms, including Minorminer. 3. Empirical evaluations demonstrate that our embedding approach enables faster embedding (at least two orders of magnitude faster than other metaheuristic approaches) II Related Work A scalable superconducting architecture for adiabatic quantum computation (AQC) was initially proposed by Kaminsky et al. [ 1 ] , based on the transverse-field Ising Hamiltonian. D-Wave Systems Inc. subsequently developed superconducting quantum processors using flux qubits connected via tunable coupling devices [ 2 ] . Despite these hardware advancements, embedding complex optimization problems, including complete bipartite graphs, onto such quantum processors remains a challenging task in AQC. Early embedding techniques, such as the TRIAD method [ 3 , 4 ] , were designed to efficiently embed complete graphs ( K_{n} ) by mapping each vertex to chains of qubits arranged in regular patterns. Although these methods minimize coupler overhead for fully connected topologies, they often provide suboptimal embeddings for bipartite structures (i.e., complete bipartite graphs). In particular, the chain-based minor embeddings typically grow in length for bipartite graphs, increasing vulnerability to decoherence and chain breakage [ 3 , 4 ] . Recent minor-embedding strategies have focused on optimizing hardware efficiency specifically for bipartite graphs, leveraging the structured layouts found in modern quantum architectures [ 5 , 6 ] . Serra et al. [ 5 ] demonstrated a template-based approach that significantly reduces embedding overhead, and Goodrich et al. [ 7 ] alongside Zbinden et al. [ 8 ] presented systematic heuristics that achieve practical reductions in chain length for bipartite embeddings, particularly on Pegasus topologies. These advances highlight the importance of architecture-specific and graph-specific optimization strategies to ensure efficient utilization of quantum resources. An important practical application of complete bipartite graphs arises in Restricted Boltzmann Machines (RBMs), which have received considerable attention in Quantum Machine Learning (QML) due to their ability to model complex probability distributions. Quantum Annealing approaches for RBM training have shown promise in generative modelling and anomaly detection [ 9 , 10 , 11 ] . In these scenarios, Quantum RBMs (QRBMs) leverage the Ising Hamiltonian to implement the bipartite structure directly on quantum hardware, reducing simulation overhead and potentially enhancing performance [ 12 , 13 ] . Consequently, the choice of quantum processor topology, such as Chimera or Pegasus, critically impacts the scalability and accuracy of QRBMs by affecting qubit connectivity and embedding complexity [ 6 , 13 ] . Benedetti et al. [ 9 ] underscored the necessity of tailored embedding approaches for specific quantum architectures when deploying RBMs. Building on these insights, our proposed universal embedding framework seeks to address the limitations in existing minor embeddings for complete bipartite graphs. By systematically exploiting the enhanced connectivity in modern quantum processors, our approach ensures both scalable and robust embeddings of bipartite structures, thereby offering a practical pathway for quantum-enhanced generative modelling and anomaly detection tasks. III Theoretical Analysis III-A Optimal Embedding of Complete Bipartite Graphs on Pegasus This section presents a theoretical analysis of the optimal embedding for complete bipartite graphs on quantum annealing architectures. A complete bipartite graph is a unique graph divided into two distinct node groups (or sets). Each node in one set is connected to every node in the other set, but there are no connections between nodes within the same set. A Restricted Boltzmann Machine (RBM) is an example of a complete bipartite graph, as it has two sets of units—visible and hidden—with each visible node fully connected to all hidden nodes and no internal connections within the same layer. An adiabatic quantum architecture can represent an undirected graph U with weighted vertices and edges. Each vertex i\in V(U) corresponds to a qubit, and each edge ij\in E(U) corresponds to a coupler between qubits i and j . Throughout the discussion, we will use qubit and vertex , as well as coupler and edge , interchangeably when there is no ambiguity. Each qubit i has two associated weights: h_{i} (the qubit bias) and \Delta_{i}