CoChat
Sign Up
Cited by 1,738Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

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

Open access
Vandersypen, Lieven M. K., Steffen, Matthias, Breyta, Gregory, Yannoni, Costantino S., Sherwood, Mark H., Chuang, Isaac L.·2001·Nature
DOI 10.1038/414883a
Open this paper in CoChat — free accountOpen PDF

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 systems containing many quantum bits, 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.

AI snapshot

Written from the paper’s full text.

TL;DR

The paper reports an NMR implementation of Shor’s quantum factoring algorithm, factoring N = 15 into 3 and 5 using seven spin-1/2 nuclei as qubits. It also presents a parameter-free decoherence model that reproduces the main non-ideal features of the measured spectra.

Key findings

  • Shor’s algorithm was experimentally executed for N = 15 with two parameter choices: a = 11 (“easy” case) and a = 7 (“difficult” case). The output spectra gave period r = 2 for a = 11 and r = 4 for a = 7, yielding gcd(11^2/2 ± 1, 15) = 3, 5 and gcd(7^4/2 ± 1, 15) = 3, 5, respectively.
  • The quantum computer used seven spin-1/2 nuclei: five ^19F and two ^13C, manipulated by room-temperature liquid-state NMR. The difficult case used a sequence of ∼300 spin-selective RF pulses, with the complete Shor sequence lasting up to ∼720 ms.
  • A parameter-free decoherence model, using measured T1 and T2 values and treating generalized amplitude damping and phase damping sequentially, agreed well with the large non-idealities in the data. The paper states this is the first NMR quantum computation experiment for which decoherence is the dominant source of errors.
  • The authors state that scalability to many qubit systems is not implied by this work; the significance lies in demonstrating experimental and theoretical techniques for precise control and modelling of complex quantum computers.

Methods

  • Experiments were performed at IBM Almaden with an 11.7 T (500 MHz) magnet, a custom-modified four-channel Varian Unity INOVA spectrometer, and a Nalorac HFX probe. The molecule was a custom-synthesized perfluorobutadienyl iron complex with the inner two carbons ^13C-labeled, at 0.88 ± 0.04 mole % in diethyl ether-d10, with all experiments at 30 °C.
  • The seven-qubit effective pure state was created by a two-stage temporal averaging scheme summing 4 × 9 = 36 experiments, with state preparation sequences ∼200 ms long. The algorithm was implemented with spin-selective Hermite-180 and Gaussian-90 pulses, shaped in 256 steps, and read out by NMR spectroscopy of the first three qubits.
  • The modular exponentiation and inverse QFT were implemented with a simplified quantum circuit for N = 15, including controlled additions and swaps, followed by spectral analysis to determine the period and factors.

Limitations

  • The paper states that scalability of this NMR approach to many qubit systems is not implied by the present work.
  • The decoherence model assumes independent stochastic relaxation with correlation times ≪ 1/ω_i, uses phenomenological Bloch equations with only T1 and T2 per spin, and treats non-commuting processes as commuting/sequential; the authors note remaining discrepancies due to model approximations and experimental imperfections such as RF inhomogeneity, imperfect calibrations, incomplete field drift compensation, and incomplete unwinding of coupled evolution during RF pulses.
  • The experiment used an ensemble of independent quantum computers, so measurement gives the bitwise average value of 8c/r rather than a sample of 8c/r; this was sufficient for the present experiment, but for larger N a continued fractions algorithm would need to be performed on the quantum computer, requiring additional qubits.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

Crossref · 10.1038/414883a

Cites

33 of 33 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Claims the paper makes

0 of 15 cited sources checked · 0 supported · 0 flagged

  • Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 2

    The paper implemented Shor's algorithm to factor N=15 using seven spin-1/2 nuclei in a molecule as qubits with room-temperature liquid-state NMR.

    “Here we report an implementation of the simplest instance of Shor's algorithm: factorization of N = 1 5 (whose prime factors are 3 and 5). We use seven spin-1/2 nuclei in a molecule as quantum bits [11, 12], which can be manipulated with room temperature liquid state nuclear magnetic resonance techniques.”
    • Also stated in: § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 5 · boosted
      “Thus, even after the long and complex pulse sequence of the difficult case, the experimental data conclusively indicate the successful execution of Shor's algorithm to factor 15.”
    Quote in the paperSubstantial claim
  • Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 6

    The predictive value of the decoherence model was confirmed via independent test experiments.

    “The predictive value of the model was further confirmed via independent test experiments.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Each spin experiences independent stochastic relaxation with correlation time scales much less than 1/ω_i.
    • The authors state this as an assumption: The non-commuting GAD, PD, and ideal unitary evolution processes can be treated as commuting transformations so that simultaneous processes can be modeled sequentially.
  • Findingcitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 6

    This is the first NMR quantum computation experiment for which decoherence is the dominant source of errors.

    “This is the first NMR quantum computation experiment for which decoherence is the dominant source of errors [8]; the demands of Shor's algorithm clearly push the limits of the current molecule, despite its exceptional properties.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [8] Jones, J. A. NMR quantum computation. Prog. NMR Spectrosc. 38, 325–360 (2001). source

      Not checked in the free run.

  • Study design and conductcitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 4

    The effective pure state ρ1 is a suitable initial state for Shor's algorithm because it generates the same signal as |ψ1〉 up to a proportionality constant.

    “We converted ρ th into a 7-spin effective pure state [11, 12] ρ 1 via temporal averaging [9] (step 0); ρ 1 constitutes a suitable initial state for Shor's factoring algorithm since it generates the same signal as | ψ 1 〉 , up to a proportionality constant [11, 12].”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [11] Gershenfeld, N. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350–356 (1997). source

      Not checked in the free run.

    • cites [12] Cory, D. G., Fahmy, A. F. & Havel, T. F. Ensemble quantum computing by NMR spectroscopy. Proc. Natl Acad. Sci. 94, 1634–1639 (1997). source

      Not checked in the free run.

  • Premisecitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 4

    From r, at least one factor of N is given by gcd(a^{r/2}±1,N) with probability greater than 1/2.

    “From r , at least one factor of N is given by the greatest common denominator (gcd) of a r/ 2 ± 1 and N (with probability greater than 1 / 2); the gcd can be computed efficiently using Euclid's algorithm on a classical computer [2] .”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [2] Koblitz, N. A Course in Number Theory and Cryptography (Springer, New York, 1994). source

      Not checked in the free run.

  • The quote only partly states this claim. 1
  • May combine two claims. 11
  • Classified as probably not a substantial claim. 1

  • The quote only partly states this claim.

    Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 5

    There are obvious discrepancies between the measured and ideal spectra, most notably for the difficult case a=7.

    “Nevertheless, there are obvious discrepancies between the measured and ideal spectra, most notably for the difficult case.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 5

    For a=7, the output spectra indicate the first register is in a mixture of |0〉, |2〉, |4〉, and |6〉, giving period r=4 and factors 3 and 5.

    “The periodicity in the amplitude of | y 〉 is now 2, so r = 8 / 2 = 4 and gcd(7 4 / 2 ± 1 , 15) = 3 , 5. Thus, even after the long and complex pulse sequence of the difficult case, the experimental data conclusively indicate the successful execution of Shor's algorithm to factor 15.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 6

    The parameter-free decoherence model agrees well with the large non-idealities of the experimental spectra, though some discrepancies remain.

    “While some discrepancies between the data and the simulations remain (due to the approximations in the model as well as due to experimental imperfections such as RF inhomogeneity, imperfect calibrations, incomplete field drift compensation and incomplete unwinding of coupled evolution during the RF pulses [15]), the model agrees well with the large non-idealities of the data.”
    Quote in the paperSubstantial claim
    • The authors state this as an assumption: Each spin experiences independent stochastic relaxation with correlation time scales much less than 1/ω_i.
    • The authors state this as an assumption: The non-commuting GAD, PD, and ideal unitary evolution processes can be treated as commuting transformations so that simultaneous processes can be modeled sequentially.

  • May combine two claims.

    Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 4

    For a=11, the output spectra indicate the first register is in a mixture of |0〉 and |4〉, giving period r=2 and factors 3 and 5.

    “The periodicity in the amplitude of | y 〉 is thus 4, so r = 2 n / 4 = 2 and we find that gcd(11 2 / 2 ± 1 , 15) = 3 , 5. The prime factors thus unambiguously derive from the output spectra.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Findingcitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 3

    The seven spins in the molecule are remarkably well separated in frequency and interact pairwise via J-coupling.

    “All seven spins in this molecule are remarkably well separated in frequency ω i / 2 π , and interact pairwise via the J -coupling, described by H J = ∑ i<j 2 π ¯ hJ ij I zi I zj [17].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [17] Schack, R. & Caves, C. M. Classical model for bulk-ensemble NMR quantum computation. Phys. Rev. A 60, 4354–4362 (1999). source

      Not checked in the free run.

  • Probably not a substantial claim: may not pass S3 (load-bearing).

    Findingown data
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 6

    The 7-spin simulation of the complete Shor pulse sequence required only a few minutes on an IBM quad power 3-II processor.

    “Using this simple model, the 7spin simulation of the complete Shor pulse sequence, including 36 temporal averaging sequences, required only a few minutes on an IBM quad power 3-II processor machine.”
    Quote in the paperNot a substantial claim
    • The authors state this as an assumption: Each spin experiences independent stochastic relaxation with correlation time scales much less than 1/ω_i.
    • The authors state this as an assumption: The non-commuting GAD, PD, and ideal unitary evolution processes can be treated as commuting transformations so that simultaneous processes can be modeled sequentially.

  • May combine two claims.

    Interpretationreasoning
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 2

    Quantum factorization of N=15 requires coherent control over seven qubits and interactions between almost all pairs of qubits, even after maximal reduction of the quantum circuit.

    “Even for such a small N , quantum factorization poses at present a significant experimental challenge: it requires coherent control over seven quantum bits (qubits) in the course of a long sequence of controlled interactions, even after maximal reduction of the quantum circuit; including the state initialization, interactions between almost all pairs of qubits are needed.”
    Quote in the paperSubstantial claim

  • May combine two claims.

    Premisecitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 2

    Shor's algorithm determines the period of f(x)=a^x mod N and from this period factors N with high probability.

    “Shor's factoring algorithm works by utilizing a quantum computer to quickly determine the period of the function f ( x ) = a x mod N (the remainder of a x divided by N ), where a is a randomly chosen small number with no factors in common with N ; from this period, number-theoretic techniques can be employed to factor N with high probability [4].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [4] Shor, P. in Proc. 35th Annu. Symp. on the Foundations of Computer Science (ed. Goldwasser, S.) 124–134 (IEEE Computer Society Press, Los Alamitos, California, 1994). source

      Not checked in the free run.

  • May combine two claims.

    Premisecitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 2

    The simplest meaningful instance of Shor's algorithm is factorization of N=15; the algorithm fails for N even or a prime power.

    “The simplest meaningful instance of Shor's algorithm is factorization of N = 15 [7] - the algorithm fails for N even or a prime power.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [7] Beckman, D., Chari, A. N., Devabhaktuni, S. & Preskill, J. Efficient networks for quantum factoring. Phys. Rev. A 54, 1034–1063 (1996). source

      Not checked in the free run.

  • May combine two claims.

    Premisecitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 5

    A full description of relaxation for the seven coupled spins involves almost 4^7 × 4^7 degrees of freedom and requires knowledge of physical properties of the molecule which are not available.

    “A full description of relaxation for the seven coupled spins involves almost 4 7 × 4 7 degrees of freedom and requires knowledge of physical properties of the molecule which are not available [23, 24].”
    Quote in the paperSubstantial claim0 of 2 sources checked
    • cites [23] Kraus, K. States, Effects, and Operations: Fundamental Notions of Quantum Theory (Springer, Berlin, 1983). source

      Not checked in the free run.

    • cites [24] Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information (Cambridge Univ. Press, Cambridge, 2000).

      Not checked in the free run.

  • May combine two claims.

    Premisecitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 2

    Classical prime factorization takes O(2^{l^{1/3}}) operations and becomes intractable as l increases.

    “Classically, in contrast, prime factorization takes O (2 l 1 / 3 ) operations [1], which quickly becomes intractable as l increases.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [1] Knuth, D. E. The Art of Computer Programming Vol. 2, Seminumerical Algorithms (Addison-Wesley, Reading, Massachusetts, 1998).

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 3

    Three qubits in the first register allow detection of more periods and constitute a more stringent test of modular exponentiation and QFT than two qubits.

    “Thus, the first register can be as small as two qubits ( n = 2); however, three qubits ( n = 3) allow for the possibility of detecting more periods and thus constitutes a more stringent test of the modular exponentiation and QFT [15].”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [15] Freeman, R. Spin Choreography (Spektrum, Oxford, 1997).

      Not checked in the free run.

  • May combine two claims.

    Interpretationcitation
    § Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance · p. 4

    In the ensemble experiment, the measurement gives the bitwise average value of 8c/r instead of a sample, which is sufficient to determine r in the present experiment.

    “In the experiment, an ensemble of independent quantum computers rather than a single quantum computer was used, so the measurement gives the bitwise average value of 8 c/r , instead of a sample of 8 c/r . This is sufficient to determine r in the present experiment, but for larger N a continued fractions algorithm will need to be performed on the quantum computer [11] requiring additional qubits.”
    Quote in the paperSubstantial claim0 of 1 sources checked
    • cites [11] Gershenfeld, N. & Chuang, I. L. Bulk spin-resonance quantum computation. Science 275, 350–356 (1997). source

      Not checked in the free run.

13 of 13

  • The authors state this as an assumption.

    Each spin experiences independent stochastic relaxation with correlation time scales much less than 1/ω_i.

    “In order to get a first estimate of the impact of decoherence during the factoring pulse sequence we assume that each spin experiences independent stochastic relaxation with correlation time scales ≪ 1 /ω i .”

  • The authors state this as an assumption.

    The non-commuting GAD, PD, and ideal unitary evolution processes can be treated as commuting transformations so that simultaneous processes can be modeled sequentially.

    “However, GAD does not commute with e -i H t , and PD and GAD do not commute with the ideal unitary evolution during RF pulses. Nevertheless, we have treated these as commuting transformations, such that all of the processes which occur simultaneously can be modeled sequentially.”

  • The paper relies on this without support.

    An effective pure ground state of all seven spins had never been created before.

    “To create an effective pure ground state of all seven spins, which has never been done before, we used a two-stage extension of the scheme of Ref. [9], necessary because ω 13 C is very different from ω 19 F .”
3 of 3

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • In these optical experiments during the computation, genuine multi-particle entanglement and multi-path interference were observed, which did not appear in previous implementations using nuclear magnetic resonance.

    “It is notable that in these optical experiments during the computation genuine multi-particle entanglement and multi-path interference were observed, which did not appear in the previous implementations using nuclear magnetic resonance (Vandersypen et al. 2001).”

    From Multiphoton entanglement and interferometry (2012) · cites this paper as Vandersypen et al. 2001

    The description of the NMR experiment (p. 3) says its effective pure state remained separable under unitary transformations, supporting the absence of genuine multi-particle entanglement. The Fig. 1 caption (p. 12) describes interference in Shor’s algorithm, but our copy does not establish whether multi-path interference was observed in this NMR experiment or compare it with the optical experiments. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • In the only demonstration to date, a compiled set of gate operations were implemented in a liquid NMR architecture.

    “In the only demonstration to date, a compiled set of gate operations were implemented in a liquid NMR architecture [14].”

    From Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement (2007) · cites this paper as [14]

  • The inverse QFT in Ref. [14] was unnecessary; this is true for any order-2^l circuit.

    “Thus the inverse QFT in Ref. [14] was unnecessary: indeed, it is straightforward to show this is true for any order-2 l circuit.”

    From Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement (2007) · cites this paper as [14]

Cites

Flagged first, then by citations

1 of the 34 references couldn’t be matched to a known paper.

Research works printed but not linked: 2

  1. Schulman, L. & Vazirani, U. in Proc. 31st ACM Symp. on Theory of Computing 322–329 (Association for Computing Machinery, New York, 1999).
  2. Freeman, R. Spin Choreography (Spektrum, Oxford, 1997).

Cited by

Sorted by citations

Related

Authors
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L.
Affiliations
IBM Research - Almaden (US)
ORCID
Venue
Nature
Publisher
Springer Science and Business Media LLC
Published
2001-12
Volume
414
Issue
6866
Pages
883-887
ISSN
  • 0028-0836 (ISSN-L)
  • 1476-4687
DOI
10.1038/414883a
OpenAlex
W2159226773
Semantic Scholar
eec83aa6e6746cab27ca7b5dd7e9535646ee65a2
Cited by
1,738
References
34
Citations by year
2026: 37 · 2025: 41 · 2024: 66 · 2023: 97 · 2022: 82 · 2021: 75 · 2020: 58 · 2019: 96 · 2018: 41 · 2017: 79 · 2016: 65 · 2015: 55 · 2014: 60 · 2013: 56 · 2012: 74
FWCI
83.11
Type
journal article
Language
en
Open access
Licence
www.springer.com/tdm (tdm)
Locations
  • Nature (publishedVersion)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (acceptedVersion)
  • RePEc: Research Papers in Economics (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
Shor's algorithm, quantum factoring, integer factorization, nuclear magnetic resonance, quantum computing, spin-1/2 nuclei, decoherence, qubits

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Claims read by deepseek-v4.1-flash under definition version 3 (extract-v3) on 2026-10-10.

Classified by jev-1.13-20260917 (gold-guideline-v0.2) on 2026-10-10.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review