Very brief background

In quantum annealing, the discrete optimization problem we wish to solve (such as finding the minimum of $b_1b_2 - 3b_1 + 5b_3b_4$ for binary variables $b_i$) may have a connectivity between the variables that doesn't match the connectivity between the qubits in the hardware. To deal with this, we may use more than one physical qubit to represent one logical qubit, so that at least one member of the "chain" of physical qubits, is connected in hardware to the other logical qubits that the original problem demands.

Literature that says "uniform" chains are preferred

If in the final embedding of the logical problem into the hardware graph, all "chains" span the same number of qubits, then the embedding is called "uniform". This definition is given in the second paragraph of section 1.1 of this excellent paper by D-Wave, which strongly emphasizes the desire to have "uniform" chains, and prioritizes uniformity of the chain lengths over pretty much every other property that we would think is important for solving our problem most efficiently (i.e. having uniform chains is more important than minimizing the total number of qubits, total number of couplings between the qubits, total number of "chains", longest length of "chains", total number of qubits inside "chains", etc.).

The paper's only justification for desiring uniform chain lengths, is given in this sentence:

"One desirable feature of native clique embeddings is uniform chain length, which results in uniform, predictable chain dynamics throughout the anneal [13]."

Reference [13] is Davide Venturelli's excellent 2014 paper. While [13] does do quite a substantial amount of analysis about quantum annealing and embedding of graphs, where are they portraying the message that uniform chains are preferred over other aspects such as "total number of qubits used" and "total number of qubit-qubit couplings"?

The reason why I ask

The team at D-Wave that designed the Pegasus architecture describes "optimal embeddings" based on the triangle embedding, which is an embedding that's sold based on being uniform (see the second paragraph of section 1.1 in the first paper referenced in this question).

However, the triangle embedding for 12 logical qubits with all-to-all connectivity, requires 48 physical qubits, 102 qubit-qubit couplings, and 12 chains of length 4 while the following embedding only requires 46 physical qubits, 100 qubit-qubit couplings and some chains with a length of only 3:

{0: [42, 31, 39, 47], 1: [25, 61, 53, 49], 2: [56, 32, 8], 3: [40, 29, 37, 45], 4: [13, 10, 58, 34], 5: [28, 36, 44], 6: [12, 59, 35, 11], 7: [27, 63, 55, 51], 8: [60, 52, 26, 50], 9: [24, 48, 62, 54], 10: [14, 57, 9, 33], 11: [43, 30, 46, 38]}

The embedding here seems superior to the triangle embedding in every single way except that instead of having all chains contain 4 qubits, it has some chains with 4 qubits and some with 3 qubits. All along in this research area, people have always told me that shorter chains are more desirable, which completely makes sense since they require fewer qubits and couplings, but the above papers suggest that we'd rather have some chains longer than necessary in order to have uniformity: why is uniformity so important here, that we would rather use more qubits and qubit-qubit couplings than mathematically needed, even when there's embeddings that require fewer resources and have chain lengths that are only 1 or 2 qubits shorter than others in the same embedding?

  • $\begingroup$ Did you find an answer to this question? $\endgroup$
    – Andrew O
    May 6, 2022 at 14:35
  • $\begingroup$ @AndrewO Do you know the answer? :D $\endgroup$ May 6, 2022 at 18:06

2 Answers 2


It could be related to chain strengths. For longer chains, you might need to set a higher chain strength, than for shorter. If you have chains of different sizes, then chain strengths will differ. Then, if you auto-scale the QUBO to fit into the bias/coupling ranges, the D-Wave software will make sure the QUBO is scaled lower than the chain-strengths, as to try to limit chain-breaks. The scaled QUBO might then have some terms so downscaled that the QUBO no longer represents the original problem very well.

I could be wrong, but I couldn't comment on the question so I just write it here.

  • $\begingroup$ I'm curious how you found this question? For a year it had no activity, then suddenly I got the comment from Andrew and the answer from you! $\endgroup$ May 22, 2022 at 2:57
  • $\begingroup$ I am learning about (and using) the D-Wave annealer, at the moment. Wondering about the same thing, a Google search took me here. BTW, for me the simplest way to find out what varying chain-length uniformity does to the anneals is to run my problem(s) for different embeddings (if possible) and study the results. But I would also like to know the real reason behind the importance of uniformity. $\endgroup$
    – fishboi
    May 23, 2022 at 7:12

Short story: From the mathematical point of view, it is not necessary at all. There don't even need to be chains in the embedding; it can be arbitrary (disjoint, connected) subgraphs. From the physical point of view, it still needs to be investigated once the embedded Ising problem can be formulated for different embeddings such that it is provably equivalent to the original one.

Long story: It is all about formulating an embedded Ising problem that correctly represents the original one that actually shall be solved. That means, the embedded problem provides (optimal) solutions that directly correspond to (optimal) solutions of the original problem. If we could set the chain strength to 'infinity' (respectively some very large value), we would not need to care about the chain breaking. This however is prevented by the machine precision which requires the coefficients to be nicely distributed in a certain range.

At the moment finding the sweat spot is done somehow handwavy: The whole function is scaled down by some factor and the chain strengths are set to some value, hoping it is enough such that the chains do not break but that the machine still has an acceptable coefficient range (influencing the success probability), and usually the results are evaluated afterwards to adjust something and repeat the annealing...

For this procedure, chains with a uniform length seem to be easier to evaluate. It is also assumed that do have a kind of a similar 'dynamical behaviour' during the annealing process. I think, one hopes that the probability that one of the chains breaks is at least equally distributed over all of them. But I do not really see these points, as the chains are usually connected very differently to other chains and thus nevertheless experience different pertubations. Furthermore these arguments also mix up two things: the mathematical formulation of embedded problem and the annealing process afterwards. This kind of 'guessing' of the chain strength does in general not result in a mathematical equivalence between the embedded and the original Ising problem. And if the embedded problem is miss-specified, the machine will not be able to find the solution corresponding to the optimal original one.

Thus, only if the embedded Ising problem can correctly be formulated for whatever embedding (which was not the case until now), we can investigate the influence of different embeddings and whether uniform chains are indeed preferable.

For more on the mathematical background, have a look here in chapter 4 ;) https://opendata.uni-halle.de/handle/1981185920/91398

  • $\begingroup$ I do not see the answer to the question here. Can you perhaps write a 1 paragraph answer straight to the point? $\endgroup$ Sep 6, 2022 at 12:17
  • 1
    $\begingroup$ What I wanted to say is that IMO there is no clear evidence at the moment why uniform chains should be preferred $\endgroup$
    – Ello
    Sep 6, 2022 at 12:48
  • $\begingroup$ Perfect! +1 on the comment :) $\endgroup$ Sep 6, 2022 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.