10
$\begingroup$

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$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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}$.

Improve this answer
$\endgroup$
5
  • $\begingroup$ This is still quite a general answer, without much detail. Is there literature available (not necessarily from D-Wave) to back this up? $\endgroup$
    – nippon
    Jun 7, 2018 at 5:51
  • $\begingroup$ @nippon: What detail do you want? When you say "to back this up", which part of this do you want to be "backed up" ? Do you disagree that each qubit can be coupled to at most 6 other qubits (4 within the $K_{4,4}$ cell and 2 from neighboring cells) ? This is the connectivity graph for a D-Wave chimera. You can see each physical qubit couples to at most 6 others. $\endgroup$
    – user1271772
    Jun 8, 2018 at 15:12
  • $\begingroup$ It is not that I believe your answer is incorrect. But to me it appears as if the answer is, "they have this topology, because they chose for it". If that is the case, then it's okay. If not, then I would like some literature/directions on why this choice was made. $\endgroup$
    – nippon
    Jun 13, 2018 at 12:49
  • $\begingroup$ @nippon: There is no literature on why the choice was made. D-Wave is a private company and their architecture is protected by patent law. Just like Intel will not publicize every detail about their architecture in journals where AMD and NVIDIA will see it, D-Wave has the right to do the same. You should know though, that if they didn't use $k=5$ it's because there is some physical limitation which would make a $k=5$ implementation less ideal than what they have for $k=4$. It is not clear what exactly you want to know. $\endgroup$
    – user1271772
    Jun 13, 2018 at 14:43
  • $\begingroup$ I have found perhaps the origin of the $K_{4,4}$ structure in the chimera. Out of all papers I've seen, it first appears in this paper by D-Wave 8 years ago, and 1 year before the D-Wave One was first released. $\endgroup$
    – user1271772
    Oct 21, 2018 at 3:51
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3

Your Answer

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

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