Weirdly interconnected qubits give D-Wave a big jump in performance
D-Wave’s architecture becomes more complex while machine gets faster, more capable.
Last week, D-Wave announced a new version of its quantum annealing computer. The new machine includes a number of technical improvements, as well as a significant change to the physical arrangement of the board. What does all this mean? Combined with D-Wave’s online resources, a tool that verges on useful is starting to take form.
Making a smooth computer
Before we reach the gooey chocolate center, we have to deal with the crusty outer coating: what is a quantum annealer? Most computers work in a straightforward manner: to add two numbers together, you construct a set of logical gates that will perform addition. Each of these gates performs a set of specific and clearly defined operations on its input.
But that is not the only way to perform computation. Most problems can be rewritten so that they represent an energy minimization problem. In this picture, the problem is an energy landscape, and the solution is the lowest-possible energy of that landscape. The trick is finding the combination of bit values that represents that energy.
To do this, we start with an energy landscape that is flat: we can start all the bits in the lowest energy of this flat landscape. Then we carefully and slowly modify the landscape around the bits until it represents our problem. If we have done that correctly, the bits are still in their lowest energy state. We obtain a solution by reading off the bit values.
Although this works without anything quantum being involved, D-Wave does this with quantum bits (qubits). That means the qubits are correlated with each other—this is called quantum entanglement. As a result, they change value together, rather than independently.
This allows something called quantum tunneling. Imagine a qubit stuck in a high energy state. Nearby, there is a lower energy state that the qubit would prefer to be in. But to get to that low energy state, it first has to go to an even higher energy state. In a classical system, this creates a barrier to reaching the lower energy state. But in a quantum system, the qubit can tunnel through the energy barrier to enter the lower energy state.
These two properties may allow a computer like the one that D-Wave operates to obtain solutions for some problems more quickly than its classical counterpart.
The devil, however, is in the details. Within the computer, an energy landscape is produced by the coupling (physical connection) among qubits. The coupling controls how strongly the value of one qubit influences the value of the rest of them.
This has always been the major sticking point of the D-Wave machine. Under ideal circumstances, every qubit would have couplers that link it directly to every other qubit. That many connections, however, is impractical.
A qubit all alone
The consequences of the lack of connectivity are severe. Some problems simply cannot be represented by D-Wave machines. Even in cases where they can, the computation can be inefficient. Imagine that a problem required qubits one and three to be connected, but they are not directly connected. In that case, you have to search for qubits that are common to both. Say qubit one is linked to qubit five, while qubit two is linked to qubits five and three. Logical qubit one is then one and five combined. Logical qubit three is qubits two and three linked together. D-Wave refers to this as a chain length of, in this case, two.
Chaining costs physical qubits, which are combined to create logical qubits, making fewer available for the computation.
D-Wave’s development path has been one of engineering ever more complicated arrangements of qubits to increase the connectivity. By increasing the connectivity, the chain lengths become shorter, leaving a larger number of logical qubits. When qubits are tied together to create more connectivity, a larger number of problems can be encoded.
The efficiency of structuring some problems is going to be very, very low, meaning that the D-Wave architecture is simply not suited to those problems. But as the connectivity increases, the number of unsuitable problems goes down.
In the previous iteration of this machine, the qubits were structured in blocks of eight, such that connectivity between diagonal blocks was improved compared to two versions ago (see the animated gif). This introduced a small improvement in chain lengths.
Now D-Wave has moved on to a Pegasus graph. I don’t know how to describe it, so I’m going to describe it incorrectly in the strict graph theory sense but in a way I think will make more sense overall. Instead of a single basic unit of eight qubits, there are now two basic units: a block of eight and a pair.
In the eight qubit blocks, the qubits are arranged as before, with an inner loop and an outer loop. But, as you can see below, the inner and outer loops have an extra connection. That means that each qubit has five connections within that small block.
The blocks are no longer arranged in a regular grid, either, and the interconnections between the qubits from separate blocks are much denser. Whereas the previous generation connected outer loop qubits to outer loop qubits, now each qubit is connected to both inner and outer loops of neighboring blocks.
Then, on top of that, there is a new network of long-range connections between different blocks. Each qubit has a long-range connection to another qubit in a distant block. The density of the long-range connectivity is increased by the second basic building block: connected pairs. The pairs are placed around the outside of the main block pattern to complete the long-range connectivity.
The idea, I think, is to ensure that the eight qubit groupings near the sides of the chip still have nearly the same connectivity as inner groups, unlike in the chimera graphs.
Make the chains shorter
What does all this mean? First of all, the similarity between the chimera and pegasus graphs means that code developed for chimera should still work on pegasus. The increased connectivity means the chain lengths are significantly reduced, making calculations more reliable.
To give you an idea of how much the new graph improves the situation, a square lattice with diagonal interconnects requires a chain length of six in the chimera graph and chain length of two in the pegasus implementation. In general, chain lengths are reduced by a factor of two or more. The run times are reduced by 30 to 75 percent on the new machine.
Aside from the new graph, D-Wave has improved at a technical level: the qubits have lower noise, and there is a much larger number of qubits. The plan is that the new architecture will eventually get D-Wave to 5,000 qubits (up from 2,000). Using the chimera architecture, this would be a nice (but not stellar) upgrade. Adding the changes in architecture means many more of those physical qubits can be used as independent logical qubits, making this a much more significant upgrade.