We’re going to have something new today at rose.blog — our first ever guest post, by Dr. Suzanne Gildert, who is the author of the wonderful Physics and Cake blog. This post is a high level overview of the Investigating the Performance of an Adiabatic Quantum Optimization Processor paper. Suz is now an official contributor on rose.blog, so expect more insightful commentary here than usual from now on!
How do you measure the speed of an adiabatic quantum computer?
This is a tricky question to answer, but this paper gives it a shot. The paper focuses on a special kind of quantum algorithm, known as Adiabatic Quantum Optimization (AQO), which runs on a microprocessor built by D-Wave, and I’m going to try and give a high level overview of the main messages in this paper. The microprocessor itself has been built and tested using a superconducting electronics technology, but this paper concentrates on SIMULATING what it is expected to do. I’ll explain why, and what the results tell us about the promise of these processors.
AQO processors behave more like analog computers than digital ones, so it is particularly tricky to measure their ‘clock speed’ in order to compare it to other processors. Of course, we’re forgetting the fact that nowadays it is even difficult to measure the speed of processors in our home PC! This is due to the fact that they are getting more and more ‘cores’, and are also now being designed with a range of different tricks to make them speedier, which may have nothing to do with the number that you read in ‘GHz’. For example, comparing an NVIDIA Tesla processor, with 240 cores each operating at about 1.5GHz, to a fast Intel processor (say the six core core i7-980X EE) is tricky, as they are good at different tasks. Bearing this in mind will help us in understanding what it is that AQO processors actually do faster than regular processors, and why it is difficult to put numbers on this. Processors with different numbers of cores and different architectures are better at some tasks than others. Graphics processors are designed to be exceedingly good at 3D rendering calculations. AQO processors have a very unusual architecture, and are exceedingly good at their specialty task, which is solving NP-Hard optimization problems. What, you say?! OK, I’ll take a minor diversion to explain.
What is an NP-Hard optimization problem?
Even though computers can solve many problems much faster than humans, there are certain problems that even the fastest supercomputers can have trouble with. A well known example is the traveling salesman problem (TSP). This goes as follows: A salesman is trying to find the best route between cities, where he wants to sell Quantum Computers. He only needs to visit each city once, as it is unlikely that people will change their mind about whether or not to buy one within his time-frame. He wants to visit as many cities as possible, as quickly as possible, and therefore in the shortest distance possible. (In addition to maximising his chances of selling quantum computers, he is also of course striving to minimise his carbon footprint). So he is trying to calculate the best journey route to take. In the first instance, he considers just his nearest 4 cities. There are 24 different routes he could take to visit them all. It is very easy to work out the corresponding distance for each potential route, and then choose the best one. But when he decides to take the business worldwide, he suddenly hits a problem! The number of cities is now in the 100s, and even though he uses the fastest possible supercomputer he can find, he still can’t be assured of achieving the minimum distance traveled:
There are many, many problems like this in the real world. They are ubiquitous. When you try to optimize some aspect of a small number of items, your method works perfectly. But when you increase it to a few more, it suddenly becomes intractable because of the exponentially growing number of possible combinations. A nice example of this is the Eternity II puzzle, where the number of possible ways of arranging the pieces is greater than the number of atoms in the universe. Many people purchase this puzzle in the hope of ‘getting lucky’ and winning the $2M prize, unaware of the NP-Hard Behemoth that faces them.
Luckily for our salesman, he has an AQO processor, which he can use to help solve the problem.
Physics inspired processing
To explain how an AQO processor solves problems such as this, I’m going to take a second minor diversion into Physics. I’ll introduce an analogy, which I will call The Water-Machine. Imagine having a volume of water and a series of different pipes that you can fit together in different ways, like this:
Many of the pipes have restrictions, which all open and close in different ways as time advances forwards. An example is shown in the steps 1 -> 2 -> 3 -> 4.
Now imagine that you had to work out the flow rate from the end of the final pipe as you ran the machine. You could calculate the whole thing using the laws of fluid dynamics, using your desktop computer, but it would be quite a difficult task. You’d have to program in all the changing restrictions and how these would affect the flow rate at each time step…… Aha! You think – why don’t I just build the Water-Machine instead? It would be quite straightforward! So you build the Water-Machine, with a cunning series of cogs and levers to open and close the restrictions in whatever way you want as you turn a single crank. You then very carefully measure the flow rate as you turn the crank. The answer pops out in a few seconds, as opposed to your simulation, which was taking a very long time to run on your desktop machine! You’ve just built what is known as an analog computer. This specialized machine is exceedingly good at calculating flow rates from a series of particular time-dependent restrictions. However, it wouldn’t be very good at multiplying numbers together!
D-Wave’s AQO processors are effectively Water-Machines for these hard traveling-salesman-type problems. You dial in the restrictions (also known as variables) which correspond to the city distances, turn the crank, and the solution pops out. AQO processors aren’t quite as specialized as the Water-Machine, because as I mentioned earlier, there are MANY MANY problems which turn out to be NP-Hard optimization types, so there are lots of things which can be adapted for AQO processors to solve even if such processors aren’t very good at, say, multiplying numbers.
The magic arises because, like the Water-Machine, the AQO naturally tries to solve a physics problem at its very core (no pun intended). The optimization problem is how to arrange a series of spins, known as an Ising problem. You can read a bit about Ising problems here and here. It turns out that a very natural thing for physical systems to do is to try and minimise their energy (think of objects falling, water finding the lowest level, etc.). If we can somehow capture this ability of nature to find the lowest energy and formulate our problem so that the lowest energy corresponds to the minimum distance between cities, then the system will lower its energy towards the answer we want!
This is exactly what D-Wave AQO processors do. And where does the ‘quantum’ come in? Well it is widely believed that if the little spins behave quantum mechanically, they are better at finding the low energy state; that’s basically all there is to the quantum part! But I’ll just spend a little more time explaining some of the detail about how the ‘crank’ is turned (also known as the ‘algorithm’) on these processors.
A more detailed look at the AQO algorithm
The paper is mainly concerned with something known as the ‘minimum gap’. What is this? Well it is the thing that limits the speed of your computation. It is the ‘bottleneck’ in the computation, and it is what makes these problems very difficult to solve. As we turn the crank on our computation, there are points where the system can become confused and sometimes gets ‘stuck’ in the wrong answer. But quantum systems (like AQO processors) avoid this problem, as they naturally have a ‘gap’ between the right answer and the wrong answer at all times (the lowest energy state and a slightly higher energy state) during the computation. The gap is extremely important – if you built the same system of little spins without quantum mechanics, as you turn the crank the gap goes to zero at some points, and therefore it is highly likely that you’ll end up in the wrong answer. The computation has a chance of ‘following’ the wrong path!
This is shown in the diagram below. The first case is a system with quantum mechanics, and the second is one without quantum mechanics playing a role (classical):
So it is important to protect this precious quantum gap and understand where it comes from, and how it behaves as we run different computations on the processor.
However, the behavior of the gap as you increase the number of variables involved in the computation (like the number of cities in the TSP or the number of restrictions in the Water-Machine) is not easy to understand. It depends on the type of restrictions, how many there are, etc. What we DO know is that it is this ‘gap’ that determines the speed at which your computer can run (the smaller the gap, the more slowly you have to turn the crank), so the main focus of the paper is on calculating how this all-important gap depends on the number of variables in the problem. The behaviour of the gap, and therefore the AQO processor, is SIMULATED using another computing resource, which I’ll return to in a moment.
Why is this ‘gap’ so important if a regular system without a gap would still get a pretty good answer – it still ends up with a low energy, right?
True, but the gap really can make all the difference. Imagine as the number of variables increased that you could get a 10% better answer by running the problem on a quantum processor. It doesn’t sound like much, but for large companies who are interested in optimization, this 10% can translate into millions of dollars worth of savings. Think of transportation companies trying to schedule parcel deliveries, or hospitals trying to schedule and distribute resources after a natural disaster. That’s not just millions of dollars, it could be thousands of lives too. As as the problem size gets bigger, this saving might become even larger.
Why can’t we just measure the gap by running the processors? You just said there’s no point in simulating the Water-Machine if you can just build one!
We want to know what we expect to happen to the ‘gap’ before we try and build big processors to run the AQO algorithm. There are 2 reasons for this: Building real processors (unlike Water-Machines) is an expensive task, and you want to make sure that the results are going to be interesting before you go ahead and do it! Also, there is a slight chicken-and-egg situation. We need to know the size of the gap to know at what speed to run the AQO processors, so we cannot measure the gap by just running them, as we would have no idea how fast to turn the crank to get the algorithm to work properly!
Using large classical computers to simulate a quantum algorithm
One interesting result of this paper is that even though we have established that it is a good idea to simulate what the gap will do before running the processors, it turns out that this is not as easy as it sounds. Just to just calculate how this gap is expected to change with the number of variables is a HUGE computational task! It is like trying to simulate the Water-Machine on your computer. The AQO processor, just like the Water-Machine, calculates this gap as part of its natural operation. But the techniques that engineers, physicists and computer scientists use for simulating such systems on their regular general-purpose desktop machines are, at present, remarkably inefficient. The amount of computing power and time needed to simulate the AQO is incredible, and yet it is still well worth running these enormous simulations – ‘a stitch in time saves nine’ – to help our understanding of what happens when the real processors run the algorithm (which takes just a few seconds!).
The project to compute ’the gap’ undertaken in this paper uses a distributed computing platform known as AQUA@Home, which is built using the BOINC framework. This is a framework where people can dedicate spare CPU cycles from their local machines by running a piece of software in the background (it also has a funky screensaver as a bonus). The idea is very similar to that of SETI (SEarch for Extraterrestrial Intelligence, also run on BOINC) where users donate spare clock cycles to help analyse signals from deep space. A surprising amount of computing power can be harnessed via this method. AQUA gathered approximately 8000 cores for around 2 years thanks to a worldwide network of volunteers, resulting in a staggering 10^20 floating point operations being performed. The calculations of the results for the expected behavior of the gap are displayed on Figure 3 of the paper. And indeed, the gap seems to still be going strong even when the number of variables is increased to 128! So if we now turn the crank on our real processors at the rate decided by that gap, we should get the right answer….
So, back to our original question. How do you measure the speed of a quantum computer? In fact, how do you measure the speed of any processor where a direct comparison of clock speed no longer applies? Well, as we have seen, it all comes down to how people measure the performance of these processors for different specialty tasks. The common approach to address this issue is to try out the processors on different tasks, effiectively ‘racing’ them against one another in a sort of ‘Microchip Olympic Games’. The tasks that form these games are known as standard benchmark problems. Some processors are better at certain tasks than others, and then it is just up to the buyer to decide what characteristics they want from their processor by looking at the results of these benchmarks.
Being a specialty optimization technique, we obviously decided to enter our results into the ‘optimizing’ event, to see how they compared to other approaches. Because we know that the speed of our computer is determined by this ‘gap’, we can compare how fast it would be to other algorithms. This is the second main result of the paper. Figure 4 in the paper (reproduced below) shows how the AQO approach compares to similar problem solving techniques already used to solve these types of hard problems in the real world. The AQO approach seems to be approximately 10,000 times faster for these optimization problems than the best approaches currently known. So now we have calculated how fast we are allowed to turn the crank on our real processors, and it turns out that it is significantly faster than what is currently being used. As a result of this, we know that it is definitely worth building such processors, so let’s go ahead and do it!
Having invested many month’s worth of clock cycles from computer clusters around the world (not to mention several years worth of scientists’ research time!), we can now turn that all important crank for just a few seconds, and through the results of the simulations performed, be confident in the answer that this fundamentally new type of computer gives us. I personally think that’s pretty neat.