Science —

D-Wave’s quantum optimizer pitted against traditional computers

D-Wave generally comes out on top, but there are some mixed results.

One of D-Wave\'s chips.
One of D-Wave\'s chips.

Back in 2007, a company called D-Wave made waves by claiming it had built a 16-bit quantum computer at a time when most academic labs could only manage a handful of bits. What they demonstrated, however, wasn't a quantum computer in the sense that most people use the term. The company has since started calling its device a "quantum optimizer." Although it's not a general-purpose quantum computer, the hardware does seem to be capable of tackling some computationally hard challenges.

The actual performance of the hardware and the software that controls it (called, somewhat ironically, the Black Box) hasn't really been described in detail. That situation seems to be changing this week, as a pair of academic researchers will be presenting a set of problems tackled both by D-Wave's hardware and by software running on more traditional computers. The results generally show D-Wave's equipment performing well, but it doesn't always beat the more mundane computers.

In a quantum computer, a set of qubits are both entangled and placed in a superposition state where they have a mixture of the two possible values (zero and one). The system is manipulated to perform a calculation, and then the actual values held by the qubits are read in order to provide the solution.

Although it's quantum in nature, D-Wave's computer doesn't work that way. Instead, it uses a process called quantum annealing, which involves a set of interacting bits that are dropped to their lowest energy state. The energy of the system is then altered so that its final state represents a solution to a calculation. If this process is done gradually enough, the system will remain in its ground state throughout the process. When the process is complete, reading out the state of these bits—which are in a new ground state—will provide an optimal solution to the problem.

In purely hypothetical terms, this process should work to provide a quick solution to a specific subset of problems. Reality, though, can be more challenging. The annealing process has to be done slowly and at a temperature near absolute zero. Even then, environmental energy can sometimes bump the system out of its ground state. To account for this, the calculation has to be repeated a number of times to determine the typical answer it produces. When all this is considered, it's not a foregone conclusion that the system will outperform traditional computers.

Two computer scientists (from Amherst College and Simon Fraser University) have gotten time on the D-Wave system and have run it against three different software solvers running on traditional hardware. To provide a serious challenge, the authors focused on a set of optimization problems that are NP-hard, meaning that the challenge of computing a solution goes up rapidly with the number of items involved in the problem. (For example, the optimal route for visiting 20 cities is much harder to calculate than it is for 10 cities.) The precise problems they tested are termed the Quadratic Unconstrained Binary Optimization (QUBO), Weighted Maximum 2-Satisfiability, and Quadratic Assignment Problem.

The software was run on a set of seven quad-core Xeons. D-Wave's hardware consisted of a dual-Xeon quad-core front end that manages the problem solving and interfaces with its custom quantum annealing chip, which has a bit that allows current to run in circles within a wire (in either a clockwise or anticlockwise direction) to represent the value of the bit. During the quantum annealing process, the current is in a superposition of the two possible values, but it gets resolved to one or the other during the readout.

Like any other computer equipment, not every bit of the D-Wave chip is functional. But since there are far fewer functional bits, this can be a significant problem. The chip used in this work is primarily the V5 version, which has 439 working bits. It simply can't solve problems involving a larger number of options. During the testing, however, the V6 chip became available and had more than 500 working bits.

One of the problems (QUBO) used maps directly to quantum annealing, meaning that the calculation can be performed on D-Wave's custom chip. In that case, the hardware dominates, coming in about 3,600 times faster than the closest software competitor. Using the newer chip and a 503-bit problem, D-Wave's advantage went up to 10,000 times faster.

For the other problems, however, D-Wave is forced to rely on large-scale sampling to find local optimizations that may or may not be the optimal solutions. Here, by some measures, the software running on standard computational hardware came out ahead. It generated answers as much as five times faster than the D-Wave hardware. But even here, D-Wave's system had some advantages—it provided more potential solutions than its competitors.

The good news for D-Wave is that when the system is given a problem it can work with, it really powers through it. The challenge right now is that there are a number of problems that don't map directly onto its hardware. More broadly, the company is going to rely on finding real-world problems that map onto the sort of math that its hardware does well. In this case, QUBO is commonly used in machine learning problems. This area has a variety of applications, so there's definitely potential here.

The paper describing this work will be presented at the ACM's Computing Frontiers meeting; a copy was made available to The New York Times.

Channel Ars Technica