Skip to content
The methodOpen data
Back to the collection

Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance

Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta

Show all 6 authors

Costantino S. Yannoni, Mark H. Sherwood, Isaac L. Chuang

2001 · arXiv

PhysicsAlgorithmsSecurity & cryptography
Read the paper
HN score
0
Mentions
7
Readers
4
Months
6
What’s in a score?

From the abstract

The number of steps any classical computer requires in order to find the prime factors of an $l$-digit integer $N$ increases exponentially with $l$, at least using algorithms known at present. Factoring large integers is therefore conjectured to be intractable classically, an observation underlying the security of widely used cryptographic codes. Quantum computers, however, could factor integers in only polynomial time, using Shor's quantum factoring algorithm. Although important for the study of quantum computers, experimental demonstration of this algorithm has proved elusive. Here we report an implementation of the simplest instance of Shor's algorithm: factorization of ${N=15}$ (whose prime factors are 3 and 5). We use seven spin-1/2 nuclei in a molecule as quantum bits, which can be manipulated with room temperature liquid state nuclear magnetic resonance techniques. This method of using nuclei to store quantum information is in principle scalable to many quantum bit systems, but such scalability is not implied by the present work. The significance of our work lies in the demonstration of experimental and theoretical techniques for precise control and modelling of complex quantum computers. In particular, we present a simple, parameter-free but predictive model of decoherence effects in our system.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

7 selected excerpts · 7 total mentions

Strilanc
Neutral mention · rule
> That graph suggests that even with the best error correction in the graph, it is impossible to factor RSA-4 with less then 10^4 qubits. Which seems very odd. It's because the plot is assuming the use of error correction even for the smallest cases. Error correction has minimum quantity and quality bars that you must clear in order for it to work at all, and most of the cost of breaking RSA4 is just clearing those bars. (You happen to be able to do RSA4 without error correction, as was done in 2001 [0], but it's kind of irrelevant because you need error correction to scale so results without it are on the wrong trendline. That's even more true for the annealing stuff…
Read the full comment
Scott mentioned, which has absolutely no chance of scaling.) You say you don't see the uranium piling up. Okay. Consider the historically reported lifetimes of classical bits stored using repetition codes on the UCSB->Google machines [1]. In 2014 the stored bit lived less than a second. In 2015 it lived less than a second. 2016? Less than a second. 2017? 2018? 2019? 2020? 2021? 2022? Yeah, less than a second. And this may not surprise you but yes, in 2023, it also lived less than a second. Then, in 2024... kaboom! It's living for hours [4]. You don't see the decreasing gate error rates [2]? The increasing capabilities [3]? The ever larger error correcting code demonstrations [4]? The front-loaded costs and exponential returns inherent to fault tolerance? TFA is absolutely correct: the time to start transitioning to PQC is now. [0]: https://www.nature.com/articles/414883a [1]: https://algassert.com/assets/2025-12-24-qec-foom/plot-half-l... (from https://algassert.com/post/2503 ) [2]: https://arxiv.org/abs/2510.17286 [3]: https://www.nature.com/articles/s41586-025-09596-6 [4]: https://www.nature.com/articles/s41586-024-08449-y
Original comment A Cryptography Engineer's Perspective on Quantum Computing Timelines
JanisErdmanis
Neutral mention · rule
It is! Taking into account that only the Schor algorithm is proven to be exponentially faster in factorising numbers and looking into current progress on using it, the threat for RSA 2048 will become real in ridiculous 2^2048 years. This can be estimated by taking three events in factorisation: 2002: factorisation of 15 [1] 2012: factorisation of 21 [2] 2022: factorisation of 35 by IBM (although the article is about number 21, but let’s give them credit) [3] In a plot, the tendency is somewhat linear, with the factorised number increasing by one every year. A sceptic immediately replies to this thread, saying we already have 100-1000 qubit quantum computers and are on the…
Read the full comment
path to getting a million qubits in the foreseeable future. That may as well be true. The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits. This is also why the line for factorisation is about to be linear. If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear. The error correction is not a panacea either. It does not reduce errors to zero for logical qubits but rather reduces them after the error threshold is reached. It would require repeated application to get the necessary error threshold to run the Schor algorithm for a desired number, which would require an unreasonable number of qubits. [1]: https://www.nature.com/articles/414883a [2]: https://www.nature.com/articles/nphoton.2012.259 [3]: https://arxiv.org/pdf/2103.13855v1.pdf
Original comment Parent story unavailable in snapshot
chrislipa
Neutral mention · rule
While, you're right, it is minimalistic, Einstein's Statistical Ensemble Interpretation is an incomplete theory. It doesn't tell you which possible future you'll end up in. And if you try to patch the theory by saying there's some deeper element of reality that we just haven't found yet that's deciding the outcome of experiments, then the violation of the Bell Inequalities renders that whole line of thinking moot. If, instead, you try to patch it the other way and say that everything in the ensemble is real, then you've just reinvented Many Worlds by a different name. I'm unclear why you're bringing up Hitach's experiment and what you think it shows. Maybe you could…
Read the full comment
elaborate? My understanding is that the raison d'être of the experiment is to show that multiple particles are not necessary for quantum interference to occur, and that a single particle is perfectly capable of destructively interfering with itself. This is pretty direct evidence for superposition, because you're getting measurable effects from the superposition. And if anything, it's evidence against the Ensemble Interpretation. Also, quantum computers are real and here today. Any successful theory of physics must explain how 15 was factored using Shor's Algorithm. (http://arxiv.org/abs/quant-ph/0112176)
Original comment Can the multiverse explain human history?
Strilanc
Neutral mention · rule
The very first demonstration of factoring 15 with a quantum computer, back in 2001, used a valid modular exponentiation circuit [1]. The trickiest part of the circuit is they compile conditional multiplication by 4 (mod 15) into two controlled swaps. That's a very elegant way to do the multiplication, but most modular multiplication circuits are much more complex. 15 is a huge outlier on the difficulty of actually doing the modular exponentiation. Which is why so far 15 is the only number that's been factored by a quantum computer while meeting the bar of "yes you have to actually do the modular exponentiation required by Shor's algorithm". [1]: https://arxiv.org/pdf/quant-ph/0112176#page=15
Original comment It looks like the “JVG algorithm” only wins on tiny numbers
Strilanc
Neutral mention · rule
I'm not trying to be evasive. I'm directly saying quantum computers won't factor interesting numbers for years. That's more typically described as biting the bullet. There are several experiments that claim to factor 15 with a quantum computer (e.g. [1][2]). But beware these experiments cheat to various degrees (e.g. instead of performing period finding against multiplication mod 15 they do some simpler process known to have the same period). Even without cheating, 15 is a huge outlier in the simplicity of the modular arithmetic. For example, I think 15 is the only odd semiprime where you can implement modular multiplication by a constant using nothing but bit flips and…
Read the full comment
bit swaps. Being so close to a power of 2 also doesn't hurt. Beware there's a constant annoying trickle of claims of factoring numbers larger than 15 with quantum computers, but using completely irrelevant methods where there's no reason to expect the costs to scale subexponentially. For example, Zapata (the quantum startup that recently went bankrupt) had one of those [3]. [1]: https://www.nature.com/articles/414883a [2]: https://arxiv.org/abs/1202.5707 [3]: https://scottaaronson.blog/?p=4447
Original comment Parent story unavailable in snapshot
JanisErdmanis
Neutral mention · rule
The threat estimate for a quantum computer that breaks cryptography shall be based on currently available data and the understanding that only the Schor algorithm is known to provide exponential speedup for factorisation. Let’s give IBM credit for attempting to factor in the number 35 in 2022, although they failed there [1]. Before that, the successful factorisation happened for the number 21 in 2012 [2] and the first factorisation of 15 in 2001 [3]. Now we have three points. There is a trend that the factorised number grows by a number of 10 for every ten years. Thus, to get a quantum computer that facilitates RSA-2048, we shall wait for 2^2048 years. [1]: https://arxiv.org/pdf/2103.13855v1.pdf [2]: https://www.nature.com/articles/nphoton.2012.259 [3]: https://www.nature.com/articles/414883a
Original comment Parent story unavailable in snapshot

Keep following the thread.

More in Physics

More from the same topics.