⚛️ quantum physics

Addressing the Minor-Embedding Problem in Quantum Annealing and Evaluating State-of-the-Art Algorithm Performance

This study investigates the critical impact of embedding quality on D-Wave quantum annealer performance, revealing a correlation between average chain length and solution error while demonstrating that the standard Minorminer algorithm requires significant improvement compared to deterministic alternatives like Clique Embedding.

Original authors: Aitor Gomez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez

Published 2026-03-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Aitor Gomez-Tejedor, Eneko Osaba, Esther Villar-Rodriguez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Map-Making" Problem

Imagine you have a complex puzzle (a math problem) that you want to solve using a super-specialized robot (a Quantum Annealer). This robot is incredibly fast, but it has a very strange limitation: it can only understand puzzles that are built in a very specific shape, like a giant honeycomb or a grid of roads.

However, most real-world problems (like scheduling flights, optimizing traffic, or designing drugs) are messy. They don't look like a honeycomb; they look like a tangled ball of yarn.

The Minor-Embedding Problem is the challenge of taking that "tangled ball of yarn" and forcing it to fit onto the robot's "honeycomb" without breaking anything. To do this, you often have to use multiple robot parts to represent a single piece of your puzzle.

The Analogy: Imagine you are trying to fit a large, irregularly shaped sofa into a small, square elevator. You can't just shove it in. You might have to disassemble the sofa, wrap its legs in protective foam, and use two people to carry one leg. In this analogy:
- The Sofa is your math problem.
- The Elevator is the Quantum Computer.
- The People carrying the leg are the "chains" (groups of qubits) used to represent one variable.

The Two Main Questions the Authors Asked

The researchers wanted to answer two big questions:

Does the quality of the "fit" matter? (If we use a clumsy, bulky way to fit the sofa, does the robot solve the puzzle worse?)
Is the current tool we use to fit the sofa any good? (The standard tool is called Minorminer. Is it the best we can do, or is it clumsy?)

Finding #1: A Bad Fit Ruins the Solution

The researchers discovered that how you fit the problem onto the machine matters more than you think.

The Analogy: Think of the "chains" (the groups of robot parts holding one variable) as a team of people holding hands to carry a heavy box.
- If the team is short (short chains), they can move quickly and stay in sync.
- If the team is long (long chains), it's harder for everyone to agree on which way to turn. If one person lets go or moves the wrong way, the whole team drops the box.

The Result: The longer the chains (the more "people" you need to carry one piece of the puzzle), the more likely the robot is to get confused and drop the box.

The Data: They found a direct link: Longer chains = More errors.
The Takeaway: Even if the robot is perfect, if you force it to solve a problem using a clumsy, stretched-out map, the answer will be wrong. The "quality of the map" dictates the quality of the answer.

Finding #2: The Standard Tool (Minorminer) is Flawed

The industry standard for making these maps is an algorithm called Minorminer. It's like the "Google Maps" of quantum computing—it's the default app everyone uses. The researchers tested it against a rival tool called Clique Embedding (which is designed for the worst-case scenario: perfectly connected, messy problems).

The Shocking Result:
Minorminer is often doing a worse job than the "worst-case" tool, even on problems that aren't the worst case.

The Analogy: Imagine Minorminer is a GPS app that tries to route you through a city.
- Minorminer is a greedy driver who takes the first turn they see to save time, often getting you stuck in traffic or taking a longer route than necessary.
- Clique Embedding is a super-planner who knows the city perfectly. It takes a bit longer to plan the route, but once it does, the route is perfect.

What the researchers found:

It fails often: For many types of problems, Minorminer simply couldn't find a way to fit the puzzle onto the robot at all, while the other tool could.
It's inconsistent: Sometimes Minorminer finds a great fit; other times, it finds a terrible, bulky fit for the exact same problem. It's like rolling the dice every time you try to solve a problem.
It's slow: Because it's a "greedy" algorithm that tries to fix things step-by-step, it takes a long time to calculate the map. The rival tool (Clique Embedding) is actually faster for many problems because it has a pre-calculated plan.

The Bottom Line

The paper concludes that we are leaving a lot of performance on the table.

Because the current standard tool (Minorminer) is often creating "bad maps" (long, messy chains), the quantum computers are solving problems with more errors than they need to. If we could find better ways to map these problems—perhaps by combining the best features of different tools or inventing new strategies—we could make quantum computers significantly more powerful and accurate, even with the hardware we have today.

In short: The hardware is getting better, but the "software map" we use to talk to it is still a bit clumsy. Fixing the map is the key to unlocking the true power of quantum computing.

1. Problem Statement

The paper addresses the Minor-Embedding Problem (MEP), a critical bottleneck in quantum annealing (QA).

Context: Quantum annealers (specifically D-Wave systems) solve Ising models by sampling low-energy states. However, the hardware topology (e.g., Pegasus graph) has limited connectivity compared to the fully connected or complex graphs required by real-world combinatorial optimization problems.
The Challenge: To map a problem graph (source) onto the hardware graph (target), variables must often be represented by chains of multiple physical qubits. This mapping is the MEP.
The Core Issue: Finding an optimal embedding (minimizing the number of qubits used) is an NP-Hard problem. Current hardware relies on heuristic algorithms, primarily Minorminer, to solve this.
Motivation: There is a significant performance disparity when QA solves "hardware-native" problems versus those requiring complex embedding. The authors hypothesize that the quality of the embedding (specifically the number of qubits used and chain length) directly dictates the solution quality of the quantum annealer.

2. Methodology

The study employs a rigorous experimental framework to evaluate the relationship between embedding quality and QA performance, and to benchmark the standard algorithm (Minorminer).

Experimental Setup

Hardware: D-Wave Advantage_system4.1 processor (5,627 qubits, broken Pegasus topology).
Problem Generation: Random Erdös-Rényi (ER) graphs were generated with varying sizes (10 to 300 nodes) and densities (0.05 to 1.0). These were formulated as Ising models.
Algorithms Compared:
- Minorminer: The standard greedy heuristic provided by D-Wave.
- Clique Embedding (CE): A deterministic algorithm designed for fully connected graphs, used here as a "worst-case" baseline (since it is optimized for the most difficult connectivity scenarios).
Parameters:
- Chain Strength: Varied using the Uniform Torque Compensation (UTC) function with different prefactors (0.5 to 2.0).
- Patience Parameter: Varied in Minorminer to generate embeddings of differing qualities.
Metrics:
- Embedding Quality: Measured by Average Chain Length (ACL) and total qubit count.
- QA Performance: Measured by Median Relative Error (comparing QA energy to classical reference solvers: MST2 Tabu Search and Simulated Annealing).
- Stability: Measured by the standard deviation of ACL across multiple runs.

Research Questions (RQs)

RQ1: What is the impact of embedding quality (specifically ACL) on the performance of the quantum annealer?
RQ2: How effective is Minorminer compared to Clique Embedding (CE) in terms of success rate, quality, stability, and execution time?

3. Key Contributions & Results

RQ1: Impact of Embedding Quality on QA Performance

Correlation with Error: The study establishes a clear, positive correlation between Average Chain Length (ACL) and relative error. As ACL increases, the probability of finding a valid solution (without broken chains) drops exponentially.
Solution Space Degradation: Longer chains expand the solution space of the embedded Ising model. Due to hardware noise and the probabilistic nature of QA, a larger solution space significantly reduces the likelihood of sampling the ground state.
Chain Strength Trade-offs:
- High chain strengths minimize broken chains but distort the energy landscape, leading to poor solution quality.
- Low chain strengths allow for better energy landscapes but result in frequent broken chains.
- Finding: Even with optimal chain strength tuning, poor embeddings (high ACL) consistently yield worse solutions than good embeddings, regardless of the problem size.

RQ2: Evaluation of Minorminer vs. Clique Embedding (CE)

The authors found that Minorminer, the industry standard, has significant limitations compared to the "worst-case" baseline (CE):

Embedding Success: Minorminer fails to find valid embeddings for dense graphs (density > 0.5) and large sizes (approaching 177 nodes) where CE succeeds.
Embedding Quality (ACL):
- Counter-intuitively, CE outperforms Minorminer in terms of qubit usage (shorter ACL) for graphs with densities as low as 0.10–0.15, provided the source graph's average degree exceeds the hardware's average degree.
- Minorminer only produces shorter chains when the problem graph is significantly sparser than the hardware topology.
Stability (Dispersion): Minorminer exhibits high variability. For the same problem, different runs can produce embeddings with ACL differences of up to 4 qubits per chain. This instability means a single run might yield a suboptimal embedding, drastically hurting QA performance. CE is deterministic and stable.
Execution Time:
- CE: Requires a one-time preprocessing step (~43 seconds) but then generates embeddings in microseconds ( $10^{-5}$ s).
- Minorminer: Constructs embeddings from scratch for every instance. For large, dense graphs, it frequently hits the 1000-second timeout limit.
- Conclusion: When accounting for preprocessing, CE is faster than Minorminer for over 50% of the tested cases, particularly for large/dense instances.

4. Significance and Implications

Critical Role of Embedding: The paper proves that the minor-embedding problem is not just a preprocessing step but a primary determinant of quantum annealing success. Poor embedding quality degrades performance exponentially, often negating any quantum advantage.
Re-evaluation of Standards: The results challenge the reliance on Minorminer as the default solver. The study suggests that Clique Embedding (CE) should be considered for a much broader range of problems (not just fully connected ones), specifically when the problem's connectivity exceeds the hardware's native connectivity.
Future Directions:
- Hybrid Strategies: Combining CE (for initial structure) with Minorminer (for local refinement).
- Problem-Aware Embedding: Modifying algorithms to prioritize embedding high-impact variables into shorter chains.
- Multiple Executions: Running Minorminer multiple times in parallel to mitigate its instability and select the best embedding.
- Broader Benchmarks: Testing on other graph types (e.g., Barabási-Albert, d-regular) and next-gen hardware (Zephyr topology).

Conclusion

The study concludes that the minor-embedding problem remains a substantial hurdle for quantum annealing. The current standard, Minorminer, is often suboptimal, unstable, and slower than deterministic alternatives like Clique Embedding for a wide range of problem densities. Improving embedding strategies is essential to unlocking the full potential of current and future quantum annealers.