Quantum supremacy: I,
for one, welcome our new quantum overlords.
The persistence of memory.
The announcement of Google’s
achievement of quantum supremacy1 made the news not once, but twice.
The first one, when the paper with the momentous development was, somehow,
leaked in September 2019. The second one, about one month later, when the
scientific article was finally published in Nature. And I am not counting what
would be the third one, when IBM released a press note trying to refute
Google’s findings. As you can see, this is not your typical discovery. It
reaches way beyond the academic and scientific environments to capture the
public’s imagination. In fact, it has been compared by Scott Aaronson, one of
the world’s most prominent quantum computing researchers, to that historical
moment of the Wright Brothers’ first flight. It is intriguing, isn’t it? In
this brief note, I will try to explain what that much talked-about quantum
supremacy is, what the researchers at Google have exactly done to achieve it,
why IBM objects to it and, more importantly, why all this has the potential to
become one the most celebrated scientific and technological developments of the
21st century. To that extent, we need to start at the very
beginning, by answering a fundamental question…
What is quantum computing?
The inner workings of
quantum computers are the subject of the (excellent) chapter by Diego
García-Martín that you can find in this very same volume and, in fact, not so
long ago I had the pleasure of writing about the topic for another book2.
However, in order to make this article as self-contained as possible, I will
take the liberty of mentioning some of the facts that I will be referring to
later on.
In my opinion, the most important thing to understand is that a quantum
computer is not just a faster
computer. In fact, it is not even true that quantum computers are faster than
classical computers at every task (and they may be slower at some!). Then, why
all the fuss about quantum computing? What makes quantum computers so special
is that they can take advantage of some weird properties of subatomic particles
(such as superposition, interference and entanglement) to approach certain
problems in a different way, one that
classical computers cannot use. This makes it possible to develop quantum
algorithms that solve some problems in much less time than any classical
algorithm we have found3.
The most prominent example of such a quantum algorithm is due to Peter
Shor, who in 1994 discovered a way to quickly factor numbers with the help of a
quantum computer. Finding the prime factors of an integer may seem like a
child’s play, and it indeed is, at least if the number in question is 15, 21,
49 or any other small enough number. But what about, for instance,
3442236437844890848962691120256523872456444051997010354874932020517692086113259539755530138240613932133436429030725281214457504205876121500455522122021956828989679539799089428606069211781714466580121376966304852290646741335767985832244563863256968923004470022322683044576929476947120638879022104852435535246204194655452192106910647827239222132389476473637854580838107932559200658278001280804572498177?
Not so easy, right4? It turns out that the best classical algorithm
for this kind of problem that we know of would take an inordinate amount of
time if the input was a number of, lets say, 1000 digits. This difficulty is,
in fact, the basis of some widely used cryptographic protocols such as the
famous RSA method. But Shor’s algorithm shows that, with a quantum computer,
factoring such a number and, consequently, breaking most of the Internet’s
security would be much, much easier.
What is, then, quantum supremacy?
Proving mathematically that
a quantum computer can achieve feats such as factoring a very long number is
one thing; running Shor’s algorithm in an actual
quantum computer is a very different one. The technological challenge of
building a big enough quantum computer has proven to be one of the most
difficult ones that we, as a species, have ever faced. However, the last few
years have seem some remarkable improvements and developments in the techniques
needed to build general-purpose quantum computers and some devices have jumped
from lab prototypes to actual, albeit limited, devices that can even be used
for free on the Internet. This led John Preskill, in 2012, to define quantum supremacy as that moment in
which a real quantum computer “clearly beats” the most powerful classical
computer at some task. Note that this task needs not be useful. It only has to
be something that the quantum computer solves much faster than any existing
classical computer. Eventually, several research groups accepted, in some way
or another, this challenge, among them Google’s Quantum AI Lab, directed by
John Martinis. This team would, some years later, rock the world by announcing
their success.
How has Google achieved quantum supremacy?
It would be natural to think
that a perfect candidate for a quantum supremacy experiment would be finding
the factors of a big number. We know of no algorithm that can efficiently solve
the problem in a classical computer (and we strongly suspect that there is no
such a method), but we could use Shor’s algorithm to find the factors on a
quantum computer and, later, check that they are correct in any desktop PC
(multiplication is, of course,
efficient on classical computers).The problem is that using Shor’s algorithm
with a big integer requires a quantum computer much bigger and accurate than
any we have been able to build so far. One of the most important parameters in
a quantum computer’s architecture is the number of qubits (somehow equivalent
to the RAM of a conventional computer). Sycamore, the quantum processor that
Google used to achieve quantum supremacy, has 54 (of which 53 are usable). It
has been estimated that to factor a number that is beyond the capabilities of
current classical computers, several million
qubits would be needed.
Google's Sycamore quantum processor. (Credits: Erik Lucero, Google).
However, there is a straightforward task that is easy for quantum
computers but seems to be very hard for classical algorithms: executing quantum circuits. These circuits are the
analog of programs from classical
computers. So, essentially, what a quantum computer does is just executing
quantum circuits5. Classical computers can also execute (simulate would probably be a more
accurate term) these circuits, but the needed time grows exponentially with the
number of qubits. This means that simulating a 100 qubit quantum circuit with a
classical computer may take longer than the time that has passed since the Big
Bang. What Martinis’ team did was to generate random quantum circuits of 53
qubits, run them of their quantum processor and sample from the results. This
took their computer about 300 seconds. They estimated that doing something
similar with the fastest classical computer available would take 10,000 years.
Quantum supremacy achieved!
Or not?
As I’ve mentioned in the
introduction, some researchers at IBM have objected to Google’s announcement.
Their argument is that Google has not considered all the possibilities. To make
a long story short, there exists an algorithm for simulating quantum circuits
that uses a lot of memory. A lot. So
much, that no existing computer today has enough RAM to run it for 53 qubit
circuits. Thus, Google made their estimations considering another algorithm
that is slower but uses much less memory. Hence the 10,000 years. IBM argues
that you could still run the faster simulation algorithm if you used not only
RAM, but also hard disks for storaging the data needed in the computation. With
this approach, they estimate that the running time for simulation Google’s
circuits would be just two and a half
days.
So… who is right after all?
Quantum supremacy is loosely
defined. It does not set a clear milestone, and the goal could change if new
algorithms are discovered or with new hardware breakthroughs. But, measure it
as you will, Google’s achievement is extremely remarkable. 300 seconds is
certainly much less than two and half days and even IBM concedes that with a
few more qubits their approach would be unfeasible. Even better. What John
Martinis’ team has achieved, this quantum supremacy, is just the beginning of a
new era in which quantum computers may help us reach higher and higher peaks.
The era of quantum computing. Carl Sagan would most surely be very proud!
Notas:
1 The term “quantum
supremacy”, because of its political implications, has been considered
inadequate by some quantum computing researchers. Several alternatives have
been suggested, including “quantum advantange”, but as has been pointed out by
John Preskill, this new term fails to capture the real difference between
quantum and classical computers. For this reason, and because of the widespread
used of “supremacy”, I have decided to use it in this text.
2 “Y un gran paso para la humanidad”, edited by Ana Casalvilla Dueñas and
Quintín Garrido, that you can download free from:
3 And we have good reasons to
think that it is not because we have not tried hard enough, but because it is
indeed impossible to find fast classical algorithms for those problems.
4 Its factors are, by the
way,
38446987513619644955815324662957851615740204558929741701011236593747201243473865651109495096257976848140931686246832118997178441313186890031551687408532105122099332172678260860632442477936678431268763
and
89532019553560510572280382084216577436370480412820899579066689247911167282144485321539000856903001904683556540913581333554678296618564366005378732821281475596193803322477850929715108931267459260799379.
5 Other quantum computing
paradigms exist, but the most popular is the quantum circuit one.
Bibliography:
(1) Arute, F., Arya, K., Babbush, R. et al., 2019, Quantum supremacy using a programmable superconducting processor. Nature 574, 505–510
https://doi.org/10.1038/s41586-019-1666-5
(2) Pednault E., Gunnels J., Maslov D., Gambetta J., 2019, On “Quantum Supremacy”, IBM Research blog, https://www.ibm.com/blogs/research/2019/10/on-quantum-supremacy/
(3) Preskill, J., 2019, Why I
Called It ‘Quantum Supremacy’, Quanta Magazine, https://www.quantamagazine.org/john-preskill-explains-quantum-supremacy-20191002/
Elías
Fernández-Combarro Álvarez.
MSc in Mathematics. Bachelor in Computer Science. PhD in Mathematics.
Associate Professor - Computer Science Department – University of Oviedo
(Spain).
No hay comentarios:
Publicar un comentario