Quantum supremacy?

A Wafer of the D-Wave Quantum Computer.
By Steve Jurvetson from Menlo Park, USA

We have been speaking about quantum computers for a few decades. These computers would work with qubits (quantum bits) instead of bits, and would perform certain operations much faster than ordinary computers.

It has been known since the thirties that quantum computers cannot solve problems that cannot be solved by ordinary computers. Those problems are called non-computable. What they would do, in principle, is solve certain problems (not all) much faster than ordinary computers. That higher speed, which in some cases should be enormous, is called quantum supremacy.

Let's give an example: we know that the decomposition of a composite number into its prime factors can be difficult. It’s trivial if the factors are small, but if the composite number is the result of multiplying two prime numbers of 100 digits each (for example) it is almost impossible to break it down, if we don’t know ay least one of the prime numbers.

This fact is used to secure Internet connections, using a public key, which everyone can use to send encrypted messages to the owner, and a private key, which is used to decrypt the message. The public key is a function of the composite number, while the private key depends on the two prime numbers from which it was obtained. When the numbers are very large, it is almost impossible for anyone who does not know the private key to decipher the message encrypted with the public key, even using the most powerful existing computers. This encryption algorithm is called RSA by the initials of its inventors, who published it in 1979.

With a quantum computer with a sufficient number of qubits, it would be possible to decrypt an encrypted message with the RSA algorithm in a reasonable time. This could have unfavorable consequences, since the keys we use on the Internet would become obsolete. We must find others, probably based on quantum mechanics.

Although quantum supremacy has been announced for a long time, until now no one had proven it. In fact, there are some theorists who argue that such supremacy may not exist, because by increasing the number of qubits, the speed of the quantum computer could decrease. For that reason several companies are trying to prove it, which means doing the following:

• Build a quantum computer with a sufficient number of qubits.
• Execute a quantum algorithm that solves a certain problem and measure the time it takes.
• Solve the same problem with an ordinary computer.
• Compare the calculation times, to see if the quantum computer takes much less time than the ordinary computer.

A few months back, a possible proof of quantum supremacy (by Google) has been aired by the media. The quantum computer used (with 53 qubits) performed an operation that has no practical application, but was specially selected to distinguish quantum and classical computing. The operation is called random sampling of a circuit, which performs random operations on the qubits and then measures their values, which at the end of the process turn out to be almost random, but not quite.

According to Google researchers, to solve this problem, the world’s fastest classic supercomputer would take 10,000 years. The quantum computer, however, took just over three minutes. Quantum supremacy would have been demonstrated.

However, things are not so clear. One of Google’s competitors in the field of quantum computing, IBM, which also manufactures classic supercomputers, argues that the resolution of that problem in a classic supercomputer would only take about 60 hours. The quantum computer would be faster, yes, but the difference would be much smaller than Google claims.

Why the discrepancy? Because neither company has performed the experiment in question on an ordinary computer. They have simply estimated how long it would take, based on calculations and simulations. The results obtained are, therefore, debatable (and debated). Consequently, the issue of quantum supremacy remains unsolved.

On the other hand, some researchers think that the issue of quantum supremacy is irrelevant. What matters is ensuring that quantum computers are stable (few have been so far) and that they can operate in conditions a little more normal than near absolute zero (they need superconducting circuits). According to these researchers, efforts should be directed towards achieving these objectives, rather than proving a quantum supremacy that, after all, remains hypothetical.

The same post in Spanish
Thematic thread on Natural and Artificial Intelligence: Preceding Next

Manuel Alfonseca