Factoring integers with sublinear resources on a superconducting quantum processor
Can Quantum Technologies Crack RSA Encryption as China Researchers Claim?
Scientists in China claim they have found a way for current-generation quantum computers to crack the RSA algorithm underlying the most common form of online encryption. The researchers said the encryption could be broken with a 372-quantum-bit (qubit) system using hybrid quantum-classical methods to overcome scaling limitations. The Chinese paper “Factoring integers with sublinear resources on a superconducting quantum processor” stated that the algorithm used factored a number with 48 bits on a quantum system with 10 qubits.
The likelihood that quantum computers would be able to crack online encryption was widely believed a danger that could lie a decade or more in the future. But the 24 researchers, from a number of China’s top universities and government-backed laboratories, said their research showed it could be possible using quantum technology that is already available. The quantum bits, or qubits, used in today’s machines are highly unstable and only hold their quantum states for extremely short periods, creating “noise.”
As a result, “errors accumulate in the computer and after around 100 operations there are so many errors the computation fails,” said Steve Brierley, chief executive of quantum software company Riverlane. That has led to a search for more stable qubits as well as error-correction techniques to overcome the “noise,” pushing back the date when quantum computers are likely to reach their full potential by many years. The Chinese claim, by contrast, appeared to be an endorsement of today’s “noisy” systems, while also prompting a flurry of concern in the cyber security world over a potentially imminent threat to online security.
By late last week, a number of researchers at the intersection of advanced mathematics and quantum mechanics had thrown cold water on the Chinese claim:
- Massachusetts Institute of Technology’s Peter Shor pointed out that the team had “failed to address how fast the algorithm will run,” as it could “still take millions of years.” Shor, the American mathematician who first proposed a way for quantum computers to crack encryption, predicted that the inability to run all the computations at once meant it would take “millions of years” for a quantum computer to run the calculation proposed in the paper. The Chinese research comes at a time when many companies working on the technology are in a race to prove that today’s “noisy” systems can reach so-called quantum advantage — the point at which a quantum computer can perform a useful task more efficiently than a traditional, or “classical”, machine, ushering in commercial use of the technology.
- Brierley at Riverlane said it “can’t possibly work” because the Chinese researchers had assumed that a quantum computer would be able to simply run a vast number of computations simultaneously, rather than trying to gain an advantage through applying the system’s quantum properties.
- Four years ago, John Preskill, a professor of theoretical physics at the California Institute of Technology, predicted that quantum systems would start to outperform and might have commercial uses once they reached 50-100 qubits in size. But that moment has come and gone without quantum systems showing any clear superiority. IBM unveiled a 127-qubit computer more than a year ago, and last month announced that a new 433-qubit processor would be available in the first quarter of 2023. These days, Preskill sounds more cautious. “I expect that for practical applications with significant business value we’ll have to wait for error-corrected fault-tolerant quantum computers,” he said, adding that this was likely to be “a ways off.” But he added that today’s systems already had scientific value. One reason that hopes have retreated is that new ways have been found to program classical computers to handle tasks that were once thought to be beyond them.
This has pushed back the quantum frontier, delaying the moment when people building quantum systems can claim an advantage, said Oskar Painter, head of quantum hardware in the cloud computing division at Amazon, one of the tech companies that is building its own quantum computer. “They never finally could say, ‘This will be better,’” he said. After years of rising expectations, the lack of practical uses for the technology has led some experts to warn of a potential “quantum winter” — a period when disappointment about a new technology leads to a waning of interest for a number of years. The term is borrowed from the AI “winters” of the 1970s and 1980s, when a number of promising research avenues turned out to be dead ends, setting the field back for prolonged periods.
“People are worried it will be really harsh,” said Painter at Amazon Web Services. Like many in the field, though, he said that any short-term backlash was unlikely to hit long-term research funding. “I don’t think it will go away.” Receding hopes for early benefits from quantum computing have already contributed to a sharp fall in the stocks of a handful of companies that rode the wave of enthusiasm over the sector to go public since the middle of 2021. Based on their peak share prices soon after they each went public, Arquit, IonQ, D-Wave and Rigetti reached a combined value of $12.5bn. That has since fallen to $1.4bn.
Among the events to batter the quantum companies last year, IonQ was hit by a report from a short seller claiming its technology did not live up to its claims, while Rigetti founder Chad Rigetti was removed as chief executive before quitting the company late in the year.
Part of the problem facing the sector has been an excess of “hype” about the technology, said Constantin Gonciulea, chief technology officer of advanced technology at Wells Fargo. He compared the build-up of expectations around quantum to the crypto industry, as many non-experts have been drawn into the field and promises for the technology have far outgrown its potential in the near term. Despite this, companies working on the first quantum machines and software still insist that practical uses of the technology are just around the corner — while continuing to carefully avoid giving too precise a prediction about exactly when that will be.
David Rivas, head of engineering and product at Rigetti, said that the company still believed it would reach quantum advantage when its computers have “a few hundred to a few thousand qubits.” Even if they cannot match the performance of today’s supercomputers, they will still be useful if they cost much less, or if they can operate faster or with more precision, he said. For some quantum companies, the startling Chinese claim about online encryption was a sign that the technology’s big moment is drawing nearer. But for the doubters, the apparent impracticality of the research will serve as confirmation that quantum computing is still an impressive science experiment rather than a practical technology.
Quantum Technologies Update: U.S. vs China now and in the future
AT&T will be “quantum ready” by the year 2025; New fiber network launched in Indiana
New ITU-T SG13 Recommendations related to IMT 2020 and Quantum Key Distribution