Why did D-Wave choose the Chimera graph the way they did?

Question

D-Wave makes use of a $(n,k=4)$-Chimera structured graph in their computers. Meaning a $n\times n$ grid of unit cells, with each unit cell consisting of a complete bipartite graph on $2k=8$ nodes ($4$ for each side), also called $K_{4,4}$.

Why did D-Wave chose $k=4$? An argument given is that this non-planar structure allows for an embedding of many interesting problems. However, $K_{3,3}$ is also a non-planar graph. So why not choose $k=3$? Additionally, increasing $k$ seems to me as one of the easiest ways to increase the number of qubits your problem has. So why not use $k=5,6,\dots$?

Answer 1

You are right that $K_{3,3}$ is non-planar, but as you said yourself, a larger $k$ is much better. If they could do $K_{1000,1000}$ that would be nice, because each qubit could be coupled to 1002 qubits (1000 within the $K_{1000,1000}$ and two to the neighboring cells). Instead D-Wave is limited to problems which can be embedded such that each qubit couples to at most 6 other qubits.

The reason they don't have larger $k$ is for physical reasons. It is harder to couple a qubit to 1002 qubits than it is to couple it to 6 qubits. It is also harder to couple a qubit to 6 qubits vs 5 qubits, but they found that it was easy enough to go to $k=4$, so they were not limited to $K_{3,3}$.

Answer 2

user1271772's answer is entirely correct. I was going to comment with additional information to help answer nippon's question, but I just created this account and apparently there's a reputation requirement before adding comments.

D-Wave's superconducting flux qubits are niobium metal loops that form a "hash symbol" made of two flat layers that have been stretched out and laid parallel. One layer is 90-degrees rotated from the other. When you move charge (current) in a loop it produces a magnetic field perpendicular to the plane of the loop. When you move a magnetic field through a charge-carrying loop it induces motion in the charge (current). But the amount of induction is partly determined by the size of the overlapping area (not linearly, since perfect overlap doesn't mean perfect induction, and non-overlapping adjacent wires still do it) so you can't currently usefully overlap 1000x1000 because the influence on each neighbor would be small. Stacking more layers is hard for the same reason wireless charging only just started to not suck.

The D-Wave uses Niobium loops interspersed with these amazing little quantum-permeable membrane slices called Josephson Junctions (that won their discoverer a Nobel before he went a little wacky) cooled to just above 0 kelvin, so they can hold a charge with zero resistance. Basic quantum computing hardware generally has to be robust to decoherence, which means it can't interact much with the outside environment (should be its own Hamiltonian). There's already a ton of control hardware and stuff that has to go into keeping it all stable. Every time they move the machine they have to recalibrate it (at least with the DW2) and a new random arrangement of like 90% of the qubits will work until it's calibrated again. So it's actually a harder problem than just fitting to a chimera graph. Needs to be a readily radiation-hardenable system of some kind, e.g. a neural network.