Quantum acceleration

The sensational quantum computer turned out to be a quantum, but not quite a computer

The D-Wave 2X device, claiming the title of the first quantum computer in the history, managed to solve the computing problem 100 million times faster than a regular computer. This was stated by the scientific work of a group of researchers from Google, who, even before going out in the reviewed magazine, managed to make a lot of noise. Radio Liberty explains why any news from the world of quantum computers seems to be a sensation and whether the revolution actually occurred.

Golden calf

The quantum computer is the same obligatory attribute of the beautiful world of the soon future as thermonuclear energy, cancer panacea or new physical theory outside the standard model. And in the same way, quantum computers are beckoning, but they slip away from the hands: a quick (or even accomplished) creation of an effective device that can perform quantum calculations, is constantly announced and constantly turns out to be untruthful, half -truth, in a word, in a word, trading in expectations.

However, few doubt that the “real”, almost useful quantum computer will still appear in a relatively close future. For example, Ruslan Yunusov , General Director of the Russian Quantum Center, talks about the prospect of 10 years. For this, it also says that there are no fundamental physical obstacles to the creation of a quantum computer, and the fact that many scientific and engineering groups with good financing are already being carried out in this direction. And most importantly, quantum computers, which in theory will have many orders of higher performance than classic ones, really very much needs humanity. Progress has become a synonym for the growth of performance, and the growth rate of the capacities of traditional processors slows down, no longer comply with the Law of Moore. About when exactly the physical limit of the evolution of classic computers will be achieved, disputes are underway, but the creation of a quantum computer will immediately make these conversations meaningless. Against this background, any news about progress in building a quantum computer causes a lot of noise in the press, and the champion in creating high-profile information reasons for this kind is the Canadian company D-Wave, which produces the same devices.

Obsessive marketing

The D-Wave startup was founded in 1999 by the physicist and the worldwide champion in Brazilian Jiu-Jitsu Jordi Rose. The company was originally more marketing than technological: at a time when quantum calculations were nothing more than a bold idea on paper, Rose managed to attract impressive investments to create a prototype of the quantum computer, which went to finance specialized academic and scientific laboratories. Today, under the D-Wave brand, three generations of computing devices have been published, the last, D-Wave 2X, was presented in August 2015.

The D-Wave Two computer was acquired by the NASA, Google collaboration and the University Space University Association (USRA). It is known that the previous version of the car, D-Wave One, went to the American military-industrial company Lockheed Martin for about $ 10 million, so it is easy to assume that here the transaction value is unlikely to amount to a lower amount. Before selling the Google device, d-Wave ordered an independent study that was supposed to confirm the company's statements that their black box is a really quantum computer, in other words, the device, which use the effects of quantum mechanics and which has higher performance than ordinary computers. The work published following the results of the research stated that the D-Wave Two really copes with some type of optimization tasks in just half a second, while the most powerful IBM processors are required to search for the right solution for more than half an hour. The transaction took place, but, oddly enough, the question of the real essence of the machine has not yet been completely closed. There are two main reasons for this: firstly, D-Wave managed to earn the reputation of the company inclined to let the dust of the eye, and each of her statements meets with the famous skepticism. Secondly, in the main ones, it is not so easy to prove that this device is a quantum computer, if only because you can call this term different things.

Quantum magic or speed?

According to the most general definition, quantum computers are computing devices that use quantum effects in their work, that is, the phenomena of quantum confusion and quantum superposition. However, it is almost impossible to make sure that this this machine does not really do in its calculations without these effects. Therefore, applicants for the title of quantum computer are evaluated not by content, but by abilities: they are expected to be able to solve algorithmic problems much faster than classic computers, that is, to demonstrate the so -called “quantum acceleration”, or Quantum Speedup. But here there is obvious uncertainty: what tasks should be compared on? What exactly traditional computers to compare? And with what classic algorithms - are they also very much different in speed?

From a practical point of view, the “correct” quantum computer should solve a wide range of computing tasks noticeably faster than any classic computer that uses any classic algorithm. From this, by the way, it will inevitably follow that the operation of the device really does not do without quantum magic. But checking such a universal Quantum Speeedup is technically almost impossible. And in the case of D-Wave it is impossible even in principle: this machine can solve only one and very specific computing task-finding a minimum of a function among a set of candidate solutions, and only one method-using the so-called quantum annealing or, in other ways, expressing themselves, quantum normalization.

Black box

Generally speaking, it is very important to understand about the D-Wave device that it cannot be called a computer in the full sense-in any case, in the usual sense of the word. “Computers are usually called universal computing devices that can solve any mathematical problems,” says Yunusov. “In this sense, D-Wave is not a computer, it is a quantum device that can solve a certain class of problems, namely to look for minimums of cost functions.” Moreover, D-Wave does not solve this problem as an ordinary computer that would require a program, an algorithm. Here, the solution is achieved during the natural physical evolution of the system, when it gradually reaches the state of the energy minimum. For comparison, imagine that you want to find out which hole the roulette wheel will fall into a ball running at a certain speed. If you accurately take into account all the parameters, it is not so easy to solve such a problem. But you can just start the ball in a real roulette and see where it turns out. About this does D-Wave.

Scott Aaronson , professor of the Computer Science Massachusetts Institute of Technology, a specialist who has not been the first year to consistently criticize the technology of D-Wave, says this: the only task that the D-Wave device can solve is to simulate himself. So what did the authors of the article compared such a car symunition? The natural evolution of the quantum system, which is the physical basis of the machine, can be algorithmically simulated using the so -called imitation of quantum annealing. The real quantum annealing works faster than any classical simulation due to a quantum tunnel effect: in some cases, a particle that should take its place in a crystal lattice can jump over a potential barrier without even having sufficient energy for this. A very small ball, which lacks energy to roll over the hill, can go through the laws of quantum mechanics “through” it.

A comparison of real quantum annealing, which physically occurs inside D-Wave with its algorithmic imitation, made by researchers from Google, showed that the first is 100 million times faster. “And this proves that the tunnel effect really occurs inside the D-Wave device,” says Scott Aaronsonon. Indeed, the algorithm imitating the evolution of the system does not keep up with the quantum jumping of particles through energy peaks, due to the phenomena of quantum mechanics, D-Wave has a significant handicap before its classical simulation, and if nothing quantum had happened inside the device, there would be no such difference.

Yes, it is now proven that quantum effects are used in D-Wave. But is it possible to say that she demonstrates “quantum acceleration” - knows how to solve, even only one task, but faster than any classic computer? Unfortunately no. “Even the most ordinary computer can cope with the only task that D-Wave can solve it much faster than it,” says Aaronson. “You only need to use the correct algorithm.” And there is such an algorithm-this is the algorithm of Selby, which solves the same problem-finding a minimum of function among sets of candidate solutions-faster than D-Wave quantum annealing. By the way, the superiority of the classic Selby algorithm over this device is directly said in the article of the team from Google.

So, in some rather narrow sense, D-Wave can now really be called a quantum computer. With two large “but”:

1) The device can solve only one optimization problem. Other computational tasks can theoretically be reduced to it, but the process of bringing some task to this can be so difficult that it leaning all the advantage in performance.

2) Even when solving this one problem, D-Wave overtakes only one specific and initially non-optimal classic algorithm, and is already more successful in speed. It is worth noting that, choosing it for comparison, the authors of the article did not try to cheat-the superiority of the quantum annealing D-Wave over the imitation of quantum annealing proved that the device really uses quantum effects in the work. Before that, there was no such confidence. “Quantum effects there are really participating in one way or another, the whole question is whether there is a significant“ quantum increase ”in performance,” explains Ruslan Yusunov.

***

The study preparing for publication, unfortunately, will not revolutionize quantum computers, although it will close the discussion for several years about whether D-Wave technology with pure charlatanism is. But in order for one to safely say that the quantum computer is finally created, something else must happen. “If your car using the Schora algorithm ( an algorithm theoretically designed for quantum calculations. - RS ) decomposed a number consisting of 10,000 digits into the multipliers - perhaps you can safely declare that you have created a quantum computer, although, of course, it cannot be excluded that the matter is not in quantum mechanics, but in the gammlins sitting inside the device,” Aaronson is ironicized. But this is unlikely to expect this from D-Wave: “In order to go beyond the limits of a very narrow circle of tasks, it is necessary to build a different installation, arranged differently than installing D-Wave,” Yunusov believes.

Fortunately, not only a Canadian company is engaged in the development of quantum computers, just the rest are less prone to loud statements and less often appear in media reports. “Previously, I did not give optimistic forecasts for the near future,” Aaronson notes, “but the latest results achieved by John Martiniz, Chris Monroe and other researchers inspire great optimism that obvious quantum acceleration in solving some (not, however, almost interesting) tasks will be achieved very soon.”

Aaronson notes that the creation of an industrial design will take more time. The main obstacle is the extremely whimsical conditions that the main elements of a quantum computer in their work are cubes. “We need to bring them to a certain state, make them work with each other, and then you need to measure the resulting condition. Moreover, with an increase in the number of cubes, this is increasingly difficult and more difficult,” explains Yunusov. Any, even the weakest effect on the cubes of the external environment leads to the fact that quantum magic ends. Work with them in one article was compared with an attempt to put on a smooth countertop many sharply sharpened pencils with the tips of the neck. “Have we learned to do this? In any case, how they sang Beatles in the song Getting Better , it turns out better and better,” Aaronson laughs.