This article is based on a conversation between Peter Shor and Daniel Rodán Legrain as part of the Quantum Builders series, sponsored by Qblox. Watch the full webinar for more on Shor's algorithm, quantum error correction, and the open questions that still shape the field.
Before 1994, most people working on quantum information were treated as if they were chasing something useless. Peter Shor describes the field he walked into in plain terms.
"A lot of people thought that everyone studying quantum information was crazy and they were pursuing something that would never be practical and was completely useless," Shor says.
The algorithm he discovered that year changed that almost overnight. But the story behind it, and what Shor thinks the field still hasn't figured out, is even more interesting than the textbook version.
Shor's path to the factoring algorithm began with a conference submission from Dan Simon.
"I saw Dan Simon's paper. Actually, I saw it in a program committee where we managed to reject it."
The rejected paper introduced what's now called Simon's problem. It looked abstract, but Shor recognized something underneath it. Simon's algorithm finds a period over a binary vector field. The structure of that period-finding, Shor realized, could be adapted to a different kind of period, the kind that shows up in number theory.
He worked on it quietly. His job at Bell Labs was finding classical algorithms, and quantum work still carried a reputation.
"I didn't actually tell anyone I was working on quantum algorithms before I discovered the discrete log algorithm because I thought it would be pursued basically as a waste of time."
The first algorithm he found was for discrete log, not factoring. Factoring came later that same week, after his colleague Jeff Lagarias, a number theorist, suggested he look at it, given the historical link between the two problems.
The story of how the world found out is even stranger. Shor gave a talk on the discrete log result at an internal Bell Labs seminar on a Tuesday. By the following weekend, Umesh Vazirani called him from Berkeley.
"He said, I hear you have a quantum algorithm for factoring."
Vazirani had the wrong problem. But by the time he called, Shor had found that one, too.
"I didn't tell him that his information was wrong. I just described the algorithm for factoring."
What's often left out of the story of Shor's algorithm is that Shor himself didn't think it would run.
"For a while after I discovered the algorithm, I thought it would not work.”
Without error correction, a quantum computer can do roughly ten useful steps. To run a million steps, gates need to be accurate to one part in a million, which the field still hasn't reached. To run a billion steps, you need accuracy to one part in a trillion, which experimentalists would tell you is impossible right now.
In 1994, the conventional wisdom said you couldn't do error correction on a quantum computer at all. There were no-go theorems. Researchers like Rolf Landauer and Asher Peres were pointing this out in talks and papers.
"A lot of people believed that quantum computers, that the factoring algorithm was a great theoretical discovery, but it would never be practical."
The work that followed, the nine-qubit code, CSS codes, stabilizer codes, the threshold theorem, was Shor proving the no-go arguments wrong.
Most people treat fault-tolerant quantum computing as a settled architectural problem. Shor doesn't.
"I'm not convinced that we really know the best way to do fault tolerance in quantum computers. And in fact, I'm sure we don't because there are lots and lots of advances happening right now."
He points to quantum low-density parity-check codes (qLDPC codes) as the current frontier.
"The advances in qLDPC codes over the last few years have been really enormous. And I suspect that LDPC codes are going to be the clear choice in another few years."
Surface codes have been the working standard for fault-tolerant designs. Whether qLDPC codes already outperform them is, by Shor's read, an open empirical question. Either way, the architecture the field eventually settles on for large-scale machines probably hasn't been finalized yet.
That has implications for anyone building hardware now. The codes you optimize for today may not be the ones that win.
Ask most people what's slowing quantum computing down, and you'll hear "qubits" or "noise." Shor's answer is different.
"We don't have enough quantum algorithms."
He draws an analogy to the simplex algorithm in classical computing. George Dantzig developed it in the 1940s. For nearly fifty years, theorists could prove it took exponential time on worst-case inputs, but in practice, it ran fast on almost everything. The reason the simplex algorithm survived that gap was that people had classical computers to run it on. They could see it worked, even when no one could prove why.
Quantum is in the inverse situation. Plenty of algorithms might work in practice. No one can run them at scale to find out.
"It's quite possible that when we actually get larger quantum computers, we'll be able to test some of these algorithms and show that they really work."
For researchers entering the field, that's a useful reframe. The next generation of quantum algorithms may not come from people who can prove a clean speedup on paper. They may come from people who can test ideas on real hardware and see which survive exposure to noise.
Shor doesn't expect a quantum computer capable of breaking RSA for another ten to twenty years. But that doesn't mean organizations have ten to twenty years to migrate.
"Some of these conversations that are being recorded today are going to be very useful to governments twenty years from now. And twenty years from now is not an unreasonable time frame for breaking quantum computers large enough to break RSA."
The threat isn't your credit card. The first machines capable of breaking RSA will take hours per key. The high-priority targets, intercepted communications stored by intelligence agencies, are what get decrypted first.
When asked when organizations should have started transitioning to post-quantum cryptography, his answer was direct.
"For the people who have the most sensitive information, we should have started ten years ago. But we didn't."
For everyone else, the framework looks closer to Y2K. The migration is significant, but if you start now, you have runway.
Shor's career advice is the opposite of "specialize early."
The reason he found the factoring algorithm, by his own account, was that he had taken a wide range of courses that nobody at the time would have called relevant to each other. Algorithms. Physics. Cryptography. Number theory.
"A broad range of courses is what enabled me to find the factoring algorithm."
He extends that to current students.
"If there's some course you're interested in in some area of abstract math or computer science that doesn't look at all like it would be useful for quantum computing or physics, similarly, go ahead and take it. Because at some point, this area is going to be important for quantum computing. And when that happens, you will be the only person in the field who has the requisite knowledge to solve whatever problem needs this knowledge."
His example: topological quantum field theory, which seemed entirely abstract until it became the basis for some of the most interesting quantum codes in use today.
Shor sees two areas where quantum computers will likely surpass classical ones first.
The first is Hamiltonian simulation. Setting up a quantum system to behave like the physical system you want to study, then letting it evolve and watching what happens. Neutral atom arrays and trapped ion systems are already approaching this.
"I think that's one area where you'll see quantum computers work better than classical computers fairly soon."
The second is quantum sensing, an area he flags as undervalued in the current conversation. Techniques from quantum information theory may apply to sensing in ways that haven't been fully worked out.
On the hype side, he's measured.
"Not all the applications of quantum computing that people are looking at right now are going to pan out. And I think the same thing is true for deep learning. Not all the proposed applications for deep learning are going to pan out either."
His example of a likely miss: using quantum computers to make better stock market investments. His example of where quantum and AI might eventually meet, but probably not yet: any application that requires both a clean theoretical grounding and the ability to run at scale, since right now neither exists.
"For quantum computing, we have a lot of theory for how it works, but we can't program it up and see that it works yet. So if you have quantum theory plus AI, it's very difficult to know which of the proposals might actually work."
A few things stand out across the conversation.
The architecture isn't finalized. Anyone treating today's fault-tolerance schemes as the endpoint is going to be wrong about something important.
The algorithm pipeline is thin. The field needs more researchers building things and testing them, not only proving them.
The migration window for cryptography is shorter than the development window for quantum hardware, because the threat model includes data being stored today and broken later.
Those who end up doing the most interesting work over the next decade are likely the ones whose backgrounds don't look obviously quantum on paper. That was true in 1994. Shor's bet is that it stays true.
Scaling quantum systems requires more than individual advances. It requires coordination across hardware, software, and infrastructure. Qblox works alongside research teams, industry partners, and system builders to make that possible. If you're exploring how to move from experiments to systems, we'd be glad to connect.
Contact us to learn how Qblox supports scalable quantum systems.
