New approach to multiplication suggests how to improve quantum computers

In practice, quantum computers cannot run many programs designed for classic computers, since they do not know how to selectively forget information. A 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. It was in almost all respects better than the old, except for one thing: my favorite races did not start on it. I remember how I thought - why do I need a newfangled computer if it does not run my favorite program?

The same problem exists with quantum computers. In theory, they are capable of anything that a 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 from Google AI Quantum, located in Santa Barbara (California), describes a quantum version of the classical algorithm for quickly multiplying very large numbers. On classic computers, this algorithm has been running for quite some time. But before Gidni’s work, it was not clear whether it would be possible to adapt it for quantum machines.
')
More importantly, the multiplication algorithm belongs to the class of commonly used computer science algorithms. Gidni believes that his new technology will allow quantum computers to implement the entire class of these algorithms, which so far were considered too cumbersome to use in a quantum machine.

This multiplication algorithm benefits from the discovery, which became the first breakthrough in multiplication made over several thousand years. The traditional school multiplication method requires n ² steps, where n is the number of characters in the multiplied numbers. For thousands of years, mathematicians believed that there was no more effective approach.

But, as we recently explained in the article " Mathematicians Found the Ideal Way to Multiply Numbers, " in 1960 the Soviet mathematician Anatoly Karatsuba discovered a faster way. His method was to break long numbers into shorter ones. To multiply two eight-digit numbers, for example, you must first divide them into two four-digit ones, then split each of them into two two-digit numbers. Then you need to perform several operations with double digits and restore the result of the final multiplication. To multiply very large numbers, the Karatsuba method takes far fewer steps than the school method.

When a classic computer works according to the Karatsuba algorithm, it deletes the information in the process. For example, restoring two-digit numbers back to four-digit ones, he forgets two-digit ones. Now he is only interested in four-digit numbers. The classic version of the algorithm is similar to a climber who throws his gear as he ascends - he can move faster if he doesn’t carry all the junk with him.

But quantum computers cannot discard information.

Quantum computers perform computations through manipulations with quantum bits, or “qubits.” They are intertwined with each other, or tangled. This confusion gives enormous possibilities to quantum computers: instead of storing information in separate bits, quantum computers use the complex interactions of all qubits. As a result, for certain tasks, quantum computers are capable of exhibiting an exponentially greater computational power compared to classical ones.

However, the same property that makes quantum computers so powerful also makes them fragile. Since qubits are tangled, it is impossible to change some of them without affecting all the others. This makes it impossible to selectively delete information that is available to classic computers. Dropping qubits is like cutting out parts of a web — even a single cut could destroy the whole web.

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

In the new work, Gidni describes a quantum way of implementing Karatsuba multiplication, which does not require a large memory consumption. Instead of generating intermediate values ​​to produce a final result, it uses the " tail recursion optimization " method to directly convert the input data to the 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 spawning extra qubits,” said Thomas Vaughn , a specialist in quantum information at Creighton University.

Gidni believes that his method will work to adapt many classical recursive algorithms for quantum computers. So far, quantum computers are in such an embryonic state that they can hardly cope with the multiplication of single-digit numbers. However, the algorithm is ready, and when their schemes are improved, they will become capable of much more.