A paper published — and then removed — from NASA’s website claims that Google has established so-called quantum supremacy. If true, it would be a significant achievement for quantum computing as a whole. The impact on the general-purpose world of computing from this specific breakthrough is minimal, but it’s an important milestone towards the practical, real-world use of quantum computing.
First, let’s talk about the paper itself. A number of news outlets have led with headlines like “Google Announces Quantum Supremacy” or “Google Claims Quantum Supremacy,” implying that the company has made a major PR effort around this issue. This is not true. Various publications obtained a copy of a paper posted on NASA’s website claiming that Google had achieved quantum supremacy before the paper was taken down. Google has not commented publicly on this situation or made any statements other than those that were contained within the paper, which may have been a draft document. SpaceRef has posted a cached version of the document, complete with original formatting errors and typos.
What Is Quantum Supremacy?
The entire reason scientists and engineers are racing to develop quantum computers is that quantum computers can be used to solve certain types of problems that are unsolvable using classical computing. The computers we use today, from a smartphone to a TOP500 supercomputer deployment, are all classical computers.
We will achieve quantum supremacy (or have achieved it, if Google’s paper is accurate) when it can be demonstrated that a quantum computer has solved a problem that is practically impossible to solve on a classical system. Demonstrating quantum supremacy requires a sufficient number of qubits, which is why Google, IBM, Intel, and other companies have been working hard on building larger systems. Quantum systems are extremely susceptible to noise (quantum error correction is an area of active research).
Google’s paper states:
Here, we report using a processor with programmable superconducting qubits to create quantum states on 53 qubits, occupying a state space 253 ˘1016. Measurements from repeated experiments sample the corresponding probability distribution, which we verify using classical simulations. While our processor takes about 200 seconds to sample one instance of the quantum circuit 1 million times, a state-of-the-art supercomputer would require approximately 10,000 years to perform the equivalent task.
This is the claim of quantum supremacy that’s being hailed as a breakthrough. Google notes that even this breakthrough still has real limitations — while it shows that quantum speedups are possible in real-world tests, there’s still additional work required to engineer fault-tolerant qubits in order to tackle problems like Shor’s algorithm.
In order to achieve its breakthrough, Google sampled the output of a pseudo-random circuit. The chip they used to achieve this, codenamed Sycamore, was a two-dimensional array of 54 transmon qubits. Each transmon is tunably coupled to its four nearest neighbors in a rectangular lattice. Google writes, “We have performed random quantum circuit sampling in polynomial time with a physically realized quantum processor (with sufficiently low error rates), yet no efficient method is known to exist for classical computing machinery.”
The big question is why NASA removed the whitepaper. Hopefully, we’ll have more information on that point in the near future.