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?


Your Answer

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

Browse other questions tagged or ask your own question.