For years, scientists have been battling to build a computer that exploits one of the strangest areas of modern science—quantum physics.
Now Google claims to have achieved a breakthrough by using quantum techniques to perform a mathematical task over a billion times faster than the world’s most powerful existing supercomputer.
“This is a tremendous milestone and a hallmark of computer science history if true”
The discovery could force a fundamental rethink of the mathematical coding techniques that underlie cryptocurrencies and internet-based commerce.
“This is a tremendous milestone and a hallmark of computer science history if true. It is, I would dare say, one of the greatest achievements in the history of humankind,” said Dionysis Zindros, a cryptographer at the University of Athens.
How quantum computing works
Classical computing relies on the communication of information in a stream of binary digits, or ‘bits’, for short. As their name suggests, bits can exist in one of two binary states—zero or one.
By contrast, quantum computing relies on the strange properties of sub-atomic particles, as set out in quantum mechanics, a branch of physics discovered in the early 20th century.
In quantum computing, rather than representing a choice between zero and one, particles can represent quantum bits, or ‘qubits’. A qubit could take on the value zero, one, both, or neither, simultaneously.
Another quantum phenomenon called entanglement allows qubits to influence other qubits at a distance.
In aggregate, these properties could create computers with massively more processing power than traditional binary systems.
But that’s in theory. Since they rely on the behaviour of sub-atomic particles, quantum computers are notoriously difficult to build and operate, since the slightest interference or imprecision can affect the results of the computation being performed.
What’s Google claiming?
But now there appears to have been a breakthrough in this area.
As if befitting the subject, Google’s quantum computing claims appeared, mysteriously, in a research paper on the NASA website, then disappeared. However, cached copies of the paper are available.
Google has so far refused to comment on the topic.
The paper cites John Martinis of the University of California, Santa Barbara, who is known to have partnered with Google to build the hardware for a quantum computer.
“This heralds the advent of a much-anticipated computing paradigm”
The paper describes how the quantum processor tackled a random sampling problem: checking if a set of numbers has a truly random distribution. This task is very difficult for a traditional computer if there are a lot of numbers involved.
However, the quantum processor achieved the task over a billion times faster, according to the paper.
“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,” the paper claimed.
“This dramatic speedup relative to all known classical algorithms provides an experimental realization of quantum supremacy on a computational task and heralds the advent of a much-anticipated computing paradigm,” Martinis said.
Google’s rivals respond
Google’s rivals in the race to build a quantum computer offered contrasting reactions to the reported discovery.
IBM, which has a large quantum computing research unit, was dismissive of the scope of Google’s claims.
This is “a laboratory experiment designed to…implement one very specific quantum sampling procedure with no practical applications,” said Dario Gil, head of research at the firm, quoted in the Financial Times.
The director of quantum hardware at Intel, James Clarke, was cautiously positive, however.
“Google’s recent update on the achievement of quantum supremacy is a notable mile marker as we continue to advance the potential of quantum computing,” he said.
Implications for cryptocurrencies and internet commerce
Could quantum computers help unravel the cryptographic algorithms used by cryptocurrencies like bitcoin?
Bitcoin, for example, relies on a mathematical scrambling scheme involving elliptic curves. This scheme creates so-called ‘one-way’ functions that are difficult to undo.
In theory, quantum computers could be used to crack such algorithms, rendering the associated cryptocurrencies worthless.
Some researchers have already called for the ‘quantum-proofing’ of encryption algorithms to ensure that they cannot be undone by much more powerful computers.
However, according to Dhruv Bansal, a theoretical physicist, there is still some way to go before quantum computing represents a real threat to bitcoin in particular.
“E-commerce and credit cards will be hacked by quantum computing long before bitcoin”
“It’s clear that Google is on the path to breaking certain kinds of cryptography. We all knew this would happen eventually, I guess Google is just letting us know that it’s happening now,” Bansal told New Money Review.
“But systems like bitcoin are actually better protected than most as they use a combination of different cryptographic techniques, some of which are breakable by quantum computing (elliptic curve digital signatures) and others which aren’t (hashing),” he continued.
“In particular, those who re-use bitcoin addresses lose one of these protections, leaving them vulnerable to attack by quantum computers,” said Bansal. “But eventually, even bitcoin will have to adapt in some ways to this development.”
A bitcoin ‘address’ is generated from a user’s public key by an irreversible mathematical function, and using a separate address for each bitcoin transaction is considered an important privacy safeguard.
But it’s internet commerce in general that is more at threat from the reported advances in quantum computing, said Bansal.
“Most secure services use some form of public-key cryptography and most forms of public key cryptography are vulnerable to attack by quantum computing,” said Bansal.
“Basic services such as e-commerce and credit cards will be hacked with quantum computing long before bitcoin is,” he said.
Another commentator, however, saw Google’s recent advance as a cause for pessimism about bitcoin.
“I take this as a very important breakthrough in quantum computing,” said Jin Liu, chairman of the ABCMint Foundation, which specialises in developing quantum-resistant cryptocurrencies.
“I’m not sure how soon it will be powerful enough to crack bitcoin, but definitely it will influence the bitcoin price very soon,” said Liu.
——–
Postscript (29 September)
According to Scott Aaronson, a professor of computer science at the University of Texas, quantum computing still has a way to go before it represents a real threat to existing code systems.
“The devices currently being built by Google, IBM, and others have 50-100 qubits and no error correction,” Aaronson wrote on his blog last week.
Error correction is especially important in quantum computers because they are more prone than traditional computers to various forms of interference.
“To break the RSA cryptosystem would require several thousand logical qubits,” Aaronson said.
“With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today. I don’t think anyone is close to that, and we have no idea how long it will take.”
However, added Aaronson, if anyone does manage to build such a quantum computer, it will undo the internet’s current security protocols.
“By an unfortunate coincidence, the public-key codes that [quantum computers] can crack include most of what we currently use to secure the internet: RSA, Diffie-Hellman and elliptic curve cryptography,” wrote Aaronson.
Public key cryptography, developed by Rivest, Shamir, Adleman (RSA), Diffie, Hellman and Merkle in the 1970s, gave the world a radical new tool to ensure privacy in communication. It underlies the most important internet communications protocols, including those used for online commerce.
——–
Don’t miss any more New Money Review content: sign up here for our newsletter
Support New Money Review on Patreon or in cryptocurrency
