If you have done any computational work, you must have spent some time waiting for your program to run. As an undergraduate, I expected computational biology to be all fun and games: idyllic hours passing time while the computer works hard to deliver results… well, very different from the more typical frenetically staring at the computer, wishing the program would run faster. But there is more — there are some problems that are so intrinsically expensive that, even if you had access to all the computers on Earth, it would take more than your lifetime to solve a slightly non-trivial case of them. Some examples are full configuration interaction calculations in quantum chemistry, factorisation of prime numbers, optimal planning, and a long, long, etcetera.

One of the greatest computer science discoveries in the last few years is the fact that a particular model of computation, quantum computing, can offer notable, when not game-changing improvements to this problems. Remarkably, Shor’s algorithm provides a polynomial-time algorithm for solving prime number factorisation, thus challenging RSA, one of the most extended encryption protocols. Many other algorithms exist, from linear algebra to knot theory. Note however that not all the problems show a quantum improvement – in fact there are many processes that show no advantage over the classical case. In any case, it is widely believed than within the next decade or two — depending on your level of optimism — there will be quantum computers that can challenge our best supercomputers for some of the aforementioned problems.

In this post I want to talk about a particular kind of quantum information processing: quantum annealing, or the more or less equivalent adiabatic quantum computing. This approach is quite popular, not only because its beauty and simplicity, but especially because the Canadian company D-Wave has announced many computers that — they claim — implement this model of computation. Note, however, that D-Wave computers are highly controversial, and many believe that they do not offer any advantage over classical computers. This has not prevented many big players, such as Ford or NASA, to buy some machines at the modest price of 15 million USD each.

 

This is how D-Wave computers look like! Fortunately, it is possible to access them through a cloud service if you don’t have an industrial storage facility nearby… Image reproduced from the D-Wave webpage.

Adiabatic quantum computing is based on a result from elementary quantum mechanics, the adiabatic theorem. This theorem states, essentially, that if you take a quantum system in the global minimum of a certain potential, and if you change that potential slowly enough  to transform it into some other potential, then the system will end up in the global minimum of the last potential. Now, if you can think a clever way to write a problem as a potential whose global minimum represents the solution… well, here you have a procedure to find the solution!

In a slightly more mathematical way, quantum annealing employs two potentials: , the initial potential, and , the the “problem” potential. The initial potential is chosen to be very simple, so that we can easily prepare the computer in the global minimum. Our final, “problem” potential is designed so that its global minimum represents the solution to our problem. We then simply transform  into , as described by:

The last element to the annealing procedure is the annealing program , that expresses exactly how  is transformed into . It is clearly a continuous function with and , and for most practical purposes you can assume it is a linear program. However, the form of this program determines the runtime of the computer, so there have been some interesting studies on how to design optimal programs that make the annealing process faster.

There is just one problem, and as it often happens with theorems, it lies in the conditions. The adiabatic theorem ensures that we will reach the global minimum of the final potential… if we do it slowly enough. However, what does “slowly enough” mean? In a more or less general parlance, the annealing time must be large in comparison with the difference between the global minimum , and the next lowest energy minimum . It is often mentioned that the scaling in adiabatic quantum computers is proportional to .

The apparent simplicity of the annealing process has opened quite a lot of discussion regarding the actual potential of quantum annealers. In particular, it is widely believed that these computers cannot solve some really hard problems, such as, for example, the optimal way to organise a trip between cities (known as travelling salesman problem). Nevertheless, this field is advancing by leaps and bounds, and we can certainly expect interesting results — positive or negative — in the next years.