by Joel Hruska
Last month, the quantum computing world lit up with the news that Google might have achieved quantum supremacy. A draft version of a paper surfaced on NASA’s website claiming this but was quickly yanked offline. Now, the final version of the same paper has run in Nature, making a formal claim to what had previously been implied by the quick appearance and disappearance of the draft. Google argues that it has achieved so-called quantum supremacy by demonstrating a quantum computer capable of solving a problem no classical computer could compute in a reasonable amount of time.
Is this the moment that quantum supremacy is absolutely without question achieved? According to IBM, no. Here’s what’s going on.
Achieving Quantum Supremacy
To achieve quantum supremacy, Google needs to demonstrate that a quantum computer has performed a series of operations at speeds that classical computers are literally incapable of achieving. There are problems that a modern classical computer couldn’t finish solving using the best-known methods of today before the heat death of the universe.
Scientists, however, have an annoying tendency of finding faster ways to compute workloads by improving the underlying algorithms used to do so. Writing maximally efficient algorithms is an incredibly complex topic, touching on everything from the capabilities of the hardware platform to the language and compiler used to generate the underlying code. Finding new shortcuts and more efficient methods of solving problems is a major way we’ve improved the speed of analyzing complex data in HPC classical computing, over and above the impact of Moore’s Law and other hardware improvements.
Just a few days ago, before Google’s paper was formally published in Nature, IBM put out a paper claiming there’s a way to execute Google’s chosen workload on a classical machine. Google claims that they’ve achieved quantum supremacy because the company’s “Sycamore processor takes about 200 seconds to sample one instance of a quantum circuit a million times-our benchmarks currently indicate that the equivalent task for a state-of-the-art classical supercomputer would take approximately 10,000 years.”
And here’s IBM:
As we argued in that paper, secondary storage can extend the computational reach of supercomputers for the simulation of quantum circuits… We estimate that on the Summit supercomputer at Oak Ridge National Laboratories, secondary storage allows the simulation of 53- and 54-qubit Sycamore circuits with high fidelity to arbitrary depth… In particular, for 20 cycles of the entanglement pattern ABCDCDAB, which is specifically designed to challenge classical simulation algorithms, we estimate that the computations would take approximately two and a half days.
Google is saying that it achieved quantum supremacy by performing a calculation that cannot be performed on a classical system in a reasonable amount of time. IBM is attempting to short-circuit Google’s ability to claim the quantum supremacy crown by arguing that no, Google didn’t actually achieve quantum supremacy because IBM estimates it could extend a supercomputer in particular ways that allowed it to complete the same computation in 2.5 days.
This is a weak refutation on IBM’s part. For one thing, Google is describing something it has done, while IBM is describing something it has theorized could be done. For another, standing up a quantum computer and saying “We’ve found a way to perform a task vastly more quickly than a classical computer does today,” is still relevant to the larger scope of quantum research and improvement. If the work being done in quantum computing spurs work that leads to more efficient classical computing algorithms, that’s a win-win as far as software development is concerned.
It may be easier to understand the relationship between quantum and classical computing by referring to the very early days of digital computing. While digital computers eventually outstripped analog computers, the earliest digital machines were electro-mechanical, relay-based systems that were much slower than the analog computers of the day. There were some significant digital-analog computer hybrids that took advantage of the best features of both worlds before digital computers completely took over the manufacturing landscape.
If you think about it from this perspective, “digital supremacy” was not a single event. Analog computers improved over the decades they were in use, just as digital computers did, and the best analog systems of say, 1960 were faster and more capable than the best analog computer of 1920. Digital machines improved faster, however, and were capable of addressing a much wider array of problems. Digital computers replaced analog systems over time.
One important distinction between quantum and classical computing as compared with digital versus analog is that no one expects quantum computers to ever replace classical machines. Quantum computers require liquid nitrogen to operate and there’s no way to duplicate that kind of cooling setup in a box you’d put under your desk or drop in a pocket. We’re not looking at the same kind of long-term replacement cycle, in this case, but we should expect that as both quantum and classical computers continue to evolve, classical computers will continue to be capable of addressing tests that they once could not calculate efficiently. Quantum computers, however, will grow their capabilities in these tests in a fundamentally different way.
Quantum computing expert Scott Aaronson makes this point in his blog, writing:
With a 53-qubit chip, it’s perfectly feasible to see a speedup by a factor of many millions, in a regime where you can still directly verify the outputs, and also to see that the speedup is growing exponentially with the number of qubits, exactly as asymptotic analysis would predict.
In other words, even if there’s a clever speedup that can make this specific solution simulatable on a classical computer, the rapid growth in the number of qubits in a universal quantum computer will soon prevent such solutions from working at all. As the number of available qubits increases, the number of problems quantum computing can address also increases.
So. Has Google absolutely achieved quantum supremacy? It looks that way for now, though a lot of very sharp-eyed people are going to be dissecting this paper in the days and weeks to come. But while IBM is trying to argue that they haven’t, I don’t see many scientists echoing that claim. For many years, there were real questions about whether it was possible to build a quantum computer at all. Today, researchers are grappling with how to build machines that can perform useful work. Even if Google’s paper were to be retracted, the question of quantum supremacy seems to very much be a matter of “when,” not “if.”
Originally published at https://www.extremetech.com on October 24, 2019.