As the singer Javier Krahe used to say, it is the talk of the town (va de boca en boca), both in the quantum computing community and in the general news, that a Google team has achieved quantum supremacy. It certainly sounds impressive. Which is something, especially in a world where corporate hype is almost as important as science per se, due to the huge investments needed to play on this board.
For those who don’t need an informative approach to the subject, the original article can be found here.
For the rest of the world, let’s explain in a nutshell what this quantum supremacy thing is all about. The devil, of course, is in the details. Let’s first see what it does NOT mean, in order to clear up some of the usual misunderstandings that are created when reading news reports on this subject:
1) It does NOT mean that quantum computers have been shown to be more powerful than conventional computers. The relationship between classical complexity (understood as a formal, mathematical concept) and quantum complexity is not yet well understood. The consensus (broad, but still in the realm of conjecture) among the quantum computing community is that, for example, quantum algorithms that solve NP-complete problems in polynomial time will not be found. In short, problems that we know for sure are hard (at least assuming that P is not NP-complete) will remain so, no matter how quantum we go about it.
2) It does NOT mean that it has been proven that for some problems quantum computers are faster. We have known that for a long time. Specifically since David Deutsch in 1985 created an ex-profeso problem to demonstrate that a quantum computer (then still only existing in theory) could perform a certain task in fewer steps than a conventional one. You can read the original article here.
3) It does NOT mean, certainly, that our privacy, banking passwords or e-mails are at risk. Conventional encryption of information circulating on the Internet depends on the practical intractability of the integer factorisation problem. And, as Peter Shor proved in 1994 there is a quantum algorithm for factoring integers that is theoretically (and let’s emphasise “theoretically“) fast – at least faster than the known conventional ones. However, it is estimated that to break RSA2048 (the most common encryption method today) we need around 4,000 qubits. Maybe more. Maybe more. Sycamore, the chip used by Google in its experiment, has 54.
Once we have banished all these outlandish ideas, we will say that what is commonly understood by the bombastic appellation of quantum supremacy is the observation that a quantum computer can solve, in a reasonably short time, a problem that a conventional computer would find impossible in practice (i.e., the time required would be excessive). Obviously, this is not a precise definition as we are used to in mathematics, and this, as we shall see, has consequences.
The problem in question, as was the case with Deutsch’s Problem, is a problem created specifically to demonstrate this and, as such, did not seek practical applications. In this sense, it is worth noting that Scott Aaronson, one of the leading figures in the field, has a randomness certification protocol that can be used by the Google problem.
Without going into a description of the problem (an excellent analysis can be found in the previous reference), we cannot fail to mention the controversy between Google and IBM, the great adversaries in the quantum race, over what is meant by “a reasonably short time”. According to Google, Sycamore solved in about 200 seconds what a conventional computer would solve in 10,000 years. IBM was quick to issue a note downplaying the significance of the matter. Subsequently, they refined it a little more and developed in an interesting preprint how to solve the problem proposed by Google on a conventional computer in about 60 hours.
As we can see, the foggy definition of quantum supremacy gives a lot of room for manoeuvre, and will surely continue to do so, in this new race where so much money is on the table: the investments of both sides, or those of the Chinese state, for example, are around 500 million dollars a year each. As has happened in other great scientific-technical rivalries in history, let us hope that the real triumph will not belong to anyone in particular, but to the human spirit in its struggle for the conquest of knowledge.
Leave a Reply