Is D-Wave a Quantum Computer?

Quantum computing is one of the most interesting fields of study nowadays, both from theoretical and pragmatic point of views. A universal quantum computer can potentially solve certain problems, as factorizing numbers, much faster and with fewer resources than a classical one ¹. This developing technology is based on the use of quantum mechanics as a new framework for computation. On quantum computers the information is not store, neither compute, in classical bits, but in quantum bits. The principal difference between classical and quantum bits is that qubits can be in superposition of two different states. Unfortunately, there is a general agreement about the state of the art, and it is that we are still far from having an operable universal quantum computer. Recent experimental groups have developed different architectures, but they are still small and they can operate just a few qubits. Hence, the principal concern regarding the real utility of quantum computers is the possibility of designing one that handles a few hundred qubits, at least.

One milestone in the direction of quantum computing has been recently released, by the private company DWave . This company has developed an operable quantum simulator of 128 qubits, called D-Wave One. Furthermore, they are going to install a new version, called D-Wave Two, with capability for operating with 512 qubits, for a new laboratory created by Google and NASA ². Hence, the question now is what this new machine does, and if it is really a quantum computer.

What is D Wave and which problem can it solve?

D-Wave is based in a technology called superconducting flux qubits. The qubits it operates are grouped in 4×4 units, with different connections between them. A scheme of the architecture is shown in Fig. 1. The first version has 128 qubits, but tot all of them can be used for computing, as some of them are disconnected from their neighbors.

This new machine should be considered a quantum simulator more than a universal quantum computer. It does not perform universal quantum computation, because it cannot make arbitrary operations in all qubits.

Basically the principal problem D-Wave can solve is the problem of quantum annealing. That is to find the ground state, that is the state with lowest energy, of an Ising spin glass model. This problem is known to be a non polynomial (NP) hard problem. Because of that when the dimension of the problem growths linearly the complexity of finding a solution growths in an exponential way. There are no indications that allow us to conclude that a quantum computer can solve this problem in a non-exponential way, but in any case it can give an important speedup over classical computers.

A fair question regarding this, or any, new technology is which really useful problems can it solve. Directly, it can solve only annealing, but this is interesting enough, because this problem is as hard as the hardest problem in the NP class. In this class there are many popular problems, as the salesman, factoring or minimization in artificial intelligence. If any of these problems is mapped to the problem of annealing it could be solved by the use of this new technology. The way of mapping each concrete algorithm is, of course, highly non trivial.

How can D-Wave be tested?

Recently, a test of the quantumness of D-Wave has been performed ³. For this purpose several researchers performed computer simulations in both the quantum machine and classical computers. They compare principally three approaches, D-Wave, a classical simulation of how quantum annealing should perform in quantum simulators, and the best known classical. For obvious reasons, the last two approaches were run in classical computers.

In Figure 2, the principal differences between these three approaches are displayed. For this simulation the authors selected 1000 different configurations and they launched each of them 1000 times, with different initial states. The plot shows how many configurations were found as a function of the success probability of finding the correct answer for each configuration.

The interpretation of this figure is clear. Classical and quantum annealing exhibit very different behaviors. For classical algorithms the distribution presents only one maximum, and most of the problems have one half probability of being solvable. For the quantum case there are many “easy” and “hard” problems and that leads to a distribution with two maxima, closed to zero and one. These result points in the direction that really D-Wave behaves in a quantum way, as its results are closer to the simulation of a quantum system than to a classical algorithm.

Finally, the authors also analyzed the scaling of the computation time with the size of the problem, but the results are inconclusive. The optimization problem for 108 qubits is quite easy, and it is difficult to see if there is a quantum speedup. This question could be potentially addressed by the next generation of quantum annealers, which are expected to have 512 qubits.

Conclusions

Based in the research performed Boixo et al there are many indicators that D-Wave is a genuine quantum annealer. On the other hand, it is not faster than classical ones. In any case it is definitively a milestone in the field of quantum computer, because it also represents a paradigm shift. Instead of creating a universal quantum computer with a few qubits, the developers of D-Wave have focused in a quantum device with many qubits that can perform only one task.

Only time can clarify if this is the beginning of a new time in quantum computing. If D-Wave Two really beats classical computers in annealing it will be the first time a quantum device can compute a general problem better than classical ones. This problem can be, at least potentially, useful to many other fields.