An historic claim from Google was accidentally (and briefly) posted online: its AI Quantum research group had achieved “quantum supremacy,” an important step towards ultra-powerful computers that can solve problems deemed impossible for current machines by using quantum physics.
The big reveal was somewhat thwarted by contributing researchers at NASA, who accidentally made a draft paper available. Not prone to understating its successes, Google made its bold assertion in the title of its research paper: “Quantum supremacy using a programmable superconducting processor.” Though the paper was quickly taken down, copies of it were archived and are floating around the web.
Google didn’t respond to a request for comment about how the paper was leaked, or when a finalized version would be published.
The news that Google had reached this milestone has got people talking, or rather, arguing about what this really means. Still, even in the fundamentally confusing world of quantum physics, there are some facts that we can untangle from the speculations, opinions, and predictions.
Here’s what we do know about Google’s claim to quantum supremacy.
What is ‘quantum supremacy’?
Quantum supremacy is the point at which quantum computers can solve problems that are practically unsolvable for “classical” (non-quantum) computers to complete in any reasonable timeframe.
In principle, even the most simple universal computer can solve anything that is computable (i.e. can be represented as a formal problem for which there is an answer, or set of possible answers) given infinite time to do so. So, “supremacy” is a matter of how quickly and reliably a computer can solve a problem.
“The purpose is to show that you've built a quantum device that can do at least one thing which is outside the reach of classical machines,” said David Gosset, an associate professor at the Institute of Quantum Computing at the University of Waterloo.
It is generally believed that at least 49 qubits are required to cross the quantum supremacy line. Qubits behave very differently to bits in classical computers. Bits represent either a “1” or a “0,” and computers read and perform operations on one bit at a time. In contrast, qubits can represent a combination state made up of both “1” and “0,” due to the peculiar quantum effects in which properties like particle position, direction, and momentum are not well-defined. This allows for a system to be in multiple states at the same time, called quantum indeterminacy.
Quantum computers can use quantum operators (a mathematical transformation) on all possible values within a qubit state, so it can read and change a “1” and a “0” piece of information at the same time. The ability to instantly process more information and simultaneously act on that information is what enables quantum computers to perform extremely complex tasks much faster than classical computers.
What did Google do?
Before the inadvertent announcement about supremacy, Google was already leading the pack in terms of the sheer size of its quantum computer. Last year it revealed a new 73-qubit computer, putting it ahead of closest rival IBM, which happened to announce its own development of a 53-qubit computer on September 18.
For its supremacy demonstration, however, Google used a different, smaller computer, named Sycamore.
As described in the leaked paper, Google used a 53-qubit processor (originally 54 qubits, but one qubit let the team down) to perform a sampling task. First, a classical computer was used to generate a series of quantum instructions called quantum gates, the equivalent of logic gates which act on the 1s and 0s in classical computers. This series, collectively called a quantum circuit, was sent to the quantum computer to perform only on qubits in pure zero states, generating a probability distribution for resulting states. (This is a function that assigns probabilities to all possible values, because of the indeterminacy features of quantum physics.) Finally, the quantum computer was asked to output samples from the probability distribution.
To check that the quantum computer actually performed this task, the team had to use a classical computer as a “simulator” to verify that samples of the quantum computer’s output are close to the expected values.
The classical simulator uses mathematical techniques to generate a similar probability distribution function to compare with the quantum computer, but it doesn’t actually execute the same operations—this would undermine the demonstration of quantum supremacy. The simulation takes a huge amount of resource and time, increasing with the size of the quantum computer it is checking. Using classical computers to verify quantum supremacy is only possible when quantum computers are around 50 qubits or less.
It looks like Sycamore did complete this job pretty quickly, within the allowed error thresholds. In a shorter summary paper which also appeared online, Google’s researchers estimate it would take the most advanced classical computer today 10,000 years to do sampling that the quantum computer did in 200 seconds.
This doesn’t rule out the possibility that there is a very efficient algorithm which could enable a classical computer to do the same task in a reasonable timeframe. Currently, no one has proven mathematically that such an algorithm does not exist, but there are weaker proofs that make it unlikely that a yet-undiscovered super-fast classical algorithm exists.
How important is this result?
In response to the leaked announcement, presidential candidate Andrew Yang declared that it meant “no code is uncrackable.” He was roundly roasted.
See, a major concern about quantum computing in general is that our current security and encryption protocols will no longer be safe from ultra-fast and powerful machines. But the fact that Sycamore can perform one specific task that people believe would take too long for a classical computer, does not mean it can perform the tasks it would need to in order to crack important security protocols.
In a blog post responding to frequently-asked questions about the Google news, Scott Aaronson, a quantum professor at The University of Texas (Austin), explained why.
According to Aaronson, current RSA encryption can only be broken by “several thousand logical qubits.” Current quantum computers have fewer than 100 qubits at most, and Sycamore had even fewer. Canadian company D-Wave’s machines use more, but using an entirely different approach without quantum gates.
Logical qubits are higher-level (more abstract) qubits which aren’t affected by quantum decoherence, the messy quantum interactions which produce noise and create errors. A single logical qubit is constructed from hundreds, if not thousands, of physical qubits in such a way that errors due to decoherence at a physical qubit level are cancelled out.
This means that millions of “high quality” physical qubits are needed to produce the thousands of logical qubits which would be able to crack today’s common encryption methods, according to Aaronson’s blog. And that’s a long way off—Sycamore used 53 physical qubits.
Regardless, almost everyone agrees that Google’s results are important in terms of scientific and engineering advancement. Putting claims of supremacy aside, the key innovation is Google’s superconducting processor is programmable, so it can receive instructions for different tasks, some of which may be beyond the reach of classical computers.
Still, some healthy skepticism remains. Confirming caims of quantum supremacy is notoriously hard, since the methods to verify quantum results are not always convincing. In Google’s case, the validation involved comparing the quantum output samples to an “ideal” output, generated by a classical computer.
“Such a demonstration [of quantum supremacy] isn't inherently useful, since most proposals for quantum supremacy are based on computational problems you wouldn't encounter in any other context,” Gosset said. “But it puts a stake in the ground and makes a bold claim that our community will need to scrutinize, once the full details are available.”
Some academics are already questioning the experiment’s methodology. Gil Kalai, a mathematics professor at the Hebrew University of Jerusalem, pointed out in a blog post that Google’s research fails to show that the quantum computer is actually sampling the intended probability distribution and not doing something else entirely to arrive at the output.
A main problem, as he puts it, is that “relying just on the behaviour of qubits and gates” to infer what the quantum computer is doing does not account for errors, called “noise”, which distort the behaviour of quantum computers.
In a paper published in August, he presented concerns about the reliability of the type of quantum supremacy demonstrations Google has now done, writing: “The experimental outcomes will not be robust…and hence the outcomes will be chaotic…running the experiment twice will lead to very different probability distributions.”
Has Google achieved quantum supremacy, as it claims? Right now, the answer is indeterminate.