New Advances Bring the Era of Quantum Computers Closer Than Ever
Kristina Armitage/Quanta Magazine
Introduction
Some 30 years ago, the mathematician Peter Shor took a niche physics project — the dream of building a computer based on the counterintuitive rules of quantum mechanics — and shook the world.
Shor worked out a way for quantum computers to swiftly solve a couple of math problems that classical computers could complete only after many billions of years. Those two math problems happened to be the ones that secured the then-emerging digital world. The trustworthiness of nearly every website, inbox, and bank account rests on the assumption that these two problems are impossible to solve. Shor’s algorithm proved that assumption wrong.
For 30 years, Shor’s algorithm has been a security threat in theory only. Physicists initially estimated that they would need a colossal quantum machine with billions of qubits — the elements used in quantum calculations — to run it. That estimate has come down drastically over the years, falling recently to a million qubits. But it has still always sat comfortably beyond the modest capabilities of existing quantum computers, which typically have just hundreds of qubits.
However, two different groups of researchers have just announced advances that notably reduce the gap between theoretical estimates and real machines. A star-studded team of quantum physicists at the California Institute of Technology went public with a design for a quantum computer that could break encryption with only tens of thousands of qubits and said that it had formed a company to build the machine. And researchers at Google announced that they had developed an implementation of Shor’s algorithm that is ten times as efficient as the best previous method.
Neither company has the hardware to break encryption today. But the results underscore what some quantum physicists had already come to suspect: that powerful quantum computers may be years away, rather than decades. “If you care about privacy or you have secrets, then you better start looking for alternatives,” said Nikolas Breuckmann, a mathematical physicist at the University of Bristol, who did not work on either of the papers.
While the new results may provide a jolt for the policymakers and corporations that guard our digital infrastructure, they also signal the rapid progress that physicists have made toward building machines that will let them more thoroughly explore the quantum world.
“We’re going to actually do this,” said Dolev Bluvstein, a Caltech physicist and CEO of the new company, Oratomic.
Collision Path
Bluvstein and his collaborator Madelyn Cain came to Caltech last summer with a simple question: What is the smallest quantum computer one could imagine building that would have the juice to, say, hack a Bitcoin wallet? Finding the answer would require them and their new colleagues to project where two major trends in quantum computing might collide.
Madelyn Cain (left) and Dolev Bluvstein asked themselves: What is the smallest quantum computer one could imagine creating that could hack something like a Bitcoin wallet?
Mude Gull; Dolev Bluvstein
The first trend was the rise of a flexible new type of qubit: the neutral atom.
Over the last decade, physicists have refined their ability to suspend dozens, hundreds and, more recently, thousands of neutral atoms in laser beams and arrange them as they like. Other qubits, such as the superconducting circuits championed by Google and IBM, operate much more quickly but sit locked in place, like traditional transistors.
Bluvstein and Cain had been working in the lab of the Harvard physicist Mikhail Lukin, where they arranged for 280 neutral atoms to run sophisticated quantum algorithms in 2023. Soon afterward, a group led by Manuel Endres at Caltech set a record when it demonstrated the ability to manipulate 6,100 neutral atoms at once, although it did not perform any calculations with them.
The second quantum trend was an increase in the potency of error correcting codes.
Qubits of any sort are extremely error-prone, and computing with them will require constant vigilance. The gold-standard protocol for error correction is called the surface code. You lay qubits out in a rectangular grid, with each one linked to its neighbor, and use the whole block to store one virtual qubit of information. Then, when some of the real qubits go haywire, the virtual qubit stays protected long enough for you to find and fix the rogue qubits. The surface code is completely reliable and thoroughly understood, but it would take thousands of real qubits to create one reliable virtual qubit. And the virtual qubits are the ones you need to perform an accurate calculation.
Mikhail Lukin’s lab arranged for 280 neutral atoms to run sophisticated quantum algorithms in 2023. From left: Simon Evered, Sophie Li, Alexandra Geim, Mikhail Lukin, Dolev Bluvstein and Markus Greiner.
Ken Richardson for Quanta Magazine
But over the last few years, physicists have found a way to dramatically reduce the number of real qubits they need to create the virtual ones, using quantum “low-density parity-check” (qLDPC) codes. The codes are tricky because they require linking up the real qubits to other real qubits that are far away in the array, as opposed to just their neighbors. But in return, they let you pack many more virtual qubits into an array of a given size. Neutral atoms are a natural fit for these codes, because physicists can freely move one atom across an array to meet a distant atom.
Bluvstein and Cain’s question about the simplest code-cracking quantum computer became a challenge: How far could the Caltech physicists tailor qLPDC codes to the neutral atom technology? They started working with Qian Xu, an expert in those codes; Robert Huang, an expert in quantum theory and machine learning; and Endres, for experimental feedback. John Preskill, a senior theoretical physicist at the university with a long history in the field of quantum error correction, advised the group.
Cooking Up Codes
These funky new qLDPC codes come in many forms, and choosing which one to use typically involves a tradeoff. Some are efficient, in that each virtual qubit doesn’t require many real qubits; others are effective, in that they can withstand many simultaneous errors.
But small tweaks can lead to big changes in performance. Breuckmann, who has done pioneering work on qLDPC codes, likens it to cooking: Sometimes a pinch of just the right ingredient can go a long way. The team knew that the key to a smaller, more powerful quantum computer would be finding a code that balanced both virtues. Xu identified a particularly promising recipe, and Huang set off to perfect it.
Huang and his students recruited a large language model (LLM) designed by mathematicians to help. They gave it a mathematical description of qLDPC codes and set it loose. Eventually it came back with a code efficient enough to make one virtual qubit from just four atoms and effective enough to withstand 20 to 24 catastrophic errors. (By contrast, an earlier high-performing qLDPC code needed 12 real qubits for each virtual qubit and could handle up to 12 catastrophic errors.) The LLM also found an efficient decoder, an algorithm for figuring out what kinds of errors have occurred and devising a plan to correct them.
In 2018, researchers in Paris demonstrated their ability to maneuver neutral atoms by arranging a swarm of atoms in the shape of the Eiffel Tower.
Thierry Lahaye/CNRS
With a superior code and decoder in hand, Cain, Xu, and Huang developed ways to pull off the intricate manipulations of the real qubits required to perform calculations, all while keeping them protected. The team assembled a string of protocols and made its best estimates for how fast it would execute them. Finally, the researchers simulated their design to see how well it would run Shor’s algorithm.
“We put together a lot of things,” Preskill said. “When you do it right, the answer turns out to be surprisingly encouraging.”
The team members simulated different atomic arrays to get a sense of how fast each size could crack the two main encryption schemes, called Rivest–Shamir–Adleman (RSA) and elliptic curve cryptography (ECC). They concluded that they would be able break the common form of RSA in about a century using 10,000 atoms. Using 100,000 atoms, however, it would take only three months. The team found that the easier-to-crack ECC encryption, which is also widely used, would be overcome by an array of 10,000 atoms in about three years, or to 26,000 atoms in a few days.
At the same time the Caltech team was designing its dream machine, researchers at Google led by Craig Gidney were continuing work they had done for years, coming up with ever more efficient ways of executing Shor’s algorithm. In 2019, Gidney and a collaborator detailed a quantum program that could break RSA encryption in eight hours with 20 million qubits. Last year, he came up with a way of doing it with fewer than a million qubits.
In Mikhail Lukin’s lab at Havard, physicists manipulate qubits made of atoms with finely controlled laser beams.
Ken Richardson for Quanta Magazine
In a white paper posted the same day as the Caltech paper, Gidney and his collaborators announced that they had developed a new quantum procedure specifically for breaking ECC that was at least 10 times as efficient than previous procedures. They estimated that most cryptocurrencies would yield in minutes to a machine with fewer than 500,000 qubits.
“That tenfold reduction in the actual space-time cost of elliptic curve code breaking is hugely significant,” said Jeff Thompson, a physicist at Princeton University and CEO of the neutral atoms startup Logiqal.
Google’s efficient implementation of Shor’s algorithm and Caltech’s new protocol suggest that smaller quantum computers will be able to pull off bigger feats than many researchers had realized. They also mark a turning point at which researchers are beginning to conceal crucial details that competitors or bad actors might find useful. For the first time, Google described their work using a “zero knowledge proof,” a technique for revealing that a program works without revealing exactly how it works.
Robert Huang used a large language model to create a qLDPC code efficient enough to make one virtual qubit from only four atoms.
IQIM, Caltech
Given the rapid quantum progress, physicists say that switching out RSA and ECC for new cryptographic schemes that quantum computers can’t break is essential. In 2024, the National Institute of Standards and Technology published new codes that can keep secrets safe from both classical and quantum computers. And the U.S. government has laid out a plan to completely switch to these new codes by 2035. But some researchers believe that key players may need to act more quickly. Google, for instance, recently announced that it aims to stop relying on RSA and ECC by 2029.
“If you were thinking about when you were going to do a post-quantum crypto transition, you should not be waiting any longer,” Thompson said. “This is the time to do it.”
Quantum Dreams vs. Reality
Opinions range on how plausible it will be for Oratomic to build a quantum computer as formidable as the one the physicists have described on paper. To one leader of neutral atom computing, the Caltech team’s projections are not particularly surprising. “They are broadly in line with what we and others have estimated,” said Lukin of Harvard, a founder of the neutral atom startup QuEra Computing. “But in these resource estimates details matter and it is important to work them out carefully.”
And a few key details remain vague — notably error correction steps crucial to the Caltech team’s rosiest projections — making it hard for external researchers to fully evaluate their claims.
Other researchers question some of the team’s mechanical expectations. For example, the Caltech group made “aggressive assumptions about the speed of operations they can do,” Thompson said. The group claims in its paper that the machine will eventually be able pull off the entire error correction process — check for errors, interpret what it finds, fix the errors, replace any atoms that have gone astray, and prepare to do it all over again — once every millisecond.
The machine would also have to keep up that cadence of error correction for days or even weeks while a computation runs, a feat no group has accomplished. “I’d like to see a demonstration on a smaller scale, say, 100 or 1,000 qubits,” said Mark Saffman, a physicist at the University of Wisconsin-Madison and chief scientist for quantum information at Infleqtion, another neutral atom startup. “Show me that you can do a million rounds or something.”
The Caltech team knows its plan is ambitious and that integrating all the parts it has in mind will require a tremendous engineering and technological effort. At the same time, the physicists don’t see any insurmountable obstacles. “We just have to build these machines and see if they work,” Preskill said.
New Horizons
If any group succeeds at building a quantum computer that can realize Shor’s algorithm, it will mark the end an era — specifically, the “Noisy Intermediate Scale Quantum” era, as Preskill dubbed the pre-error-correction period in a 2018 paper. Each researcher has a vision for what to pursue first with a machine in the new “fault-tolerant” era.
Huang said he would start by running Shor’s algorithm, just to prove that the device works. After that, he said he would try to use it to speed up machine learning — an application to be detailed in coming work.
Most of the architects building quantum computers, whether at Oratomic or other startups, are physicists at heart. They’re interested in physics, not cryptography. Specifically, they’re interested in all the things a computer fluent in the language of quantum mechanics could teach them about the quantum realm, such as what sort of materials might become superconductors even at warm temperatures. Preskill, for his part, would like to simulate the quantum nature of space-time.
The Caltech group knows it has years of work ahead before any of its dreams have a chance of coming true. But the researchers can’t wait to get started. “Pick a cooler life quest than building the world’s first quantum computer with your friends!” said a jubilant Bluvstein, reached by phone shortly before their paper went live, before rushing off to celebrate.
