Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Minor-embedding planar graphs in grid graphs

Ehsan Tavakoli

Published May 17, 2016• 0 citations
OpenAlex

Abstract

A recent development in solving challenging combinatorial optimization problems is the introduction of hardware that performs optimization by quantum annealing. Exploiting this hardware to solve a problem requires first solving a graph minor-embedding problem, which is also apparently intractable. Motivated by this application, we consider the special case of finding a minor-embedding of a planar graph in a grid graph. We introduce two algorithmic approaches to the problem, based on planarity-testing techniques. For one approach, we provide an implementation and an experimental evaluation demonstrating its potential.

Related papers

Planarity Based Algorithms for Minor Embedding in Grid Graphs

Seyedeh Sahba Etezad

We present heuristic algorithms for minor embedding planar graphs in grids. Our work is motivated by the development of quantum computing hardware that performs quantum annealing. This hardware can be used to solve hard combinatorial problems, but requires the graph of each problem instance to be minor embedded in a graph that models the hardware. Hence, there is a need for practical minor embedding algorithms. We restrict our attention to planar graphs, and thus are able to make use of existing graph drawing methods. We present two algorithms for minor embedding planar graphs in grid graphs, and provide an experimental evaluation of one.

•Jul 20, 2016•1 citation

Quantum annealing correction with minor embedding

Walter Vinci, Tameem Albash, Gerardo A. Paz-Silva +2 more

Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a two-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with ``planted'' (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems but also when minor embedding is used to extend the connectivity of physical devices.

arXiv:1507.02658•Physical Review A•Oct 9, 2015•102 citations

Scalable embedding of parity constraints in quantum annealing hardware

Michele Cattelan, Jemma Bennett, Sheir Yarkoni +1 more

One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.

arXiv:2405.14746•Physical Review A•Jan 23, 2025•4 citations

Exploring Topologies in Quantum Annealing: A Hardware-Aware Perspective

Mario Bifulco, Luca Roversi

Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem $P$ via QA involves a hardware-aware circuit compilation which requires representing $P$ as a graph $G_P$ and embedding it into the hardware connectivity graph $G_Q$ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU). Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of $G_P$ -- the logical variables of $P$ -- to a chain of adjacent nodes in $G_Q$ by means of one of its minors, so that the arcs of $G_P$ are preserved as physical connections among qubits in $G_Q$. The static topology of hardwired qubits can clearly lead to inefficient compilations because $G_Q$ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology $G_Q$ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise. We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map $G_P$ into a minor of $G_Q$. Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of $G_P$, exhibiting smoother scaling of the largest embeddable $G_P$ as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.

quant-pharXiv:2511.03327•Nov 6, 2025•1 citation

4-Clique network minor embedding for quantum annealers

Elijah Pelofske

Quantum annealing is a quantum algorithm for computing solutions to combinatorial optimization problems. This study proposes a method for minor embedding optimization problems onto sparse quantum annealing hardware graphs called 4-clique network minor embedding. This method is in contrast to the standard minor embedding technique of using a path of linearly connected qubits in order to represent a logical variable state. The 4-clique minor embedding is possible on Pegasus graph connectivity, which is the native hardware graph for some of the current D-Wave quantum annealers. The Pegasus hardware graph contains many cliques of size 4, making it possible to form a graph composed entirely of paths of connected 4-cliques on which a problem can be minor-embedded. The 4-clique chains come at the cost of additional qubit usage on the hardware graph, but they allow for stronger coupling within each chain, thereby increasing chain integrity, reducing chain breaks, and allow for greater usage of the available energy scale for programming logical problem coefficients on current quantum annealers. The 4-clique minor embedding technique is compared with the standard linear path minor embedding with experiments on two D-Wave quantum annealing processors with Pegasus hardware graphs. We show proof-of-concept experiments where the 4-clique minor embeddings can use weak chain strengths while successfully carrying out the computation of minimizing random all-to-all spin glass problem instances. Published by the American Physical Society 2024

arXiv:2301.08807•Physical Review Applied•Mar 13, 2024•19 citations

Minor Embedding for Max-Cut: Empirical Analysis of Quantum Annealing’s Combinatorial Bottleneck

Ron Lavi, Alberto Moraglio, Ofer M. Shir

Quantum optimization by annealing constitutes a stochastic global search over QUBO-formulated combinatorial optimization problems. Its performance depends on pre-solving the Minor Embedding (ME) challenge—the $\mathcal{N}\mathcal{P}$-hard problem of mapping logical graphs representing QUBOs onto the quantum hardware. Despite determining solution feasibility and quality, ME remains understudied as a standalone optimization challenge. Current understanding is largely limited to synthetic graphs on isolated topologies, leaving the generalizability of structural predictors across hardware generations unclear. We conduct the first cross-topology study analyzing the MINORMINER heuristic—the de facto industry standard—over ≈550 benchmark graph instances across D-Wave’s Chimera, Pegasus, and Zephyr architectures. Our analyses reveal a functional dissociation between embedding feasibility and cost: topological independence (via Maximum Independent Set ratio) predicts feasibility by identifying structural ‘slack’, while edge density—reflecting clique-like proximity—governs the resource ‘toll’ (chain length). Since ME is a purely graph-theoretic problem, agnostic to the combinatorial origin of the source graph, these structural predictors apply to any QUBO whose logical graph falls within the studied structural regime. This dissociation remains invariant across all architectures, establishing ME as a benchmark for Evolutionary Computation, where the local distribution of edges, rather than global density alone, determines algorithmic difficulty.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2026•0 citations
A recent development in solving challenging combinatorial optimization problems is the introduction of hardware that performs optimization by quantum annealing. Exploiting this hardware to solve a problem requires first solving a graph minor-embedding problem, which is also apparently intractable. Motivated by this application, we consider the special case of finding a minor-embedding of a planar graph in a grid graph. We introduce two algorithmic approaches to the problem, based on planarity-testing techniques. For one approach, we provide an implementation and an experimental evaluation demonstrating its potential.
We present heuristic algorithms for minor embedding planar graphs in grids. Our work is motivated by the development of quantum computing hardware that performs quantum annealing. This hardware can be used to solve hard combinatorial problems, but requires the graph of each problem instance to be minor embedded in a graph that models the hardware. Hence, there is a need for practical minor embedding algorithms. We restrict our attention to planar graphs, and thus are able to make use of existing graph drawing methods. We present two algorithms for minor embedding planar graphs in grid graphs, and provide an experimental evaluation of one.
Quantum annealing provides a promising route for the development of quantum optimization devices, but the usefulness of such devices will be limited in part by the range of implementable problems as dictated by hardware constraints. To overcome constraints imposed by restricted connectivity between qubits, a larger set of interactions can be approximated using minor embedding techniques whereby several physical qubits are used to represent a single logical qubit. However, minor embedding introduces new types of errors due to its approximate nature. We introduce and study quantum annealing correction schemes designed to improve the performance of quantum annealers in conjunction with minor embedding, thus leading to a hybrid scheme defined over an encoded graph. We argue that this scheme can be efficiently decoded using an energy minimization technique provided the density of errors does not exceed the per-site percolation threshold of the encoded graph. We test the hybrid scheme using a D-Wave Two processor on problems for which the encoded graph is a two-level grid and the Ising model is known to be NP-hard. The problems we consider are frustrated Ising model problem instances with ``planted'' (a priori known) solutions. Applied in conjunction with optimized energy penalties and decoding techniques, we find that this approach enables the quantum annealer to solve minor embedded instances with significantly higher success probability than it would without error correction. Our work demonstrates that quantum annealing correction can and should be used to improve the robustness of quantum annealing not only for natively embeddable problems but also when minor embedding is used to extend the connectivity of physical devices.
One of the main bottlenecks in solving combinatorial optimization problems with quantum annealers is the qubit connectivity in the hardware. A possible solution for larger connectivity is minor embedding. This technique makes the geometrical properties of the combinatorial optimization problem, encoded as a Hamiltonian, match the properties of the quantum annealing hardware. The embedding itself is a hard computational problem, and therefore heuristic algorithms are required. In this work we present fixed, modular, and scalable embeddings that can be used to embed any combinatorial optimization problem described as an Ising Hamiltonian. These embeddings are the result of an extension of the well-known parity mapping, which has been used in the past to map higher-order Ising Hamiltonians to quadratic Hamiltonians, which are suitable for existing quantum hardware. We show how our new embeddings can be mapped to existing quantum annealers and that the embedded Hamiltonian physical properties match the original Hamiltonian properties.
Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem PPP via QA involves a hardware-aware circuit compilation which requires representing PPP as a graph GPG_PGP​ and embedding it into the hardware connectivity graph GQG_QGQ​ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU). Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of GPG_PGP​ -- the logical variables of PPP -- to a chain of adjacent nodes in GQG_QGQ​ by means of one of its minors, so that the arcs of GPG_PGP​ are preserved as physical connections among qubits in GQG_QGQ​. The static topology of hardwired qubits can clearly lead to inefficient compilations because GQG_QGQ​ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology GQG_QGQ​ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise. We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map GPG_PGP​ into a minor of GQG_QGQ​. Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of GPG_PGP​, exhibiting smoother scaling of the largest embeddable GPG_PGP​ as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.
Quantum annealing is a quantum algorithm for computing solutions to combinatorial optimization problems. This study proposes a method for minor embedding optimization problems onto sparse quantum annealing hardware graphs called 4-clique network minor embedding. This method is in contrast to the standard minor embedding technique of using a path of linearly connected qubits in order to represent a logical variable state. The 4-clique minor embedding is possible on Pegasus graph connectivity, which is the native hardware graph for some of the current D-Wave quantum annealers. The Pegasus hardware graph contains many cliques of size 4, making it possible to form a graph composed entirely of paths of connected 4-cliques on which a problem can be minor-embedded. The 4-clique chains come at the cost of additional qubit usage on the hardware graph, but they allow for stronger coupling within each chain, thereby increasing chain integrity, reducing chain breaks, and allow for greater usage of the available energy scale for programming logical problem coefficients on current quantum annealers. The 4-clique minor embedding technique is compared with the standard linear path minor embedding with experiments on two D-Wave quantum annealing processors with Pegasus hardware graphs. We show proof-of-concept experiments where the 4-clique minor embeddings can use weak chain strengths while successfully carrying out the computation of minimizing random all-to-all spin glass problem instances. Published by the American Physical Society 2024
Quantum optimization by annealing constitutes a stochastic global search over QUBO-formulated combinatorial optimization problems. Its performance depends on pre-solving the Minor Embedding (ME) challenge—the NP\mathcal{N}\mathcal{P}NP-hard problem of mapping logical graphs representing QUBOs onto the quantum hardware. Despite determining solution feasibility and quality, ME remains understudied as a standalone optimization challenge. Current understanding is largely limited to synthetic graphs on isolated topologies, leaving the generalizability of structural predictors across hardware generations unclear. We conduct the first cross-topology study analyzing the MINORMINER heuristic—the de facto industry standard—over ≈550 benchmark graph instances across D-Wave’s Chimera, Pegasus, and Zephyr architectures. Our analyses reveal a functional dissociation between embedding feasibility and cost: topological independence (via Maximum Independent Set ratio) predicts feasibility by identifying structural ‘slack’, while edge density—reflecting clique-like proximity—governs the resource ‘toll’ (chain length). Since ME is a purely graph-theoretic problem, agnostic to the combinatorial origin of the source graph, these structural predictors apply to any QUBO whose logical graph falls within the studied structural regime. This dissociation remains invariant across all architectures, establishing ME as a benchmark for Evolutionary Computation, where the local distribution of edges, rather than global density alone, determines algorithmic difficulty.