3
$\begingroup$

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?

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

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\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 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 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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