New Multiplication Approach Tips How to Improve Quantum Computers

In practice, many programs designed for classical computers cannot be run on quantum computers because they cannot selectively forget information. New multiplication algorithm shows how to get around this problem.

Classic bits are black and white, and quantum bits are a bit more complicated.

When I was 9, my parents bought a new computer. In almost all respects, he was better than the old one, except for one: my favorite races did not start on it. I remember how I thought - why do I need a newfangled computer if it does not start my favorite program?

Quantum computers have the same problem. In theory, they are capable of everything that the classic is capable of. In practice, their quantum nature makes it almost impossible to run some of the most important classical algorithms.

That is why the work , published on April 15, contains good news. Craig Gidney, a computer scientist at Google AI Quantum in Santa Barbara, California, describes a quantum version of the classic algorithm for quickly multiplying very large numbers. On classic computers, this algorithm has been running for quite some time. But before Gidney's work, it was unclear whether it would be possible to adapt it for quantum machines.

More importantly, the multiplication algorithm belongs to the class of ubiquitous computer science algorithms. Gidney believes that his new technique will allow quantum computers to implement the entire class of these algorithms, which so far have been considered too cumbersome to use in a quantum machine.

This multiplication algorithm takes advantage of the discovery, which was the first breakthrough in multiplication made over several thousand years. The traditional school method of multiplication requires n ²steps, where n is the number of characters in multiplied numbers. For several thousand years, mathematicians believed that a more efficient approach did not exist.

But, as we recently clarified in the article “ Mathematicians discovered the ideal way to multiply numbers, ” in 1960, Soviet mathematician Anatoly Karatsuba discovered a faster way. His method was to split long numbers into shorter ones. To multiply two eight-digit numbers, for example, you must first break them into two four-digit numbers, then break each of them into two two-digit numbers. Then you need to carry out several operations with two-digit numbers and restore the result of the final multiplication. To multiply very large numbers, the Karatsuba method takes much less steps than the school method.

When a classic computer runs on the Karatsuba algorithm, it deletes information in the process. For example, restoring two-digit numbers back to four-digit ones, he forgets two-digit numbers. Now he is only interested in four-digit numbers. The classic version of the algorithm is similar to a climber throwing out his equipment as he ascends - he can move faster if he does not carry all the junk with him.

But quantum computers cannot discard information.

Quantum computers carry out calculations through manipulations with quantum bits, or "qubits." They are intertwined with each other, or confused. This confusion gives quantum computers enormous opportunities - instead of storing information in separate bits, quantum computers use complex interactions of all qubits. As a result, for certain tasks, quantum computers are able to demonstrate exponentially greater computing power compared to classical ones.

However, the same property that makes quantum computers so powerful also makes them fragile. Since qubits are entangled, it is impossible to change some of them without affecting everyone else. This makes it impossible to selectively delete information available to classic computers. Knocking back qubits is like cutting parts of a web - even a single cut can destroy the entire web.

This requirement for the preservation of information complicates the creation of quantum versions of recursive algorithms - that is, turning to themselves. In computer science, recursive algorithms are used very widely, however, in order to work in the best way, they need the computer to discard information at every step. Without this, computing will quickly become impractical. “If you save information each time you perform an operation, the space it occupies will grow with the number of operations,” said Ashley Montanaro , a quantum information specialist at the University of Bristol. Any practical machine will run out of memory quickly.

In a new work, Gidney describes a quantum method for implementing Karatsuba multiplication, which does not require a large memory consumption. Instead of generating intermediate values ​​to get the final result, it uses the " tail recursion optimization " method to directly turn input into output. This allows the algorithm to avoid creating intermediate information that a quantum computer cannot discard. “He gets rid of the problem of extra qubits without generating extra qubits,” said Thomas Vaughn , a quantum information specialist at Creiton University.

Gidney believes his method will work to adapt many classic recursive algorithms for quantum computers. So far, quantum computers are in such an infancy that they can barely cope with the multiplication of single digits. However, the algorithm is ready, and when their schemes are improved, they will become capable of much more.