Google’s Potential Claim to the Throne of Quantum Supremacy: What Does it Mean for Cybersecurity?

By Roberta Faux, Shamik Kacker, Bruno Huttner, John Hooks, Ron F. del Rosario, Ludovic Perret and John Young

A mysterious paper

A research paper titled “Quantum Supremacy Using a Programmable Superconducting Processor” briefly appeared last September 21, 2019 on NASA’s Technical Report Server (TRS), but was later removed.

In the paper, researchers from Google AI Quantum Labs claimed supremacy in quantum computing by successfully running a series of ground-breaking experiments utilizing a processor with programmable superconducting qubits and completing an experiment within 200 seconds that normally would take a modern, state-of-the-art supercomputer approximately 10,000 years to complete.

Various research and scientific community websites were able to obtain a copy of the document prior to its removal. Therefore, this document has been the subject of much debate, scrutiny and speculation for the past few weeks. It is very likely that the paper is currently under peer review and shall be available soon.

Whether it was a PR stunt to attract interest (it worked!) or an honest mistake, it is now official: Google published on October 23, the results of their quantum supremacy experiment in the Nature article Quantum supremacy using a programmable superconducting processor.

What is Quantum Supremacy?

Coined by John Preskill back in 2012, “Quantum Supremacy” describes the point where quantum computers can do things that classical computers can’t, regardless of whether those tasks are useful. John is a Theoretical Physicist and Director of The Institute for Quantum Information and Matter (IQIM) at Caltech.

In the paper, Google AI Quantum Labs researchers claimed they were able to achieve this status in quantum computing through their experiments utilizing a physical quantum processor with sufficiently low error rates:

“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. As a result of these developments, quantum computing is transitioning from a research topic to a technology that unlocks new computational capabilities. We are only one creative algorithm away from valuable near-term applications.”

Note however, that some naysayers doubt this claim. The mathematician, Gil Kalai fully expects that "quantum supremacy cannot be achieved at all". While accepting the importance of this work, Kalai argues that Google made a crucial mistake in their supremacy claims. IBM, who is also one of the main contenders in the quantum race and has built its own 53-qubit machine, was not slow to react as well. The IBM team published a counter-argument to Google’s estimates, arguing that the calculation could be simulated in just 2.5 days on available supercomputers, not the 10,000 years which Google reported. Whether Google has demonstrated “quantum supremacy” or is merely on the verge of “quantum supremacy,” this feat should be noted as a milestone.

Potential impact on current cryptographic systems

According to John Preskill, the experiment is a sort of “demonstration” at this early stage that Google researchers understand their quantum computing hardware and the next big step is to look for more practical applications in general computing.

Researchers also stated that the next focus should be on engineering quantum error correction technology in order to tackle problems with immediate implications to current computing paradigms such as Shor’s Algorithm.

Published back in 1995 by AT&T Labs Researcher Peter Shor in his paper “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, the so-called Shor’s Algorithm is a quantum algorithm that causes an exponential speed-up when solving factoring, discrete logarithm (DLP), and elliptic curve discrete logarithm (ECDLP) problems. Modern public key cryptography, which underpins secure communication and e-commerce on the internet, relies on the difficulty of solving these problems with our current classical computing paradigm. Therefore, a fully-realized quantum computer running Shor’s algorithm will easily circumvent our current cryptographic infrastructure. Note that Shor’s algorithm is not the only quantum algorithm attacking cybersecurity. Grover’s algorithms can compromise our symmetric cryptography (e.g. AES). However, as it only results in a quadratic speed-up, increasing the AES key size can provide adequate resistance against Grover’s quantum attack.

Does it mean that Google’s experiment means doom for cybersecurity today? Not quite. As expressed above, the first caveat is about quantum error correction technology. A brief technical aside is required here to explain what we are writing about.

Today, all quantum processors utilize physical qubits, which can be in a coherent superposition of zero and one. With this type of qubits, every operation introduces some error, basically reducing the quality of the qubit. This limits the total number of operations, which can be performed before you “lose” your qubits, or decohere. In order to go further and perform longer computations, we need to move to logical qubits. A logical qubit is built from a large number of physical qubits, which protect it and enable error-free computations. This is the field of quantum error correction technology. Note that a classical computer, which runs on classical bits (zeros and ones), runs naturally on logical bits. In order to run Shor’s algorithm, a quantum computer has to implement logical qubits. Now back to our development...

Google’s system is using physical qubits, with a sufficiently low error rate. This was apparently enough to demonstrate quantum supremacy. However, it will probably be a good number of years before a quantum computer can run long enough computations with logical qubits. The current estimates are between 5 to +10 years.

The second caveat is that, although current cybersecurity infrastructure relies on potentially unsafe cryptographic protocols, new developments are currently underway to address this issue. This is the task of quantum-safe cryptography.

Can we counter the quantum threat?

The fact that we still have a few years before quantum supremacy transforms into a real threat to cybersecurity should not lure us into a false sense of security. We can already record data today and decrypt it once a powerful enough quantum computer is available. Information exchanged today, which may still have value in several years, is already at threat. Even adapting our infrastructure to the threat will take several years.

According to the October 2019 research “Quantum Threat Timeline” conducted by the Global Risk Institute, the transition to quantum-safe cryptography is a challenge itself, as it requires the development and deployment of hardware and software solutions, the establishment of standards, the migration of legacy systems, and more.”

Fortunately, things are already moving. Post-Quantum or Quantum-safe algorithms are actively being developed to specifically address this looming threat of quantum computing in the security of modern communication systems. The NIST in the USA has launched a competition, wherein groups of researchers around the world propose post-quantum algorithms for different cryptographic purposes. The goal is to converge to a few of them, which will become standards between 2022 and 2024.

In an interesting twist, new solutions, such as Quantum Random Number Generators and Quantum Key Distribution, based on the same quantum effects, can already be deployed today to offer quantum-safe communications.

Within the Cloud Security Alliance (CSA), the Quantum-Safe Security (QSS) working group is a forum where companies and academic institutions meet to discuss these issues, and suggest solutions. It has written a number of white papers, which address most of the above topics in a non-technical format. The latest report discusses how to prepare enterprises for the quantum threat.

You can view and download all the white papers on this topic here: https://cloudsecurityalliance.org/research/working-groups/quantum-safe-security