Skip to main content
Back

D-Wave's Minorminer Is Quietly Killing Your Quantum Annealing Results

A new evaluation finds that D-Wave's default minor-embedding tool leaves substantial performance on the table, often losing to a simpler deterministic alternative.

Pro

  • Study quantifies how minor-embedding quality dominates D-Wave quantum annealer accuracy, above noise and tuning.
  • Average chain length correlates linearly with relative error; valid solutions shrink exponentially as chains lengthen.
  • Minorminer, D-Wave's default embedder, loses to deterministic Clique Embedding on moderately dense graphs up to 177 nodes.
  • Minorminer chain lengths vary by up to 4 qubits per chain across runs on identical problems, urging multiple executions.
  • Dense large instances frequently hit Minorminer's 1,000-second cutoff; Clique Embedding returns in microseconds after preprocessing.
  • Full code and Erdős-Rényi benchmarks are open source on GitHub.

Quantum annealers are supposed to shine on hard combinatorial optimization problems, but there is a catch that rarely makes it into the marketing material: the problem you want to solve almost never fits the shape of the hardware. Getting it to fit is called minor-embedding, and a new study argues that the default tool everyone uses for this step, D-Wave's Minorminer, is quietly costing users a lot of solution quality.

The paper, Addressing the Minor-Embedding Problem in Quantum Annealing, published in Future Generation Computer Systems, does two things: it measures how much embedding quality actually matters for the final answer, and it stress-tests Minorminer against Clique Embedding, a deterministic method designed for the worst case. The verdict is that Minorminer has significant room to improve, and that for a surprisingly large class of problems the worst-case baseline is actually the better choice.

The bottleneck hiding in plain sight

A D-Wave quantum annealer is essentially a programmable Ising solver: you give it a set of variables with biases and pairwise interactions, and it samples low-energy configurations. Its qubits are wired according to a fixed sparse topology called Pegasus, where each qubit connects to only 15 others out of roughly 5,600. That yields a graph density of about 0.0025, so any problem denser than the hardware has to be squeezed in by using multiple physical qubits to represent one logical variable. Those groups of qubits are called chains.

Four-stage quantum annealing workflow: Ising reformulation, minor-embedding, annealing, and postprocessing.

Chains are where quality goes to die. The longer the average chain, the larger the embedded problem and the more places noise can creep in. If the qubits in a chain disagree at readout you get a