Annealing and the D-Wave Quantum Computer

Today I will stay in the realm of quantum computers and I want to talk about a commercial company who delivers more than 1000 qbits in a quantum chip. This is far more what the classical embedding scheme from last time can achieve, but at close inspection it is not that impressive. Granted, the D-Wave company can boast about a venture capital investment in the 100 to 200 million range, but it is the limitations of what can they do which prevents the company to be in the hundreds of billion range. 

So what is annealing, and how does D-Wave use it to solve problems? Let me start by explaining what I did for my PhD thesis some time ago. I was working in the fiber optics area which are used to send signals (phone calls, internet traffic, TV signals). What you want to do is to increase the bit rate to take full advantage of all of the bandwidth available, but propagation over (large) distances makes the light pulses overlap with each other. Think here about big undersea fiber optic cables between say California and Japan. Key to this is the dispersion property of the optical fiber and dispersion in one point of the fiber can be different than the dispersion in another point (due to variations in manufacturing). A method is needed to measure this dispersion and the method available was to cut the fiber into 1 meter sections and measure the dispersion for each section. How can we do this in a non-destructive way? The theory of light propagation in optical fibers is well know: from Maxwell's equations, in a certain appropriate approximation one obtains the so-called nonlinear Schrodinger equation and numerical simulation methods are available to obtain the output given any input and any dispersion function. 

Now the idea is simple: send some optical pulses through the fiber and measure what comes out. Then starting with a constant dispersion map, simulate the optical pulse propagation of the input and obtain some output which will be different than the measured one. Change the dispersion map values and repeat the simulation until you get the same output as the experimental ones.

So what I had was an optimization problem: I had to minimize a "cost" function, where the cost function value is given by some measure of the mismatch between the experimental and the simulated output. The problem is that the cost function is a function of many variables (over 1000). Now how can you find the minima of an unknown function of a single variable? Start at a point and evaluate  the function. You take a step left and evaluate the function. You take a step right and evaluate the function again. Then you know if you need to move to the left or to the right, is as simple as that. To generalize in multiple variables, you need to repeat an all directions and determine the direction of the steepest descent. In other words, you determine the gradient. But how do you use the gradient? Naively you take a step along the direction of the gradient, but this is not the best strategy because you encounter the steep valley problem. I wont't go in detail on what that problem is, and the strategies to go around it, because even if you solve it, you encounter the next problem: the local minima problem.

In optimization problems you are given an unknown landscape you need to explore and your task is to find the absolute minima of the landscape. Many problems fit into this category, from training neural networks to econometric problems. Annealing is a strategy for solving the local minima problem and the inspiration comes from the technique to grow crystals. The basic idea is as follows:

suppose I gave you a tray with a two dimensional landscape built on it and I place a small ball at an arbitrary place in this landscape. The ball will naturally get trapped into a local minima. Then I ask you to shake the tray up and down with a given amplitude such that the ball will jump out of the local minima and land in another local minima (the amplitude corresponds to the temperature). Also I will tell you to keep shaking it, but slowly over time reduce the amplitude of the shaking. When the process ends, the ball will have found the local minima. Similarly, when you grow a crystal, you need to slowly reduce the temperature which will allow the molecules to find the local minima in the crystal which is growing as the temperature drops.  

The D-Wave chip is nothing but an annealing machine. However, it has a quantum twist: In quantum mechanics one encounters tunneling, and because of it the "ball exploring the landscape" can tunnel from one local minima to the next, and this is the basis of its quantum speedup because the annealing schedule can be done faster. There was much debate weather D-Wave is quantum or if it has any speedups over a classical system and Scott Aaronson was the "skeptic-in-chief". I think it is clear now that their chip is quantum, but the speedups are not really there because the kinds of the landscapes which are programmable on their computer are too simplistic. Several order of magnitude increases in the number of qbits are needed, but the good news is that D-Wave is doubling their qbit number every year.

So how does it work?

The basic building bloc is a Josephson junction which hosts a qbit. Because of the manufacturing process, different junctions are not the same and they need to be calibrated with an additional loop and a very precise magnetic flux going through it. The chip is cooled to 15 miliK for superconductivity and noise reduction and it is shielded to 50,000 times the Earth's magnetic field. The noise is still large, and repeating  a computation would result in a different answer 5% of the time.

Four superconducting loops are elongated and stacked next to each other horizontally. Then the same thing is done vertically and the two layers are coupled resulting in a 8 qbit cell which realizes an Ising Hamiltonian. The cells are connected to more cells resulting in the final chip. The coupling and the biases in the Hamiltonian are controllable and represent the actual problem being solved. This is done at room temperature. Then the chip is cooled and then the annealing process starts.

The annealing corresponds to gradually turning off an initial state Hamiltonian and turning on the Hamiltonian of the problem being solved. If done slowly, the system remains in the ground state at all times during the process. In the end the final spin configuration is read and this provides the answer. The process is repeated many times to either average the answer or get the best answer.

Now which problems can you solve using a D-Wave computer? All tasks a traditional quantum computer can do, but most of the problems (except optimization problems) are ill suited for the D-Wave chip. For example on their 1000 qbit chip, D-Wave was able to factorize the product of two prime numbers: 149 and 73: 10877=149x73, but this is a far cry from what needs to be done to break encryption. The way the factorization task is cleverly modeled on a D-Wave machine needs many orders of magnitude larger number of qbits that what is currently available. There is a lot of hype around D-Wave, but the commercially viable practical applications are few and far in between. I do not think the company covers its costs from sales, and it relies on venture capital and large grants from big companies like Google to keep increasing the number of qbits. So far they delivered on that, but if they will hit an insurmountable physical limit then the funding will evaporate. The value of the company relies mostly in its patents, and I feel that there is a very long road ahead for them to provide a genuine quantum speedup in a viable commercial setting. However it is a start.